덱(Deque)
**Deque(Double-Ended Queue, 덱)**는 양쪽에서 데이터를 삽입/삭제할 수 있는 자료구조입니다.
✔ Stack (LIFO) + Queue (FIFO)의 특성을 모두 가짐
✔ 양방향 입출력 가능 → 유연한 데이터 처리
✔ Work-Stealing 알고리즘에서 스레드 간 작업을 분배할 때 활용됨
1. Deque의 구조 및 동작 방식 (그림 포함)
Deque는 배열 기반 또는 연결 리스트 기반으로 구현될 수 있으며,
양쪽 끝에서 데이터를 삽입/삭제할 수 있습니다.
1.1 Deque의 기본 동작
| 연산 | 설명 |
| addFirst(e) | 앞(front)에서 데이터 추가 |
| addLast(e) | 뒤(back)에서 데이터 추가 |
| removeFirst() | 앞(front)에서 데이터 제거 |
| removeLast() | 뒤(back)에서 데이터 제거 |
| getFirst() | 앞(front)의 데이터 조회 |
| getLast() | 뒤(back)의 데이터 조회 |
1.2 Deque 동작 예시 (그림)
1️⃣ 처음 상태 (비어 있는 Deque)
| [ ] |
2️⃣ 데이터 추가 (addFirst(1), addLast(2), addLast(3))
| [ 1 ] → [ 1, 2 ] → [ 1, 2, 3 ] |
3️⃣ 앞에서 삭제 (removeFirst())
| [ 1, 2, 3 ] → [ 2, 3 ] (1 제거) |
4️⃣ 뒤에서 삭제 (removeLast())
| [ 2, 3 ] → [ 2 ] (3 제거) |
✅ 양쪽에서 삽입과 삭제가 가능함
2. Deque의 내부 구현 (배열 vs 연결 리스트)
2.1 배열 기반 Deque (ArrayDeque)
- ArrayDeque<E> (배열을 사용한 덱)
- 배열의 인덱스를 이동하며 데이터를 삽입/삭제
- 원형 배열 구조를 사용하여 공간 낭비 최소화
- O(1)의 시간 복잡도로 앞/뒤에서 삽입/삭제 가능
- 하지만 중간 삽입/삭제는 O(n)으로 비효율적
🔹 메모리 구조: Heap 영역에 동적 배열 할당
🔹 장점: 빠른 접근 속도, 메모리 절약
🔹 단점: 크기 제한 있음 (배열 크기 초과 시 확장 필요)
2.2 연결 리스트 기반 Deque (LinkedList)
- LinkedList<E> (이중 연결 리스트를 사용한 덱)
- 각 노드가 prev(이전), next(다음)를 가리킴
- 앞/뒤 삽입/삭제: O(1)
- 중간 삽입/삭제: O(n)
- 하지만 참조 포인터 때문에 메모리 사용량 증가
🔹 메모리 구조: Heap 영역에 개별 노드들이 동적으로 할당
🔹 장점: 크기 제한 없음, 중간 삽입/삭제 용이
🔹 단점: 노드당 prev, next 포인터가 추가로 필요하여 메모리 사용량 증가
3. Deque의 메모리 활용 및 저장 위치
자바에서 Deque는 Heap 영역에 저장되며,
객체 참조 변수는 Stack 또는 메서드 영역에 저장됩니다.
| 메모리 영역 | 저장되는 데이터 |
| Stack | Deque 객체의 참조 변수 |
| 메서드 영역 | Deque 클래스의 코드, 정적 변수 |
| Heap | Deque 객체 자체 (ArrayDeque, LinkedList) |
추가
알고리즘 스택 구현시
Java에서 **스택(Stack)**을 구현할 때 보통 Stack<Integer>를 사용하지만, ArrayDeque<Integer>가 더 효율적
1️⃣ Stack<?> vs ArrayDeque<?> 차이점
| 비교 항목 | Stack | ArrayDeque |
| 자료구조 | Vector 기반 | Resizable Array 기반 (ArrayList와 비슷) |
| 스레드 안전성 | O (synchronized) | X (비동기, 성능 향상) |
| 성능 | 동기화 때문에 느림 | 빠름 (Lock-Free) |
| 메서드 명칭 | push(), pop(), peek() | push(), pop(), peek() |
| 추천 여부 | ❌ (구식 API) | ✅ (권장) |
멀티스레드 환경에서는 ConcurrentLinkedDeque<Integer>를 고려