1. Queue 인터페이스: 전형적인 큐(FIFO)
프로그래밍에서도 일상과 마찬가지로, 단순히 요소 집합을 저장하는 것보다 처리 순서를 관리하는 일이 중요할 때가 많습니다. 슈퍼마켓의 줄을 떠올려 보세요. 앞에 선 사람이 먼저 처리됩니다. 이것이 FIFO — “먼저 들어온 것이 먼저 나간다” 원리입니다. 반대로 찬장에 쌓인 접시 더미는 LIFO — “나중에 들어온 것이 먼저 나간다” 원리로 동작합니다. Java에서는 이러한 원리에 대응하는 컬렉션이 있습니다: 큐 Queue, 양방향 큐 Deque, 스택 Stack.
어디에 쓰이나요:
- 도착 순서대로 작업 처리(작업 큐, 문서 인쇄, 이벤트 처리).
- 동작 취소/재실행(undo/redo) — 스택.
- 식 파싱, 트리/그래프 순회(너비/깊이 우선 탐색) 등.
큐란?
큐(Queue)는 FIFO 원리에 따라 동작하는 컬렉션입니다. 요소는 끝에 추가되고 앞에서 꺼냅니다. 가게 줄처럼 먼저 온 사람이 먼저 처리됩니다.
Queue 인터페이스의 주요 메서드
| 메서드 | 무엇을 함 | 반환값 |
|---|---|---|
|
끝에 요소를 추가(예외 없음) | true/false |
|
끝에 요소를 추가(예외를 던짐) | true/Exception |
|
첫 요소를 제거하고 반환 | 요소/null |
|
첫 요소를 제거하고 반환 | 요소/Exception |
|
삭제하지 않고 첫 요소를 반환 | 요소/null |
|
삭제하지 않고 첫 요소를 반환 | 요소/Exception |
비슷한 동작을 하는 메서드 쌍이 보입니다. 차이는 “관대함”입니다: offer, poll, peek은 실패 시 특별한 값을 반환(보통 null 또는 false)하고 예외를 던지지 않습니다. 반면 add, remove, element는 경계 상황(큐가 비었거나, 때로는 용량 초과)에서 예외를 던집니다.
예시: 작업 큐
import java.util.*;
public class QueueDemo {
public static void main(String[] args) {
Queue<String> tasks = new LinkedList<>();
tasks.offer("양치하기");
tasks.offer("운동하기");
tasks.offer("커피 마시기");
while (!tasks.isEmpty()) {
String task = tasks.poll(); // 큐의 앞에서 작업을 가져옴
System.out.println("실행 중: " + task);
}
}
}
출력:
실행 중: 양치하기
실행 중: 운동하기
실행 중: 커피 마시기
왜 LinkedList를 자주 사용할까?
인터페이스는 계약이고 구현은 여러 가지가 있습니다. LinkedList는 양쪽 끝에서의 추가/삭제가 빨라 자주 사용됩니다. 그러나 훌륭한 대안은 ArrayDeque입니다. 특수한 구현도 있습니다: PriorityQueue(우선순위 큐) — 아래에서 다룹니다.
2. Deque 인터페이스: 양방향 큐
Deque(Double Ended Queue, “덱”)는 요소를 양쪽 끝 — 앞과 뒤 — 모두에서 추가/삭제할 수 있는 큐입니다. 두 개의 문이 있는 버스처럼 어느 쪽으로든 타고 내릴 수 있습니다.
Deque = 만능 병기: 일반 큐(FIFO), 스택(LIFO), 둘 다의 하이브리드처럼 사용할 수 있습니다.
Deque 인터페이스의 주요 메서드
| 메서드 | 무엇을 함 | 사용 예 |
|---|---|---|
|
앞에 추가 | |
|
뒤에 추가 | |
|
앞에서 제거하고 반환 | |
|
뒤에서 제거하고 반환 | |
|
앞 요소를 보기(삭제하지 않음) | |
|
뒤 요소를 보기(삭제하지 않음) | |
|
앞에 추가(예외 없음) | |
|
뒤에 추가(예외 없음) | |
예시: Deque를 큐와 스택으로 사용하기
import java.util.*;
public class DequeDemo {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
// 큐(FIFO)로 사용
deque.offerLast("A");
deque.offerLast("B");
deque.offerLast("C");
System.out.println("큐(FIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.pollFirst());
}
// 스택(LIFO)으로 사용
deque.offerLast("1");
deque.offerLast("2");
deque.offerLast("3");
System.out.println("스택(LIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.pollLast());
}
}
}
출력:
큐 (FIFO):
A
B
C
스택 (LIFO):
3
2
1
왜 ArrayDeque인가?
ArrayDeque는 배열 기반의 빠르고 컴팩트한 Deque 구현입니다. 스택과 큐 용도로는 오래된 Stack보다 일반적으로 더 빠르고 신뢰할 수 있으며, 고정 크기가 없고(메모리만 한계) 제한받지 않습니다.
3. Stack: 스택 — 나중에 들어온 것이 먼저 나감(LIFO)
스택은 LIFO 원리로 동작하는 컬렉션입니다. 마지막으로 추가된 요소가 맨 위에서 제거됩니다. 프로그래밍에서 스택은 동작 이력(undo), 재귀 구조(트리/그래프) 순회, 식 계산 등에 유용합니다.
Stack 클래스(그리고 왜 사용하지 말아야 하는가)
Java에는 Stack 클래스가 있으며, 이는 구식 Vector를 상속합니다. 오늘날 새로운 프로젝트에서는 사용을 권장하지 않습니다. Deque/ArrayDeque를 사용하는 것이 더 바람직합니다.
스택 메서드(Deque)
| 메서드 | 무엇을 함 |
|---|---|
|
스택의 맨 위에 요소를 넣음 |
|
맨 위 요소를 꺼내 반환 |
|
맨 위 요소를 확인 |
주의: Deque에서는 이 연산들이 addFirst/removeFirst/peekFirst에 대응하지만, 호환성을 위해 push/pop/peek 같은 “스택식” 이름도 제공합니다.
예시: ArrayDeque로 스택 구현
import java.util.*;
public class StackDemo {
public static void main(String[] args) {
Deque<String> stack = new ArrayDeque<>();
stack.push("첫 번째");
stack.push("두 번째");
stack.push("세 번째");
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
출력:
세 번째
두 번째
첫 번째
왜 Stack이 아닐까?
- Stack은 동기화되어(더 느림) 구식 Vector를 상속합니다.
- ArrayDeque가 더 빠르고 컴팩트한 경우가 많으며, 스레드를 블로킹하지 않습니다.
- 새 코드에서 Stack을 보면 보통 ArrayDeque로 교체할 후보입니다.
4. 언제 무엇을 사용할까
| 구조 | 원리 | 사용처 | 구현 예 |
|---|---|---|---|
| Queue | FIFO | 작업 큐, 이벤트 처리, 인쇄, 고객 대기열 | |
| Stack | LIFO | Undo/redo, 재귀, 파서, 트리 순회 | |
| Deque | FIFO/LIFO | 버퍼, 회문 검사, 양방향 큐, 범용 작업 | |
생활 속 예시:
- 은행의 줄 — Queue.
- 에디터의 동작 이력 — Stack.
- 양쪽에서 진입/이탈 가능한 버스 대기열 — Deque.
5. 코드 예시: 미니 앱으로 큐와 스택 구현
예제 1: 문서 인쇄 큐
import java.util.*;
public class PrintQueueApp {
public static void main(String[] args) {
Queue<String> printQueue = new ArrayDeque<>();
printQueue.offer("문서1.pdf");
printQueue.offer("문서2.docx");
printQueue.offer("문서3.xls");
while (!printQueue.isEmpty()) {
String doc = printQueue.poll();
System.out.println("인쇄 중: " + doc);
}
}
}
예제 2: 실행 취소 스택(undo)
import java.util.*;
public class UndoStackApp {
public static void main(String[] args) {
Deque<String> undoStack = new ArrayDeque<>();
undoStack.push("텍스트 삽입");
undoStack.push("색상 변경");
undoStack.push("이미지 삭제");
System.out.println("마지막 동작: " + undoStack.peek()); // 이미지 삭제
while (!undoStack.isEmpty()) {
System.out.println("취소: " + undoStack.pop());
}
}
}
예제 3: 양방향 큐
import java.util.*;
public class DequeApp {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A");
deque.addLast("B");
deque.addFirst("C");
deque.addLast("D");
System.out.println("앞에서 꺼내기: " + deque.removeFirst()); // C
System.out.println("뒤에서 꺼내기: " + deque.removeLast()); // D
System.out.println("남은 것: " + deque); // [A, B]
}
}
6. 구현 특징과 주의점
- ArrayDeque는 대부분의 작업에서 가장 빠르고 범용적인 큐/스택 구현입니다.
- LinkedList도 Deque를 구현합니다. 유용할 수 있지만, 짧은 큐에서는 보통 ArrayDeque보다 느립니다.
- PriorityQueue는 우선순위 큐로, 순서가 우선순위(자연 순서 또는 Comparator 지정)에 의해 결정됩니다. 일반적인 FIFO 큐가 아닙니다.
- Stack은 구식이고 동기화되어 있습니다. 새로운 프로젝트에서는 ArrayDeque가 더 적합합니다.
- Deque는 앞과 뒤를 모두 다룰 수 있어 큐와 스택 시나리오를 하나의 추상화로 포괄합니다.
7. 큐와 스택 사용 시 흔한 실수
오류 1: Deque 대신 Stack 사용.
초보자는 이름만 보고 Stack 클래스를 선택하는 경우가 있습니다. 현대 프로젝트에서는 그 대신 ArrayDeque(또는 LinkedList)의 push/pop 메서드를 사용합니다.
오류 2: 자료구조 원리 위반.
예를 들어 queue.get(0) 또는 stack.get(0)처럼 큐/스택의 요소에 인덱스로 접근하려 합니다. 이렇게 하면 안 됩니다 — 큐/스택 전용 메서드(peek, poll, pop 등)를 사용하세요.
오류 3: 검증 없이 remove()/element()/add() 사용.
remove, element, add는 구조가 비었거나/가득 찼을 때 예외를 던질 수 있습니다. 실패 시 특별한 값을 반환하는 “관대한” offer, poll, peek을 사용하는 편이 더 안전합니다.
오류 4: ArrayDeque에 null 요소 사용.
ArrayDeque는 null을 허용하지 않습니다. null을 추가하려 하면 NullPointerException이 발생합니다.
오류 5: PriorityQueue를 일반 큐처럼 사용.
PriorityQueue의 순서는 우선순위(자연 순서 또는 Comparator 지정)로 결정됩니다. 엄격한 FIFO가 필요하면 ArrayDeque나 LinkedList를 사용하세요.
오류 6: for-each 순회 중 큐/스택 수정.
for-each 동안 컬렉션에서 요소를 제거하면 ConcurrentModificationException이 발생할 수 있습니다. 제거가 필요하다면 이터레이터를 사용하거나, 예시에서 보인 것처럼 poll/pop을 루프에서 호출하세요.
GO TO FULL VERSION