[알고리즘] 16. 큐(Queue)

[알고리즘] 16. 큐(Queue)

지난 글에서는 스택(Stack)에 대해 정리했습니다. 이번 글에서는 스택과 함께 알고리즘 문제에서 자주 등장하는 자료구조인 큐(Queue)에 대해 알아보겠습니다.

큐는 데이터를 먼저 넣은 순서대로 꺼내는 자료구조입니다. 대기열, 순서 처리, BFS, 작업 예약, 프린터 문제 같은 곳에서 자주 사용됩니다.

큐는 먼저 들어온 데이터가 먼저 나가는 선입선출 구조입니다.

---

1. 큐란?

큐는 데이터를 줄 세우듯이 관리하는 자료구조입니다. 가장 쉽게 떠올릴 수 있는 예시는 은행 창구나 편의점 계산대의 대기줄입니다.

먼저 줄을 선 사람이 먼저 서비스를 받고, 나중에 온 사람은 뒤에 서서 기다립니다. 큐도 이와 같은 방식으로 동작합니다.

1번 손님이 줄을 선다.
2번 손님이 줄을 선다.
3번 손님이 줄을 선다.

처리 순서: 1번 → 2번 → 3번

스택은 나중에 들어온 값이 먼저 나왔지만, 큐는 먼저 들어온 값이 먼저 나옵니다.

큐는 먼저 들어간 값을 가장 먼저 꺼내는 구조입니다.

---

2. 선입선출 구조

큐의 가장 중요한 특징은 선입선출입니다. 영어로는 FIFO라고 부릅니다.

용어	의미
선입선출	먼저 들어온 값이 먼저 나감
FIFO	First In, First Out

예를 들어 큐에 10, 20, 30을 순서대로 넣었다고 생각해보겠습니다.

add 10
add 20
add 30

이제 값을 꺼내면 가장 먼저 들어간 10부터 나옵니다.

poll → 10
poll → 20
poll → 30

이 흐름이 큐의 핵심입니다.

---

3. 큐의 기본 연산

큐에서 자주 사용하는 기본 연산은 다음과 같습니다.

연산	의미
add	큐에 값을 넣는다.
offer	큐에 값을 넣는다.
poll	큐의 맨 앞 값을 꺼낸다.
peek	큐의 맨 앞 값을 확인만 한다.
isEmpty	큐가 비어 있는지 확인한다.
size	큐에 들어 있는 값의 개수를 확인한다.

알고리즘 문제에서는 보통 값을 넣을 때 offer() 또는 add()를 사용하고, 값을 꺼낼 때는 poll()을 자주 사용합니다.

---

4. Java에서 Queue 사용하기

Java에서 Queue는 인터페이스입니다. 그래서 Queue를 바로 생성하지 않고, 보통 LinkedList를 이용해서 만듭니다.

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

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

queue.offer(10);
queue.offer(20);
queue.offer(30);

System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());

출력 결과는 다음과 같습니다.

10
20
30

10, 20, 30 순서로 넣었고, 꺼낼 때도 10, 20, 30 순서로 나옵니다. 이것이 선입선출 구조입니다.

Java에서 큐를 사용할 때는 Queue<타입> queue = new LinkedList<>(); 형태를 자주 사용합니다.

---

5. offer와 poll

큐에서 가장 기본이 되는 연산은 값을 넣는 offer와 값을 꺼내는 poll입니다.

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

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

int value = queue.poll();

System.out.println(value);

출력 결과는 다음과 같습니다.

1

가장 먼저 넣은 값이 1이므로 poll을 하면 1이 먼저 나옵니다.

offer는 넣기, poll은 꺼내기입니다.

---

6. peek으로 맨 앞 값 확인하기

poll은 값을 꺼내면서 큐에서 제거합니다. 반면 peek은 값을 제거하지 않고 맨 앞에 있는 값만 확인합니다.

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

queue.offer(10);
queue.offer(20);
queue.offer(30);

