[CS] 큐(Queue)란 - 구조와 활용 예시

큐 자료구조가 뭐고, 스택과 뭐가 다른지, 실제로 어디에 쓰이는지 자바 예시와 함께 정리했습니다.

---

 

큐란

한쪽 끝(뒤)에서 데이터를 넣고, 반대쪽 끝(앞)에서 데이터를 꺼내는 자료구조입니다. 가장 먼저 넣은 데이터가 가장 먼저 나온다는 뜻에서 FIFO(First In First Out) 구조라고 부릅니다. 놀이공원 줄서기를 떠올리면 됩니다. 먼저 줄 선 사람이 먼저 입장합니다.

기본 연산

• offer(또는 enqueue): 뒤쪽에 데이터를 추가
• poll(또는 dequeue): 앞쪽 데이터를 꺼내면서 제거
• peek: 앞쪽 데이터를 제거하지 않고 확인만

 

java

import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();

queue.offer(1);
queue.offer(2);
queue.offer(3);

System.out.println(queue.peek()); // 1 (맨 앞 확인, 제거 안 됨)
System.out.println(queue.poll()); // 1 (꺼내면서 제거)
System.out.println(queue.poll()); // 2
System.out.println(queue.poll()); // 3

1, 2, 3 순서로 넣으면 꺼낼 때도 1, 2, 3 순서로 나옵니다. 스택(LIFO)과 정반대로, 먼저 넣은 게 먼저 나오는 게 핵심입니다.

 

스택과 비교

스택(Stack)큐(Queue)

순서	LIFO (나중에 넣은 게 먼저)	FIFO (먼저 넣은 게 먼저)
비유	책 쌓기	줄서기
넣고 빼는 곳	같은 쪽(위)	다른 쪽(뒤에서 넣고 앞에서 뺌)

 

실제로 어디에 쓰이나

1) 작업 순서 관리

들어온 순서대로 처리해야 하는 작업(프린터 인쇄 대기열, 고객센터 상담 순번)을 큐에 쌓아두고 앞에서부터 하나씩 처리합니다.

 

2) 너비 우선 탐색(BFS)

java

public void bfs(int start, List<List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.size()];

    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int current = queue.poll();
        System.out.println(current);

        for (int next : graph.get(current)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next); // 다음에 방문할 노드를 뒤에 추가
            }
        }
    }
}

현재 노드와 가까운 노드부터 순서대로 방문해야 하는 BFS 알고리즘은 큐 없이는 구현하기 어렵습니다. 가까운 노드를 먼저 큐에 넣으면, 먼 노드보다 먼저 꺼내져서 처리되기 때문입니다.

 

3) 비동기 작업 처리

들어오는 요청을 바로 처리하지 못할 때, 일단 큐에 쌓아두고 순서대로 하나씩 처리합니다. Kafka나 RabbitMQ 같은 메시지 큐 시스템도 이 FIFO 개념을 기반으로 대량의 이벤트를 순서대로(또는 파티션 단위로) 처리합니다.

 

마무리

큐는 "먼저 들어온 게 먼저 나가는 FIFO 구조"라는 규칙 하나로 요약됩니다. 이 단순한 규칙이 줄서기 같은 순서 보장이 필요한 상황이나, BFS처럼 가까운 것부터 차례로 처리해야 하는 알고리즘에 자연스럽게 들어맞습니다.