큐 (Queue)

정의

큐 (Queue) 는 FIFO (First In, First Out) 순서로 원소를 관리하는 추상 자료구조입니다. push(x) (또는 enqueue), pop() (또는 dequeue), front() 세 연산만 제공하며, 가장 먼저 삽입된 원소만 접근 가능합니다.

C++ STL std::queue, Python collections.deque, Java LinkedList / ArrayDeque 로 기본 제공됩니다.

문제 상황과 동기

BFS (너비 우선 탐색), 작업 스케줄링, 프린터 큐, 윈도우 처리 등 “먼저 들어온 것을 먼저 처리” 해야 하는 모든 문제에서 큐가 필수입니다.

• naive: 배열 맨 앞 원소 제거는 O(N) (뒤 원소들을 앞으로 shift).
• circular queue: 배열 + head/tail 포인터로 push/pop 모두 O(1).
• deque (양방향 큐): 양 끝에서 모두 push/pop 가능. BFS 변형 (0-1 BFS, deque BFS) 에서 필수.

핵심 통찰: BFS = 레벨 순서 순회 = 큐. DFS 는 스택, BFS 는 큐.

시각화

핵심 아이디어

invariant: front 는 가장 오래된 원소, back 은 가장 최근 원소. 삽입 / 삭제 순서가 순서 그대로.

원형 큐 (Circular Queue)

배열 크기 N 으로 고정, head 와 tail 인덱스를 mod N 으로 순환. 배열 재할당 없이 push/pop O(1).

push(x):
    queue[tail] = x
    tail = (tail + 1) % N

pop():
    result = queue[head]
    head = (head + 1) % N
    return result

full():
    return (tail + 1) % N == head

Deque (양방향 큐)

front / back 양쪽에서 모두 push/pop. 0-1 BFS (가중치 0 / 1 인 간선), 슬라이딩 윈도우 최소 / 최대 같은 문제에서 핵심.

push_front(x), push_back(x)
pop_front(), pop_back()

알고리즘

기본 큐 (원형 배열 구현)

class CircularQueue:
    data = array of size N
    head = 0
    tail = 0

    push(x):
        if full():
            error "queue full"
        data[tail] = x
        tail = (tail + 1) % N

    pop():
        if empty():
            error "queue empty"
        result = data[head]
        head = (head + 1) % N
        return result

    front():
        return data[head]

    empty():
        return head == tail

    full():
        return (tail + 1) % N == head

BFS (너비 우선 탐색)

bfs(start):
    queue = empty
    visited = set()
    queue.push(start)
    visited.add(start)
    while queue not empty:
        u = queue.pop()
        for v in neighbors(u):
            if v not in visited:
                visited.add(v)
                queue.push(v)

구현

// BFS 기본 (인접 리스트 그래프)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m, start; cin >> n >> m >> start;
  vector<vector<int>> adj(n + 1);
  for (int i = 0; i < m; i++) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  vector<int> dist(n + 1, -1);
  queue<int> q;
  q.push(start);
  dist[start] = 0;
  while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : adj[u]) {
          if (dist[v] == -1) {
              dist[v] = dist[u] + 1;
              q.push(v);
          }
      }
  }
  for (int i = 1; i <= n; i++)
      cout << dist[i] << (i == n ? "\n" : " ");
}

# BFS (collections.deque)
from collections import deque
import sys
input = sys.stdin.readline
​
n, m, start = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
  u, v = map(int, input().split())
  adj[u].append(v)
  adj[v].append(u)
​
dist = [-1] * (n + 1)
q = deque([start])
dist[start] = 0
while q:
  u = q.popleft()
  for v in adj[u]:
      if dist[v] == -1:
          dist[v] = dist[u] + 1
          q.append(v)
print(*dist[1:])

// BFS (ArrayDeque 사용)
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int start = Integer.parseInt(st.nextToken());
      List<Integer>[] adj = new ArrayList[n + 1];
      for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          adj[u].add(v);
          adj[v].add(u);
      }
      int[] dist = new int[n + 1];
      Arrays.fill(dist, -1);
      Queue<Integer> q = new ArrayDeque<>();
      q.add(start);
      dist[start] = 0;
      while (!q.isEmpty()) {
          int u = q.poll();
          for (int v : adj[u]) {
              if (dist[v] == -1) {
                  dist[v] = dist[u] + 1;
                  q.add(v);
              }
          }
      }
      for (int i = 1; i <= n; i++)
          System.out.print(dist[i] + (i == n ? "\n" : " "));
  }
}

5 5 1
1 2
1 3
2 4
3 4
4 5

0 1 1 2 3

원형 큐 예제 (수동 구현)

// 원형 큐 (배열 + head/tail 포인터)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int q; cin >> q;
  vector<int> data(100005);
  int head = 0, tail = 0;
  while (q--) {
      string cmd; cin >> cmd;
      if (cmd == "push") {
          int x; cin >> x;
          data[tail++] = x;
      } else if (cmd == "pop") {
          if (head == tail) cout << "-1\n";
          else cout << data[head++] << "\n";
      } else if (cmd == "front") {
          if (head == tail) cout << "-1\n";
          else cout << data[head] << "\n";
      } else if (cmd == "size") {
          cout << (tail - head) << "\n";
      } else if (cmd == "empty") {
          cout << (head == tail ? 1 : 0) << "\n";
      }
  }
}

# 원형 큐 (collections.deque 로 간단히)
from collections import deque
import sys
input = sys.stdin.readline
​
q_count = int(input())
q = deque()
out = []
for _ in range(q_count):
  cmd = input().split()
  if cmd[0] == "push":
      q.append(int(cmd[1]))
  elif cmd[0] == "pop":
      out.append(str(q.popleft()) if q else "-1")
  elif cmd[0] == "front":
      out.append(str(q[0]) if q else "-1")
  elif cmd[0] == "size":
      out.append(str(len(q)))
  elif cmd[0] == "empty":
      out.append("0" if q else "1")
print("\n".join(out))

7
push 1
push 2
front
pop
pop
pop
empty

1
1
2
-1
1

복잡도

변형 / 활용

함정

1. pop() 전 empty 체크

큐가 비었는데 pop 하면 런타임 에러.

if (!q.empty()) q.pop();

2. 배열 큐에서 인덱스 범위

원형 큐 구현 시 (tail + 1) % N == head 조건 (full) 과 head == tail (empty) 을 구분해야 합니다. 한 칸을 희생하거나, 별도 size 변수 관리.

3. Python list.pop(0) 은 O(N)

list.pop(0) 은 맨 앞 제거 + 뒤 원소 shift 로 O(N). 반드시 collections.deque 사용.

from collections import deque
q = deque()
q.append(x)    # push
q.popleft()    # pop O(1)

4. Java Queue.remove() vs poll()

remove() 는 빈 큐에 예외, poll() 은 null 반환. 안전하게 poll() 사용.

Integer val = q.poll();   // null if empty
if (val != null) { ... }

5. BFS 에서 방문 체크 시점

큐에 넣을 때 visited 마크해야 중복 방문 방지. pop 할 때 마크하면 같은 정점이 여러 번 큐에 들어갑니다.

if (!visited[v]) {
    visited[v] = true;   // 여기서 마크
    q.push(v);
}

BOJ 연습 문제

참고

• 스택 (LIFO)
• 너비 우선 탐색
• 양방향 큐 (0-1 BFS, 슬라이딩 윈도우)