C++ STL Queue(큐) 사용법

큐(queue)는 데이터 구조의 일종으로, First In, First Out(FIFO) 원리에 따라 동작합니다. 즉, 먼저 들어온 데이터가 먼저 나가게 됩니다. 큐는 다양한 프로그래밍 문제에서 유용하게 사용됩니다. 이번 블로그 포스트에서는 C++에서 큐의 기본 개념과 사용법, 구현 방법, 그리고 다양한 응용에 대해 알아보겠습니다.

Queue의 기본 개념

큐는 FIFO(First In, First Out) 방식으로 동작합니다.

이는 데이터가 삽입된 순서와 동일한 순서로 제거된다는 의미입니다. 큐는 일상 생활에서도 쉽게 찾아볼 수 있습니다.

예를 들어, 은행에서 대기하는 사람들의 순서가 유사한 구조입니다.

가장 먼저온 사람이 가장 먼저 업무를 처리 할 수 있듯 큐도 먼저 들어온 데이터 부터 처리할 수 있습니다.

 

큐의 주요 연산은 다음과 같습니다:

• Enqueue: 큐의 뒤쪽에 새로운 요소를 추가합니다.
• Dequeue: 큐의 앞쪽에서 요소를 제거하고 반환합니다.
• Front: 큐의 가장 앞쪽에 있는 요소를 반환하지만 제거하지는 않습니다.
• Back: 큐의 가장 뒤쪽에 있는 요소를 반환합니다.
• Empty: 큐가 비어 있는지 확인합니다.
• Size: 큐에 포함된 요소의 수를 반환합니다.

Queue 구현

C++에서는 큐를 표준 템플릿 라이브러리(STL)에서 제공하는 std::queue를 사용하여 쉽게 구현할 수 있습니다.

내부적으로 덱(deque) 또는 리스트(list)를 기반으로 구현됩니다. 기본적인 사용법은 다음과 같습니다.

#include <iostream>
#include <queue>
 
int main() {
    std::queue<int> q;
 
    // 요소 추가
    q.push(1);
    q.push(2);
    q.push(3);
 
    // 요소 출력 및 제거
    while (!q.empty()) {
        std::cout << "Front element: " << q.front() << std::endl;
        q.pop();
    }
 
    return 0;
}

큐는 다양한 상황에서 유용하게 사용됩니다. 몇 가지 대표적인 용도를 살펴보겠습니다:

• BFS (Breadth-First Search): 그래프 탐색 알고리즘인 BFS에서 큐는 노드를 탐색하기 위한 중요한 도구입니다.
  노드를 방문한 순서대로 큐에 추가하고, 큐에서 노드를 하나씩 꺼내어 탐색을 진행합니다.
• 작업 스케줄링: 작업 큐를 사용하여 실행할 작업들을 관리할 수 있습니다.
  이때 큐는 작업의 우선 순위나 실행 순서를 관리하는 데 유용합니다.

변형

큐에는 여러 가지 변형이 있으며, 각 변형은 특정 용도에 맞게 설계되었습니다.

   1. 우선순위 큐 (Priority Queue)

우선순위 큐는 각 요소가 우선순위를 가지며, 우선순위가 높은 요소가 먼저 제거됩니다. C++에서는 std::priority_queue를 사용하여 구현할 수 있습니다.

#include <iostream>
#include <queue>
#include <vector>
 
int main() {
    std::priority_queue<int> pq;
 
    pq.push(10);
    pq.push(5);
    pq.push(20);
 
    while (!pq.empty()) {
        std::cout << "Top element: " << pq.top() << std::endl;
        pq.pop();
    }
 
    return 0;
}
 

    2. 원형 큐 (Circular Queue)

      원형 큐는 큐의 끝과 시작이 연결된 구조입니다. 원형 큐는 메모리 사용을 최적화하고, 큐의 최대 크기를 고정할 수 있        어 효율적인 queue 관리가 가능합니다. C++에서는 배열을 이용하여 직접 구현할 수 있습니다.

#include <iostream>
#include <vector>
 
class CircularQueue {
private:
    std::vector<int> data;
    int front, rear, size, capacity;
 
public:
    CircularQueue(int cap) : capacity(cap), front(0), rear(-1), size(0) {
        data.resize(capacity);
    }
 
    void enqueue(int value) {
        if (size == capacity) {
            std::cout << "Queue is full!" << std::endl;
            return;
        }
        rear = (rear + 1) % capacity;
        data[rear] = value;
        ++size;
    }
 
    void dequeue() {
        if (size == 0) {
            std::cout << "Queue is empty!" << std::endl;
            return;
        }
        front = (front + 1) % capacity;
        --size;
    }
 
    int frontElement() const {
        return data[front];
    }
 
    bool isEmpty() const {
        return size == 0;
    }
 
    bool isFull() const {
        return size == capacity;
    }
};
 
int main() {
    CircularQueue cq(3);
 
    cq.enqueue(1);
    cq.enqueue(2);
    cq.enqueue(3);
    cq.enqueue(4); // Should indicate that the queue is full
 
    while (!cq.isEmpty()) {
        std::cout << "Front element: " << cq.frontElement() << std::endl;
        cq.dequeue();
    }
 
    return 0;
}
 

큐를 사용할 때 주의할 점은 큐의 크기와 메모리 사용을 관리하는 것입니다.

특히, 큐의 최대 크기를 초과하지 않도록 관리하거나, 큐가 비어 있을 때의 처리를 신경 써야 합니다.

효율적인 큐 관리는 프로그램의 성능에 큰 영향을 미칠 수 있습니다.