[c++] 큐(Queue) 데이터 구조

08 Dec 2023

큐는 선입선출(FIFO, First-In-First-Out) 방식으로 동작하는 데이터 구조입니다. 이는 가장 먼저 추가된 데이터가 가장 먼저 제거되는 구조를 말합니다. 큐는 많은 응용 프로그램에서 사용되며, 대기열(queue), 버퍼(buffer) 등으로도 불립니다.

큐의 구현

배열을 사용한 구현

#include <iostream>
#define MAX_SIZE 100

class Queue {
    int arr[MAX_SIZE];
    int front, rear;

public:
    Queue() {
        front = -1;
        rear = -1;
    }

    void enqueue(int data) {
        if (rear == MAX_SIZE - 1) {
            std::cout << "Queue is full" << std::endl;
            return;
        }
        arr[++rear] = data;
        if (front == -1) {
            front++;
        }
    }

    void dequeue() {
        if (front == -1 || front > rear) {
            std::cout << "Queue is empty" << std::endl;
            return;
        }
        std::cout << "Dequeued element: " << arr[front++] << std::endl;
    }
};

연결 리스트를 사용한 구현

#include <iostream>

struct Node {
    int data;
    Node* next;
};

class Queue {
    Node* front;
    Node* rear;

public:
    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    void enqueue(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = nullptr;
        if (front == nullptr) {
            front = newNode;
            rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    void dequeue() {
        if (front == nullptr) {
            std::cout << "Queue is empty" << std::endl;
            return;
        }
        std::cout << "Dequeued element: " << front->data << std::endl;
        front = front->next;
    }
};

큐의 연산

enqueue(data)

큐에 데이터를 추가합니다. 배열 기반의 큐에서는 배열의 끝에 데이터를 추가하고, 연결 리스트 기반의 큐에서는 새로운 노드를 생성하여 뒤에 추가합니다.

dequeue()

큐에서 데이터를 제거하고 반환합니다. 배열 기반의 큐에서는 앞쪽의 요소를 제거하고, 연결 리스트 기반의 큐에서는 첫 번째 노드를 제거합니다.

마무리

큐는 데이터의 순서가 중요한 경우에 유용하게 사용될 수 있습니다. 다양한 응용프로그램에서 큐가 어떻게 활용되는지 공부하고, 필요한 경우 해당 구조를 사용하여 프로그래밍할 수 있습니다.

참고: GeeksforGeeks - Queue Data Structure