TIL - Deque (09.23)

📚 오늘 공부한 내용 - Deque 자료구조

🎯 Deque(데크/덱)란?

Deque는 "Double Ended Queue"의 약자로, 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 자료구조입니다. Stack과 Queue의 기능을 모두 포함한 매우 유연한 구조입니다.

🔄 Deque의 동작 원리

앞쪽 ←─ [2] [1] [3] [4] ─→ 뒤쪽
      ↑                  ↑
  offerFirst()      offerLast()
  pollFirst()       pollLast()

핵심: 앞과 뒤 양방향으로 데이터를 넣고 뺄 수 있는 만능 자료구조!

---

🔧 Deque의 주요 연산

데이터 추가

메서드 설명 위치

offerFirst(element)	앞쪽에 추가	← [element] [...]
offerLast(element)	뒤쪽에 추가	[...] [element] →

데이터 제거

메서드 설명 위치

pollFirst()	앞쪽에서 제거	← [remove] [...]
pollLast()	뒤쪽에서 제거	[...] [remove] →

데이터 조회

메서드 설명

peekFirst()	앞쪽 요소 조회 (제거 안 함)
peekLast()	뒤쪽 요소 조회 (제거 안 함)

실행 예시

Deque<Integer> deque = new ArrayDeque<>();

deque.offerFirst(1);  // [1]
deque.offerFirst(2);  // [2, 1] - 앞으로 추가하면 기존 요소가 뒤로 밀림
deque.offerLast(3);   // [2, 1, 3]
deque.offerLast(4);   // [2, 1, 3, 4]

System.out.println(deque.peekFirst()); // 2 (조회만)
System.out.println(deque.peekLast());  // 4 (조회만)

deque.pollFirst();  // 2 제거 → [1, 3, 4]
deque.pollLast();   // 4 제거 → [1, 3]

---

🏗️ Deque 구현체와 성능

주요 구현체

1. ArrayDeque ⭐ (권장)
2. LinkedList

성능 비교 (100만 건 테스트)

작업 ArrayDeque LinkedList

입력 (앞/뒤 평균)	110ms	480ms
조회 (앞/뒤 평균)	9ms	20ms

결론: ArrayDeque가 모든 면에서 더 빠름! 🚀

왜 ArrayDeque가 빠를까?

• ArrayDeque: 원형 큐 구조 + 배열 기반
• LinkedList: 동적 노드 링크 구조
• 현실: CPU 캐시 최적화, 메모리 접근 패턴에서 배열이 유리

---

🎭 Deque의 다양한 역할

Deque는 Stack과 Queue 역할을 모두 수행할 수 있어서, 각각을 위한 메서드 이름까지 제공합니다!

1️⃣ Stack으로 사용

Deque<Integer> stack = new ArrayDeque<>();

// Stack 메서드 사용
stack.push(1);    // 앞에서 입력 = offerFirst()
stack.push(2);    // 앞에서 입력
stack.push(3);    // 앞에서 입력
// 결과: [3, 2, 1]

stack.peek();     // 3 (앞쪽 조회)
stack.pop();      // 3 (앞에서 제거)
stack.pop();      // 2 (앞에서 제거)
// LIFO 동작!

2️⃣ Queue로 사용

Deque<Integer> queue = new ArrayDeque<>();

// Queue 메서드 사용
queue.offer(1);   // 뒤에서 입력 = offerLast()
queue.offer(2);   // 뒤에서 입력
queue.offer(3);   // 뒤에서 입력
// 결과: [1, 2, 3]

queue.peek();     // 1 (앞쪽 조회)
queue.poll();     // 1 (앞에서 제거)
queue.poll();     // 2 (앞에서 제거)
// FIFO 동작!

---

⚠️ 중요한 실무 팁

Java Stack 클래스 대신 Deque 사용하자!

// ❌ 성능이 좋지 않음
Stack<Integer> stack = new Stack<>();

// ✅ 권장: Deque로 Stack 구현
Deque<Integer> stack = new ArrayDeque<>();

인터페이스 선택 가이드

// Queue 기능만 필요한 경우
Queue<Integer> queue = new ArrayDeque<>();

// 양방향 기능이 필요한 경우
Deque<Integer> deque = new ArrayDeque<>();

// 구현체는 항상 ArrayDeque 권장!

---

🎯 오늘의 핵심 포인트

1. 양방향 자유자재: 앞과 뒤 모든 방향에서 입력/출력 가능
2. 만능 자료구조: Stack + Queue + α 역할
3. 성능 최고: ArrayDeque가 모든 면에서 우수
4. 메서드 제공: Stack용, Queue용 메서드 모두 지원
5. 실무 권장: Java Stack 대신 Deque 사용