4. 큐

큐

빠른 설명

큐는 먼저 넣은 원소가 먼저 나오는 FIFO 구조다. BFS, 줄 서기, 시간 순서대로 퍼지는 시뮬레이션에서 많이 쓴다.

언제 쓰는가

• 먼저 들어온 작업을 먼저 처리할 때
• 그래프에서 가까운 정점부터 방문할 때
• 동시에 퍼지는 현상을 단계별로 처리할 때

시간복잡도

• push/enqueue: $O(1)$
• pop/dequeue: $O(1)$
• front 확인: $O(1)$

참고자료

• Wikipedia - Queue
• cppreference - std::queue
• Python Tutorial - Using Lists as Queues
• Python - collections.deque

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    queue<int> q;
 
    q.push(1);
    q.push(2);
    q.push(3);
 
    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
}

Python 코드

from collections import deque
 
q = deque()
q.append(1)
q.append(2)
q.append(3)
 
while q:
    print(q[0], end=" ")
    q.popleft()