1. 큐의 정의와 특징
큐는 먼저 들어온 데이터가 가장 먼저 나가는 (FIFO, First-In First-Out) 선형 자료구조이다. 매표소 앞에 줄을 서서 순서대로 서비스를 받는 상황을 떠올리면 이해가 쉽다. 큐에는 두 가지 핵심 규칙이 존재한다.
- 삽입 (enqueue) : 새로운 원소를 항상 ‘뒤(rear)’에 붙인다.
- 삭제 (dequeue) : 데이터를 꺼낼 때는 ‘앞(front)’에서 꺼낸다.
이 규칙으로 인해 큐는 다음과 같은 특징을 갖는다.
- 순서 제어를 코드가 아닌 구조 자체가 담당한다.
- 작업 요청을 순차적으로 처리하거나, 데이터 흐름을 완충(버퍼)할 때 유용하다.
- 추가·삭제가 상수 시간에 끝난다. 구현을 배열로 하든 연결 리스트로 하든, enqueue와 dequeue 모두 O(1)이다.
큐는 단순하지만, 이 FIFO 특성 하나만으로도 프로세스 스케줄링, 너비 우선 탐색 (BFS), 네트워크 패킷 버퍼링 등 다양한 문제를 깔끔하게 해결한다.
2. 큐의 기본 연산
큐가 제공하는 핵심 연산은 네 가지로 요약된다.
| 연산 | 설명 | 반환값 | 시간 복잡도 |
| enqueue(x) | 요소 x 를 뒤(rear)에 추가한다. | 없음 | O(1) |
| dequeue() | 앞(front)에 있는 요소를 제거하고 반환한다. 큐가 비어 있으면 언더플로우 예외를 발생시키거나 특별한 값을 반환한다. | 제거된 요소 | O(1) |
| peek()/front() | 삭제하지 않고 front에 있는 요소를 조회한다. | 조회한 요소 | O(1) |
| isEmpty() / size() | 큐가 비어 있는지 또는 현재 요소 개수를 확인한다. | 불린 / 정수 | O(1) |
구현체마다 rear·front 인덱스를 관리하는 방식은 다르지만, 공통적으로 “읽기는 front, 쓰기는 rear”라는 규칙만 지키면 된다. 이 덕분에 큐는 고정된 공간(배열)에서도 두 포인터만 이동시켜 마치 원형 버퍼처럼 재활용할 수 있고, 연결 리스트 기반이면 노드 추가·삭제로 간단히 동작한다.
3. 큐의 내부 구현 방식
큐는 구현·용도에 따라 기본 선형 큐, 원형 큐, 우선순위 큐 세 갈래로 나뉜다. 세 방식은 모두 “앞에서 꺼내고 뒤에 넣는다”라는 흐름은 같지만, 내부 구조와 성능 특성이 뚜렷이 다르다.
| 구분 | 기본 큐(Queue) | 원형 큐(Circular Queue) | 우선순위 큐(Priority Queue) |
| 메모리 배치 | 배열 or 연결 리스트 한 줄로 배치한다. front·rear 포인터가 양쪽 끝을 가리킨다. | 배열을 원형 버퍼처럼 돌려 쓴다. 인덱스가 끝에 닿으면 0으로 래핑한다. | 보통 배열 기반 이진 힙을 사용한다. 노드 간 완전이진트리 형태를 인덱스로 표현한다. |
| front / rear 이동 | enqueue 시 rear++ , dequeue 시 front++ (연결 리스트면 head·tail 링크 교체) | index = (index + 1) % capacity 로 전진한다. | 삽입: 힙의 마지막에 넣고 위로 sift-up.삭제: 루트 제거 후 마지막 노드를 루트로 옮기고 sift-down. |
| 용량 문제 | 고정 배열이면 오버플로가 난다.동적 배열은 복사·재할당이 필요하다. | 배열 크기를 꽉 채워도 빈 칸이 없다. 단, “가득 참 = front == (rear+1)” 규칙 때문에 한 칸을 비워 두거나 size 변수를 추가로 관리해야 한다. | 힙 배열이 꽉 차면 2배 확장한다. 연속 복사 비용이 든다. |
| 메모리 효율 | 배열-선형은 빈 칸이 생길 수 있다.연결 리스트는 노드당 포인터 오버헤드가 있다. | 배치가 연속적이고 빈 칸을 남기지 않는다. | 값만 저장한다. 힙 특성상 메모리 낭비가 거의 없다. |
| 캐시 친화성 | 배열 구현은 우수, 리스트는 낮다. | 배열·연속 메모리라 캐시 효율이 가장 높다. | 힙도 배열이라 캐시 적중률은 좋다. |
| 구현 난이도 | 배열은 간단, 리스트는 GC 의존.포인터 두 개만 관리하면 된다. | front·rear 래핑, “가득 참 vs 빈 큐” 판별 로직이 추가된다. | sift-up / sift-down 알고리즘이 필요하다. 비교적 복잡하다. |
| 특징 요약 | - 구조가 단순하다.- 연결 리스트면 크기 제약이 없다. | - 고정 크기 환경에서 메모리 재활용이 뛰어나다.- 실시간 스트림 버퍼에 최적. | - FIFO 대신 “우선순위 높은 것부터” 꺼낸다.- 삽입·삭제 모두 O(log n). |
선택 가이드
- 입·출력 순서만 중요하고 크기 한도가 명확하지 않다면 연결 리스트 기본 큐가 단순·안전하다.
- 고정 크기 버퍼에서 끊임없이 데이터가 돌고, 복사 오버헤드도 피하고 싶다면 원형 큐가 최적이다.
- “먼저 온 순서”보다 우선순위가 더 중요하면 힙 기반 우선순위 큐를 쓴다. 작업 스케줄러·다익스트라 등이 전형적 예다.
4. 큐 사용 시 주의점
- 오버플로·언더플로를 반드시 체크한다
고정 길이 배열 큐(특히 원형 큐)는 enqueue 전에 “가득 찼는지”를 확인하지 않으면 오버플로가 발생한다. 반대로 비어 있는데 dequeue · peek 을 호출하면 언더플로가 난다. isFull · isEmpty 검사를 습관화하고, 원형 큐라면 front == (rear + 1) % capacity 규칙을 정확히 구현해야 한다. - 동적 배열 큐는 리사이즈 비용이 숨겨져 있다
ArrayDeque , ArrayList 기반 큐처럼 내부적으로 배열을 확장하는 구현은 용량이 꽉 차면 전체 요소 복사를 수행한다. 단일 enqueue가 O(n)으로 튀는 순간이 존재하므로, 대량 데이터를 다룰 때는 초기 용량을 넉넉히 잡거나 연결 리스트 큐를 고려하자. - 포인터(인덱스) 관리 오류가 빈번하다
원형 큐는 front·rear가 배열 끝을 넘어가면 0으로 래핑되기 때문에, 증가 식을 index = (index + 1) % capacity 로 고정하고 “가득 참”과 “비어 있음” 판별 로직을 명확히 분리해야 한다. 두 포인터를 잘못 업데이트하면 요소가 소실되거나 중복되는 버그가 생긴다. - 공유 큐는 스레드 안전성을 확보한다
다중 스레드가 하나의 큐 인스턴스를 동시에 조작하면 레이스 컨디션이 발생한다. 간단한 해결책은 synchronized 블록으로 enqueue / dequeue 를 감싸는 것이고, 고성능이 필요할 때는 ConcurrentLinkedQueue · LinkedBlockingQueue 등 스레드 안전한 구현을 사용한다. - 디버깅용 상태 출력 메서드를 마련한다
큐 버그는 현재 front·rear 위치와 저장된 요소를 확인하면 원인을 빠르게 찾을 수 있다. 개발 단계에서 printQueue 같은 보조 메서드를 두면 디버깅 효율이 크게 향상된다.
실전 개념 점검 1. 배열 기반 Queue·CircularQueue 구현
CustomQueue
더보기
public class CustomQueue {
private static final int DEFAULT_SIZE = 10;
private int[] arr;
private int front, rear, size;
// 기본 생성자 (기본 크기 DEFAULT_SIZE 사용)
public CustomQueue() {
this(DEFAULT_SIZE);
}
// 사용자 지정 크기 생성자
public CustomQueue(int capacity) {
arr = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == arr.length;
}
public void enqueue(int value) {
if (isFull()) {
System.out.println("큐가 가득 찼습니다.");
return;
}
arr[++rear] = value;
size++;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("큐가 비었습니다.");
return -1;
}
int value = arr[front];
front++;
size--;
return value;
}
public int peek() {
return isEmpty() ? -1 : arr[front];
}
public void printQueue() {
StringBuffer sb = new StringBuffer();
for (int i = front;i <= rear;i++)
sb.append(arr[i]).append(" ");
System.out.println(sb.toString());
}
public static void main(String[] args) {
CustomQueue queue = new CustomQueue();
queue.enqueue(1);
queue.enqueue(2);
queue.printQueue();
System.out.println(queue.dequeue()); // 1
System.out.println(queue.peek()); // 2
}
}
CustomCircleQueue
더보기
public class CustomCircleQueue {
private static final int DEFAULT_SIZE = 10;
private int[] arr;
private int front, rear, size, capacity;
// 기본 생성자 (기본 크기 DEFAULT_SIZE 사용)
public CustomCircleQueue() {
this(DEFAULT_SIZE);
}
// 사용자 지정 크기 생성자
public CustomCircleQueue(int capacity) {
this.capacity = capacity;
arr = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public void enqueue(int value) {
if (isFull()) {
System.out.println("큐가 가득 찼습니다.");
return;
}
rear = (rear + 1) % capacity;
arr[rear] = value;
size++;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("큐가 비었습니다.");
return -1;
}
int value = arr[front];
front = (front + 1) % capacity;
size--;
return value;
}
public int peek() {
return isEmpty() ? -1 : arr[front];
}
public void printQueue() {
if (isEmpty()) {
System.out.println("Circular Queue is empty");
return;
}
StringBuffer sb = new StringBuffer();
int i = front;
// 큐가 순환 구조이므로 front부터 rear까지 순차적으로 출력
for (int j = 0; j < size; j++) {
sb.append(arr[i]).append(" ");
i = (i + 1) % capacity; // 큐에서 순환하기 위해 나머지 연산 사용
}
System.out.println(sb.toString());
}
public static void main(String[] args) {
CustomCircleQueue cQueue = new CustomCircleQueue();
cQueue.enqueue(1);
cQueue.enqueue(2);
cQueue.enqueue(3);
cQueue.printQueue(); // 출력: 1 2 3
System.out.println(cQueue.dequeue()); // 1
cQueue.enqueue(4);
cQueue.printQueue(); // 출력: 2 3 4
System.out.println(cQueue.peek()); // 2
}
}
배열 큐 두 가지를 직접 구현해 보았다. 첫 번째 CustomQueue 는 선형 배열을 그대로 사용한다. front 가 앞을 가리키고 rear 가 뒤를 가리키는데, 삭제가 일어날 때마다 front 만 증가하므로 삭제된 슬롯이 재사용되지 않는다. 따라서
- enqueue 가 계속되면 rear 는 끝까지 밀려 isFull 이 곧바로 true 가 된다.
- 공간을 다시 쓰려면 전체 배열을 복사하거나 인덱스를 리셋해야 한다.
이를 해결한 형태가 두 번째 CustomCircleQueue 이다. 원형 큐라 부르며 핵심은 rear = (rear + 1) % capacity , front = (front + 1) % capacity 로 인덱스를 순환시키는 것이다.
- front == (rear + 1) % capacity 일 때 가득 찬 것으로 간주한다.
- 삭제된 자리를 자연스럽게 재활용하므로 같은 크기에서도 저장 가능 요소가 늘어난다.
| 비교 항목 | 선형 배열 큐 | 원형 큐 |
| 공간 재활용 | 불가능하다. front 가 이동해도 빈 칸은 그대로 남는다. | 인덱스를 순환시켜 빈 칸을 바로 사용한다. |
| 포인터 업데이트 | rear++ , front++ | (rear+1)%n , (front+1)%n |
| 가득 참 판별 | rear == arr.length - 1 | size == capacity 또는 front == (rear+1)%capacity |
| 코드 복잡도 | 단순 | 경계 조건·모듈러 연산 주의 |
두 구현 모두 enqueue , dequeue , peek 연산은 O(1)이다. 실제 서비스용 버퍼처럼 고정된 메모리에서 무한히 돌려야 할 때는 원형 큐가 필수이며, 입력 크기를 명확히 알고 한 번만 소비한다면 선형 큐도 무리가 없다.
체크포인트
- 원형 큐에서도 “비어 있음”과 “가득 참”을 구분하려면 size 변수를 유지하거나 한 칸 비우기 규칙을 택해야 한다.
- 두 구현 모두 스레드 환경에서는 enqueue · dequeue 를 동기화해야 레이스 컨디션을 피한다.
실전 개념 점검 2. LinkedList로 Queue 구현
연결 리스트 기반 큐는 노드 객체를 사슬처럼 연결하고, ⟨⟨head⟩⟩·⟨⟨tail⟩⟩ 두 참조만 관리한다. 삽입은 ⟨⟨tail⟩⟩ 뒤에 노드를 붙이고, 삭제는 ⟨⟨head⟩⟩ 노드를 떼어 내므로 모든 연산이 O(1) 이다. 배열 큐와 달리 크기 한도가 없어, 입력량을 예측하기 어려운 상황에 안전하다.
import java.util.LinkedList;
public class QueueWithLinkedList {
private LinkedList<Integer> list = new LinkedList<>();
public void enqueue(int value) { // 뒤에 추가
list.addLast(value);
}
public int dequeue() { // 앞에서 제거
if (list.isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
return list.removeFirst();
}
public int peek() { // 앞 요소 조회
return list.isEmpty() ? -1 : list.getFirst();
}
public boolean isEmpty() { // 비어 있는가
return list.isEmpty();
}
}
동작 흐름 요약
- 삽입(enqueue)
새 노드를 만들어 ⟨⟨tail⟩⟩(LinkedList의 ⟨⟨addLast⟩⟩) 뒤에 연결 → ⟨⟨tail⟩⟩를 새 노드로 업데이트. - 삭제(dequeue)
⟨⟨head⟩⟩(⟨⟨removeFirst⟩⟩) 노드를 떼어 내고 다음 노드로 이동. 큐가 비면 ⟨⟨head⟩⟩·⟨⟨tail⟩⟩ 둘 다 null. - 조회(peek)
⟨⟨head⟩⟩ 노드의 값을 반환하되 구조 변경은 없다.
장·단점 비교
| 항목 | 연결 리스트 큐 | 배열·원형 큐 |
| 최대 크기 | 이론상 무제한 (힙 메모리 한도) | 배열 길이로 고정 |
| 메모리 오버헤드 | 노드마다 포인터 2개(더블 링크) | 값만 저장(고정 크기) |
| 캐시 효율 | 노드가 흩어져 있어 낮음 | 연속 메모리로 높음 |
| 리사이즈 비용 | 없음 | 동적 확장 시 전체 복사 |
| 적합한 상황 | 입력량 변동이 크거나 알 수 없음 | 고정 버퍼, 캐시 친화 환경 |
Tip!
대량 실시간 스트림처럼 캐시 적중률이 중요한 경우엔 배열 · 원형 큐를,
데이터 폭주·급감이 교차하는 작업 큐라면 연결 리스트 큐를 선택하라.
실전 개념 점검 3. 스택 두 개로 큐 구현
스택은 LIFO 구조지만, 2개를 적절히 교대하면 FIFO 큐로 동작하게 할 수 있다. 핵심은 입력 전용 스택 ⟨⟨saveStack⟩⟩과 출력 전용 스택 ⟨⟨likeQueue⟩⟩ 두 개를 준비해 필요할 때만 데이터를 뒤집는 것이다.
import java.util.Stack;
public class QueueWithTwoStacks {
private Stack<Integer> saveStack = new Stack<>(); // 입력 배치
private Stack<Integer> likeQueue = new Stack<>(); // 출력 배치
public void enqueue(int value) { // 삽입
saveStack.push(value);
}
public int dequeue() { // 삭제
if (likeQueue.isEmpty() && !move()) return -1;
return likeQueue.pop();
}
public int peek() { // 조회
if (likeQueue.isEmpty() && !move()) return -1;
return likeQueue.peek();
}
private boolean move() { // save → likeQueue 뒤집기
if (saveStack.isEmpty()) {
System.out.println("큐가 비어있습니다.");
return false;
}
while (!saveStack.isEmpty()) {
likeQueue.push(saveStack.pop());
}
return true;
}
public boolean isEmpty() {
return saveStack.isEmpty() && likeQueue.isEmpty();
}
}
작동 원리
- 삽입(⟨⟨enqueue⟩⟩)
새 요소는 항상 ⟨⟨saveStack⟩⟩에 push한다. - 삭제·조회(⟨⟨dequeue⟩⟩ / ⟨⟨peek⟩⟩)
⟨⟨likeQueue⟩⟩가 비어 있으면 ⟨⟨move()⟩⟩로 ⟨⟨saveStack⟩⟩의 모든 요소를 pop→push 하며 역순 이동한다. 그러면 가장 먼저 들어온 값이 ⟨⟨likeQueue⟩⟩의 top으로 올라와 FIFO 질서를 복원한다. - 암묵적 캐싱
한 번 뒤집힌 데이터는 ⟨⟨likeQueue⟩⟩가 바닥날 때까지 그대로 사용된다. 그래서 각 요소는 최대 두 번(save→likeQueue)만 이동하고, 암묵적 원형 큐처럼 동작한다.
'Java > 알고리즘(코테)' 카테고리의 다른 글
| Selection Sort (선택 정렬) (0) | 2025.05.06 |
|---|---|
| Bubble Sort (버블 정렬) (0) | 2025.05.05 |
| Stack (스택) (0) | 2025.04.30 |
| List(리스트) (0) | 2025.04.29 |
| Array(배열) (0) | 2025.04.28 |