System.out.println(queue.peek());
System.out.println(queue.peek());
System.out.println(queue.size());

출력 결과는 다음과 같습니다.

10
10
3

peek은 값을 확인만 하기 때문에 여러 번 호출해도 값이 제거되지 않습니다. 큐의 크기도 그대로 3입니다.

---

7. isEmpty로 비어 있는지 확인하기

큐에서 값을 꺼내기 전에는 큐가 비어 있는지 확인하는 것이 안전합니다. 비어 있는 큐에서 poll을 호출하면 null이 반환될 수 있습니다.

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

if (!queue.isEmpty()) {
    System.out.println(queue.poll());
} else {
    System.out.println("큐가 비어 있습니다.");
}

출력 결과는 다음과 같습니다.

큐가 비어 있습니다.

큐 문제에서는 반복문 안에서 poll을 자주 사용합니다. 그래서 조건식에 !queue.isEmpty()가 자주 등장합니다.

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

    System.out.println(current);
}

---

8. 큐의 동작 흐름 예시

큐에 1, 2, 3을 넣고 하나씩 꺼내는 흐름을 표로 보면 다음과 같습니다.

동작	반환값	큐 상태
offer(1)	-	1
offer(2)	-	1, 2
offer(3)	-	1, 2, 3
poll()	1	2, 3
poll()	2	3
poll()	3	비어 있음

항상 먼저 들어간 값부터 빠져나가는 것을 확인할 수 있습니다.

---

9. 큐로 대기열 처리하기

큐는 대기열을 처리할 때 가장 자연스럽게 사용할 수 있습니다. 예를 들어 손님이 들어온 순서대로 처리하는 상황을 생각해보겠습니다.

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

queue.offer("손님1");
queue.offer("손님2");
queue.offer("손님3");

while (!queue.isEmpty()) {
    String customer = queue.poll();
    System.out.println(customer + " 처리 완료");
}

출력 결과는 다음과 같습니다.

손님1 처리 완료
손님2 처리 완료
손님3 처리 완료

먼저 들어온 손님부터 순서대로 처리됩니다. 이처럼 순서를 지켜야 하는 문제에서 큐가 잘 어울립니다.

---

10. 큐와 BFS의 관계

큐는 그래프 탐색 알고리즘인 BFS에서 매우 중요하게 사용됩니다. BFS는 가까운 곳부터 차례대로 탐색하는 방식입니다.

가까운 노드부터 순서대로 처리해야 하므로, 먼저 발견한 노드를 먼저 꺼내는 큐가 필요합니다.

1번 노드 방문
1번과 연결된 2번, 3번을 큐에 넣음
큐에서 2번을 꺼내 방문
큐에서 3번을 꺼내 방문

이처럼 BFS는 큐를 이용해 방문 순서를 관리합니다.

BFS는 큐를 사용해서 먼저 발견한 노드부터 차례대로 탐색합니다.

---

11. 간단한 BFS 흐름 보기

아래는 연결 정보를 직접 배열로 표현하지 않고, 큐의 흐름만 간단히 보여주는 예시입니다.

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

queue.offer(1);

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

    System.out.println(current + "번 방문");

    if (current == 1) {
        queue.offer(2);
        queue.offer(3);
    }
}

출력 결과는 다음과 같습니다.

1번 방문
2번 방문
3번 방문

1번을 먼저 방문하고, 1번에서 발견한 2번과 3번이 차례대로 방문됩니다. 실제 BFS에서는 여기에 그래프 연결 정보와 방문 배열이 함께 사용됩니다.

---

12. 큐가 사용되는 대표 상황

큐는 아래와 같은 상황에서 자주 사용됩니다.

상황	이유
대기열 처리	먼저 들어온 순서대로 처리해야 함
BFS	먼저 발견한 노드부터 탐색해야 함
프린터 작업	작업 요청 순서를 관리해야 함
작업 스케줄링	순서대로 처리할 작업을 관리해야 함
시뮬레이션	순서에 따라 상태가 변하는 문제에 적합

