Queue 자료구조 예제 및 정리

Queue

queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조이다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가진다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. queue는 C++ 표준 라이브러리(Standard Template Library)에 있는 정의 되어 있어 필요할 때마다 만들어 사용하지 않고 include 하여 사용하면 편리하다.

 

Queue의 특징

1. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조 
2. 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함 
3. 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행함  

4. 그래프의 넓이 우선 탐색(BFS)에서 사용
5. 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴

---

아래는 큐 자료구조를 활용한 백준 #18258 큐2의 소스코드이다.

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    queue<int> q;
    while(N-->0) { 
        string s;
        cin >> s;

        if (!s.compare("push")) {
            int a;
            cin >> a;

            q.push(a);
        }
        else if (!s.compare("pop")) {
            if (q.empty()) cout << -1 << '\n';
            else {
                cout << q.front() << '\n';
                q.pop();
            }
        }
        else if (!s.compare("size")) cout << q.size() << '\n';
        else if (!s.compare("empty")) q.empty() ? cout << 1 << '\n' : cout << 0 << '\n';
        else if (!s.compare("front")) {
            if (q.empty()) cout << -1 << '\n';
            else cout << q.front() << '\n';
        }
        else if (!s.compare("back")) {
            if (q.empty()) cout << -1 << '\n';
            else cout << q.back() << '\n';
        }
    }

    return 0;
}