데이터 처리의 순서가 중요한 상황에서 스택(Stack)과 함께 가장 기본적이면서도 중요한 자료구조 중 하나다 바로 큐(Queue)이다. 큐는 ‘선입선출(First In First Out, FIFO)’이라는 원칙을 따르며, 이는 가장 먼저 삽입된(Enqueue) 데이터가 가장 먼저 제거되는(Dequeue)구조를 의미한다. 일상생활에서 ‘줄 서기’와 같다
큐의 기본 개념과 원리
큐의 작동 방식을 가장 잘 보여주는 예시를 바로 마트 계산대 줄이다. 손님들은 먼저 온 순서대로 줄을 서고, 계산대에서는 줄의 가장 앞에 있는 손님부터 계산을 시작한다. 이처럼 먼저 줄을 선 손님이 먼저 계산을 하는 원칙이 바로 큐의 핵심이다
<- DEQUEUE (삭제)
FRONT REAR
+-----+-----+-----+-----+
| A | B | C | D |
+-----+-----+-----+-----+
-> ENQUEUE (삽입)
- FRONT (왼쪽): 가장 먼저 들어온 데이터 (A) - 삭제 위치
- REAR (오른쪽): 가장 나중에 들어온 데이터 (D) - 삽입 위치
큐는 컴퓨터 과학 분야에서도 폭넓게 활용된다
- 운영체제의 FIFO 스케줄링: 운영체제는 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고, CPU가 이 큐에서 순서대로 작업을 꺼내 처리한다
- 프린터 대기열: 여러 사용자가 프린터로 문서를 보낼 때, 먼저 보낸 문서부터 인쇄되기 위해 큐에 쌓인다
- 네트워크 트래픽 관리: 라우터나 스위치 같은 네트워크 장비에서 데이터 패킷을 처리할 때도 큐를 사용하여 순서를 관리한다
- 맛집 대기줄, 놀이공원 놀이기구 줄: 일상생활에서 질서 유지를 위해 서는 대부분의 줄은 큐의 특성을 가진다
스택과 마찬가지로 큐도 다음 네 가지 주요 연산을 가진다
- enqueue: 큐의 뒤(rear)에 데이터를 삽입(추가)한다
- dequeue: 큐의 앞(front)에 있는 데이터를 제거하고 반환한다
- front: 큐의 앞(front)에 있는 데이터를 제거하지 않고 참조(확인)한다
- isEmpty: 큐가 비어있는지 여부를 확인한다
연결 리스트를 이용한 큐 구현
큐는 배열이나 연결 리스트 등 다양한 자료구조로 구현할 수 있다. 여기서는 이중 연결 리스트(Doubly Linked List)를 활용한 구현 아이디어를 살펴본다.
큐의 선입선출(FIFO) 원칙을 지키려면, 데이터 삽입과 제거가 양쪽 끝에서 이루어져야 한다. 예를 들어 데이터를 head 쪽으로 삽입하고, tail 쪽에서 제거하는 방식이 일반적이다
단방향 연결 리스트의 한계점
만약 단방향 연결 리스트로 큐를 구현한다고 가정하고, head로 삽입하고 tail에서 제거한다면 문제가 발생한다. head로 삽입하는 것은 쉽지만, tail을 제거한 후에는 새로운 tail (이전 tail의 이전 노드)을 찾아야 한다. 단방향 리스트에서는 head부터 O(N)의 시간으로 순회해야만 tail의 이전 노드를 찾을 수 있어 비효율적이다
해결책: 이중 연결 리스트 사용
이러한 문제를 해결하기 위해 이중 연결 리스트를 사용한다. 이중 연결 리스트는 각 노드가 다음 노드(Next)뿐만 아니라 이전 노드(Prev)도 가리키는 구조이다
← DEQUEUE ENQUEUE →
+----+------+------+ +----+------+------+ +----+------+------+
|null| A(1) | Next |<---->|Prev| B(2) | Next |<---->|Prev| C(3) |null |
+----+------+------+ +----+------+------+ +----+------+------+
↑ ↑
HEAD TAIL
(FRONT) (REAR)
이중 연결 리스트에서는 head와 tail 포인터를 모두 유지하며, tail.prev를 통해 tail의 이전 노드에 O(1)으로 접근할 수 있다. 큐의 enqueue와 dequeue 연산을 모두 O(1)의 시간 복잡도로 구현할 수 있다
이중 연결 리스트를 이용한 큐의 동작
enqueue 연산
데이터를 삽입할 때, 이중 연결 리스트의 head (가장 앞)에 새로운 노드를 추가한다
- enqueue(1) -> [1] (head=1, tail=1)
- enqueue(2) -> [2, 1] (head=2, tail=1)
- enqueue(3) -> [3, 2, 1] (head=3, tail=1)
dequeue 연산
데이터를 제거할 때, 이중 연결 리스트의 tail (가장 뒤)에 있는 노드를 제거한다
- dequeue() -> 1이 제거 된다. 리스트는 [3, 2]가 되고, 2가 새로운 tail이 된다
- dequeue() -> 2가 제거된다. 리스트는 [3]이 되고, 3이 새로운 tail이 된다
Java를 이용한 큐 구현
DoublyLinkedList (이중 연결 리스트)
이중 연결 리스트는 head와 tail을 모두 관리하며, prev 포인터를 사용하여 효율적인 삽입/삭제를 가능하게 한다
Queue
DoublyLinkedList를 사용하여 큐의 기능을 구현한다
/**
* 이중 연결 리스트를 이용한 큐(Queue) 구현
*
* 큐의 FIFO(First In First Out) 원칙을 따른다
* - enqueue: rear(tail)에 데이터 삽입
* - dequeue: front(head)에서 데이터 제거
*
* 리스트와 큐의 매핑
* - 큐의 FRONT (삭제) = 리스트의 HEAD (인덱스 0)
* - 큐의 REAR (삽입) = 리스트의 TAIL (마지막)
*
* 리스트 구조: [HEAD=oldest] → ... → [TAIL=newest]
* 큐 관점: [FRONT] → ... → [REAR]
*
* 모든 연산의 시간 복잡도: O(1)
*/
public class Queue<T> {
private DoublyLinkedList<T> list;
public Queue() {
this.list = new DoublyLinkedList<>();
}
/**
* 큐의 뒤(rear)에 데이터를 삽입한다
*
* 구현 방식:
* - 이중 연결 리스트의 tail(마지막)에 데이터를 추가
* - insertLast() 메서드를 사용하여 O(1) 시간 복잡도로 삽입
*
* 동작 예시:
* enqueue(1) → [1] (head=1, tail=1)
* enqueue(2) → [1, 2] (head=1, tail=2)
* enqueue(3) → [1, 2, 3] (head=1, tail=3)
*
* @param data 삽입할 데이터
*/
public void enqueue(T data) {
// 큐의 rear(뒤)는 리스트의 tail(마지막)에 해당
list.insertLast(data);
System.out.println(data + "를 큐에 ENQUEUE 했습니다.");
}
/**
* 큐의 앞(front)에 있는 데이터를 제거하고 반환한다
*
* 구현 방식:
* - 이중 연결 리스트의 head(첫 번째)에 있는 데이터를 제거
* - deleteFirst() 메서드를 사용하여 O(1) 시간 복잡도로 삭제
* - 큐가 비어있으면 null을 반환
*
* 동작 예시:
* [1, 2, 3] → dequeue() → 1 반환, 큐는 [2, 3]
* [2, 3] → dequeue() → 2 반환, 큐는 [3]
* [3] → dequeue() → 3 반환, 큐는 []
* [] → dequeue() → null 반환
*
* @return 제거된 노드 (데이터 포함), 큐가 비어있으면 null
*/
public Node<T> dequeue() {
try {
// 큐의 front(앞)는 리스트의 head(첫 번째)에 해당
Node<T> deletedNode = list.deleteFirst();
System.out.println(deletedNode.getData() + "를 큐에서 DEQUEUE 했습니다.");
return deletedNode;
} catch (IndexOutOfBoundsException e) {
System.out.println("큐가 비어있어 DEQUEUE 할 데이터가 없습니다. (null 반환)");
return null;
}
}
/**
* 큐의 앞(front)에 있는 데이터를 제거하지 않고 참조만 한다
*
* 구현 방식:
* - 이중 연결 리스트의 head(첫 번째) 노드를 반환
* - 데이터를 제거하지 않고 읽기만 수행
* - 큐가 비어있으면 null을 반환
*
* @return 가장 앞에 있는 노드 (데이터 포함), 큐가 비어있으면 null
*/
public Node<T> front() {
if (isEmpty()) {
System.out.println("큐가 비어있어 FRONT 할 데이터가 없습니다. (null 반환)");
return null;
}
// 큐의 front(앞)는 리스트의 head(첫 번째)에 해당
return list.getHead();
}
/**
* 큐가 비어있는지 여부를 확인한다
*
* @return 큐가 비어있으면 true, 그렇지 않으면 false
*/
public boolean isEmpty() {
return list.getSize() == 0;
}
/**
* 큐의 현재 크기를 반환한다
*
* @return 큐에 저장된 데이터의 개수
*/
public int size() {
return list.getSize();
}
/**
* 큐의 모든 요소를 출력한다
* 형식: [front] → data1, data2, data3, ... → [rear]
*/
public void printQueue() {
System.out.print("[FRONT] → ");
list.printAll();
System.out.println(" ← [REAR]");
}
}
QueueMain
/**
* Queue 클래스의 동작을 테스트하는 메인 클래스
*
* 테스트 시나리오
* 1. enqueue() 세 번 호출하여 데이터 삽입
* 2. front()로 가장 앞 데이터 확인 (제거하지 않음)
* 3. dequeue() 네 번 호출하여 모든 데이터 제거 (마지막은 빈 큐)
* 4. isEmpty()로 큐가 비어있는지 확인
*/
public class QueueMain {
public static void main(String[] args) {
Queue<Integer> queue = new Queue<>();
System.out.println("\n===== enqueue() 세 번 호출 =====");
queue.enqueue(1); // 큐: [1] (front=1, rear=1)
queue.enqueue(2); // 큐: [1, 2] (front=1, rear=2)
queue.enqueue(3); // 큐: [1, 2, 3] (front=1, rear=3)
System.out.println("\n--- 현재 큐 상태 ---");
queue.printQueue();
System.out.println("\n--- front() 호출 ---");
Node<Integer> frontNode = queue.front(); // 큐의 front는 1 (제거하지 않음)
if (frontNode != null) {
System.out.println("Front 데이터: " + frontNode.getData()); // 1
}
System.out.println("\n===== dequeue() 네 번 호출 =====");
Node<Integer> dequeuedNode;
dequeuedNode = queue.dequeue(); // 1 제거
if (dequeuedNode != null) {
System.out.println("→ 반환된 데이터: " + dequeuedNode.getData());
}
dequeuedNode = queue.dequeue(); // 2 제거
if (dequeuedNode != null) {
System.out.println("→ 반환된 데이터: " + dequeuedNode.getData());
}
dequeuedNode = queue.dequeue(); // 3 제거
if (dequeuedNode != null) {
System.out.println("→ 반환된 데이터: " + dequeuedNode.getData());
}
dequeuedNode = queue.dequeue(); // 큐가 비어있으므로 null 반환
if (dequeuedNode != null) {
System.out.println("→ 반환된 데이터: " + dequeuedNode.getData());
} else {
System.out.println("→ 반환된 데이터: null (큐가 비어있음)");
}
System.out.println("\n--- 큐가 비어있는지 확인 ---");
System.out.println("큐가 비어있는가? " + queue.isEmpty()); // true
System.out.println("큐의 크기: " + queue.size()); // 0
}
}
/*
실행 결과
===== enqueue() 세 번 호출 =====
1를 큐에 ENQUEUE 했습니다.
2를 큐에 ENQUEUE 했습니다.
3를 큐에 ENQUEUE 했습니다.
--- 현재 큐 상태 ---
[FRONT] → [1, 2, 3]
← [REAR]
--- front() 호출 ---
Front 데이터: 1
===== dequeue() 네 번 호출 =====
1를 큐에서 DEQUEUE 했습니다.
→ 반환된 데이터: 1
2를 큐에서 DEQUEUE 했습니다.
→ 반환된 데이터: 2
3를 큐에서 DEQUEUE 했습니다.
→ 반환된 데이터: 3
큐가 비어있어 DEQUEUE 할 데이터가 없습니다. (null 반환)
→ 반환된 데이터: null (큐가 비어있음)
--- 큐가 비어있는지 확인 ---
큐가 비어있는가? true
큐의 크기: 0
*/
큐는 선입선출이라는 직관적인 규칙 덕분에 운영체제의 스케줄링, 네트워크 데이터 처리, 이벤트 관리 등 다양한 분야에서 질서 있는 데이터 처리가 필요할 때 핵심적인 역할을 수행한다.