문제를 보고 “먼저 들어온 것부터 처리해야 한다”는 느낌이 들면 큐를 떠올리면 좋습니다.

---

13. 큐와 스택 비교하기

큐와 스택은 둘 다 데이터를 넣고 빼는 자료구조입니다. 하지만 꺼내는 순서가 완전히 다릅니다.

구분	스택	큐
구조	후입선출	선입선출
영어 표현	LIFO	FIFO
먼저 나가는 값	나중에 들어온 값	먼저 들어온 값
대표 상황	괄호 검사, 되돌리기, DFS	대기열, BFS, 순서 처리

스택은 최근 값을 먼저 처리할 때, 큐는 오래 기다린 값을 먼저 처리할 때 사용한다고 생각하면 이해하기 쉽습니다.

스택은 마지막부터, 큐는 처음부터 처리합니다.

---

14. 큐의 시간복잡도

큐의 기본 연산은 대부분 빠르게 처리됩니다.

연산	시간복잡도
offer	O(1)
poll	O(1)
peek	O(1)
isEmpty	O(1)
size	O(1)

큐에 값을 넣거나 꺼내는 작업은 한 번에 처리됩니다. 데이터 전체를 한 번씩 큐에 넣고 꺼낸다면 전체 시간복잡도는 보통 O(N)입니다.

큐 자체의 기본 연산은 O(1)이지만, 전체 문제에서는 몇 개의 데이터를 처리하는지가 중요합니다.

---

15. 큐에서 자주 하는 실수

큐 문제를 풀 때는 아래 실수를 조심해야 합니다.

• 큐와 스택의 꺼내는 순서를 헷갈리는 경우
• 비어 있는 큐에서 poll한 값을 바로 사용하는 경우
• BFS에서 방문 처리를 하지 않아 같은 노드를 반복 방문하는 경우
• offer와 poll의 순서를 잘못 작성하는 경우
• 큐를 사용해야 하는 문제를 배열 반복문만으로 억지로 처리하는 경우
• 큐에 넣는 시점과 방문 처리 시점을 헷갈리는 경우

특히 BFS에서는 방문 배열이 매우 중요합니다. 방문 처리를 하지 않으면 같은 노드가 계속 큐에 들어가 무한 반복처럼 동작할 수 있습니다.

큐 문제에서는 “무엇을 언제 넣고, 언제 꺼내는지”를 정확히 정해야 합니다.

---

16. 정리

이번 글에서는 큐에 대해 정리했습니다.

• 큐는 먼저 들어온 값이 먼저 나가는 선입선출 구조이다.
• 큐의 대표 연산은 offer, poll, peek, isEmpty, size이다.
• offer는 값을 넣고, poll은 맨 앞 값을 꺼낸다.
• peek은 맨 앞 값을 제거하지 않고 확인만 한다.
• Java에서는 Queue 인터페이스와 LinkedList를 함께 자주 사용한다.
• 대기열 처리, 프린터 작업, 시뮬레이션, BFS에서 큐가 자주 사용된다.
• 큐의 기본 연산은 대부분 O(1)이다.
• 스택은 후입선출, 큐는 선입선출이라는 차이가 있다.

큐는 알고리즘에서 순서를 관리할 때 매우 중요한 자료구조입니다. 문제를 보고 먼저 들어온 값부터 차례대로 처리해야 한다면 큐를 떠올리면 됩니다.

큐의 핵심은 “먼저 들어온 값이 가장 먼저 나온다”는 흐름을 이해하는 것입니다.

---

다음 글 예고

다음 글에서는 덱(Deque)에 대해 알아보겠습니다.

덱의 개념, 양쪽 삽입과 삭제, ArrayDeque 사용법, 스택과 큐를 모두 표현할 수 있는 구조를 예제로 정리해보겠습니다.