Deque 연산: 스택과 큐
LinkedList를 Deque로 사용해 스택(push/pop)과 큐(offer/poll) 동작을 구현합니다.
Deque 연산: 스택과 큐은(는) CoddyKit의 무료 Java Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Java Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
양방향 큐
양방향 큐는 양쪽 끝에서 삽입과 제거를 수행할 수 있습니다. Java의 Deque 인터페이스는 LinkedList와 ArrayDeque가 구현합니다.
import java.util.Deque;
import java.util.ArrayDeque;
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B"); // back
deque.addFirst("Z"); // new front
System.out.println(deque); // [Z, A, B]덱으로 사용하는 ArrayDeque와 LinkedList
덱으로 사용할 때는 일반적으로 ArrayDeque가 LinkedList보다 선호됩니다.
- 요소별 Node 오버헤드가 없습니다
- 캐시 지역성이 더 좋습니다
- 스택/큐 연산이 약간 더 빠릅니다
List 인터페이스도 필요할 때만 LinkedList를 선택합니다.
덱을 사용한 스택 연산
LIFO 스택을 구현하려면 push(addFirst)와 pop(removeFirst)을 사용합니다. 기존 Stack 클래스는 동기화되어 있고 오래된 방식이므로 사용하지 마십시오.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop()); // 2덱을 사용한 큐 연산
FIFO 큐를 구현하려면 offer(addLast)와 poll(removeFirst)을 사용합니다. offer는 실패하면 false를 반환하고, add는 예외를 발생시킵니다.
Deque<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");
queue.offer("task3");
System.out.println(queue.poll()); // task1
System.out.println(queue.poll()); // task2
System.out.println(queue.size()); // 1덱 메서드 참조 표
Deque는 두 가지 메서드 계열을 제공합니다. 하나는 예외를 발생시키고, 다른 하나는 특별한 값을 반환합니다.
- addFirst/addLast와 offerFirst/offerLast
- removeFirst/removeLast와 pollFirst/pollLast
- getFirst/getLast와 peekFirst/peekLast
빈 덱에서 예외가 발생하는 것을 피하려면 offer/poll/peek 계열을 우선 사용합니다.
실전 예시: 두 스택을 사용한 실행 취소/다시 실행
Deque의 대표적인 사용 사례입니다. 실행 취소 기록은 하나의 스택이고, 다시 실행 기록은 또 다른 스택입니다.
Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();
undo.push("type 'Hello'");
undo.push("type ' World'");
String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);
System.out.println("Redo top: " + redo.peek()); // type ' World'덱을 사용한 회문 확인
덱을 사용하면 양쪽 끝의 문자를 동시에 비교할 수 있어 회문 확인을 간결하게 구현할 수 있습니다.
Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);
boolean isPalindrome = true;
while (deque.size() > 1) {
if (!deque.pollFirst().equals(deque.pollLast())) {
isPalindrome = false;
break;
}
}
System.out.println(isPalindrome); // true큐를 사용한 BFS
너비 우선 탐색은 큐를 사용합니다. 경쟁 프로그래밍과 그래프 순회에서 ArrayDeque가 BFS의 표준 선택입니다.
import java.util.*;
// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
1, List.of(2,3),
2, List.of(4),
3, List.of(4),
4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
int node = queue.poll();
if (visited.add(node)) {
System.out.print(node + " ");
queue.addAll(graph.get(node));
}
}스택을 사용한 DFS
깊이 우선 탐색은 스택을 사용합니다. 이 경우에도 오래된 방식인 Stack 클래스보다 ArrayDeque를 우선 사용합니다.
Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited.add(node)) {
System.out.print(node + " ");
// push neighbors (will be processed in reverse order)
List<Integer> neighbors = List.of(2, 3); // simplified
for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
}
}크기 확인을 사용하는 제한된 덱
ArrayDeque는 동적으로 크기가 늘어나지만, 용량을 직접 제한하여 크기가 제한된 버퍼처럼 사용할 수 있습니다.
Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;
for (int i = 1; i <= 5; i++) {
if (buffer.size() >= MAX) {
buffer.pollFirst(); // drop oldest
}
buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]성능 참고 사항
ArrayDeque는 원형 배열을 사용하며 배열이 가득 차면 크기를 두 배로 늘립니다. 모든 연산의 분할 상환 비용은 O(1)입니다. 캐시 효율성 덕분에 대부분의 성능 측정에서 LinkedList보다 빠릅니다. 직접 동기화하지 말고, 동시성 처리가 필요하면 ConcurrentLinkedDeque나 블로킹 큐를 사용하십시오.
빠른 확인
LIFO 연산에서 기존 Stack 대신 어떤 클래스를 사용해야 합니까?
복습: 덱 연산
핵심 내용:
- Deque를 사용하면 양쪽 끝에서 O(1) 삽입/제거가 가능합니다
- 순수한 스택/큐 용도에는 LinkedList보다 ArrayDeque가 선호됩니다
- push/pop → LIFO 스택, offer/poll → FIFO 큐
- 대표적인 사용 사례: 실행 취소/다시 실행, BFS/DFS, 슬라이딩 윈도, 회문 확인
- 기존 Stack 및 Queue 클래스는 사용하지 마십시오
자주 묻는 질문
“Deque 연산: 스택과 큐” 강의는 무료인가요?
네 — “Deque 연산: 스택과 큐” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Java Academy 강의 전체를 잠금 해제할 수 있습니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“Deque 연산: 스택과 큐”에서 뭘 배우나요?
LinkedList를 Deque로 사용해 스택(push/pop)과 큐(offer/poll) 동작을 구현합니다. 브라우저에서 직접 실행하는 실습 코드로 Java Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Java Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Java Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“Deque 연산: 스택과 큐” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Java Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Java Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.