[Java] Deque

🔍 Deque - 스택과 큐를 모두 활용하기

코딩 테스트에서 스택(Stack) 과 큐(Queue) 자료구조는 필수적으로 사용됨
자바에서는 Stack과 Queue가 각각 존재하지만, Deque(Double-Ended Queue)를 사용하면 스택처럼 사용할 수도, 큐처럼 사용할 수도 있으며 성능까지 우수함

---

📃 Deque

Deque(Double-Ended Queue, 데크)는 양쪽(앞/뒤)에서 요소를 추가하고 제거할 수 있는 자료구조

• Queue의 확장 형태
• 스택과 큐의 기능을 모두 제공
• ArrayDeque, LinkedList 클래스로 구현 가능

---

🛠️ Deque 사용법

1️⃣ 요소 추가

메서드	설명	실패 시
addFirst(E e)	앞에 추가	IllegalStateException
offerFirst(E e)	앞에 추가	false 반환
addLast(E e)	뒤에 추가	IllegalStateException
offerLast(E e)	뒤에 추가	false 반환

2️⃣ 요소 제거

메서드	설명	데크가 비어있을 때
removeFirst()	앞 요소 제거	NoSuchElementException
pollFirst()	앞 요소 제거	null 반환
removeLast()	뒤 요소 제거	NoSuchElementException
pollLast()	뒤 요소 제거	null 반환

3️⃣ 요소 조회 (삭제 없이 확인)

메서드	설명	데크가 비어있을 때
getFirst()	앞 요소 확인	NoSuchElementException
peekFirst()	앞 요소 확인	null 반환
getLast()	뒤 요소 확인	NoSuchElementException
peekLast()	뒤 요소 확인	null 반환

---

🧱 Deque의 다양한 구현체

자바에서 Deque 인터페이스를 구현하는 대표적인 클래스는 아래와 같음

1️⃣ ArrayDeque (가장 많이 사용됨)

• 내부적으로 배열을 사용하여 구현됨
• 빠른 접근 속도를 가짐 (LinkedList보다 성능 우수)
• 초기 크기 제한이 없음, 자동으로 크기 조절
• Stack 대체용으로 추천

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque.pollFirst()); // 1

2️⃣ LinkedList (연결 리스트 기반)

• 내부적으로 이중 연결 리스트를 사용
• 삽입/삭제가 빠르지만, 접근 속도는 느림
• 메모리 사용량이 ArrayDeque보다 많음
• Queue와 Deque 모두 지원하지만, 성능 면에서는 ArrayDeque가 우수

Deque<String> deque = new LinkedList<>();
deque.addFirst("A");
deque.addLast("B");
System.out.println(deque.pollLast()); // B

3️⃣ ConcurrentLinkedDeque (멀티스레드 환경)

• 멀티스레드 환경에서 안전하게 동작하는 비동기 데크
• 락-프리(Non-blocking) 알고리즘 사용
• 동시성 환경에서 큐를 활용할 때 유용

Deque<Integer> deque = new ConcurrentLinkedDeque<>();
deque.offerFirst(1);
deque.offerLast(2);
System.out.println(deque.pollFirst()); // 1

---

🆚 Deque vs Stack vs Queue 비교

기능	Deque	Stack	Queue
앞/뒤 사용	가능	불가능	불가능
스택처럼 사용	가능	가능	불가능
큐처럼 사용	가능	불가능	가능
성능	빠름 (ArrayDeque 권장)	느림 (동기화 문제)	보통 (LinkedList)

---

✅ 결론: 코딩 테스트에서는 Deque (ArrayDeque) 사용하기!

스택과 큐를 하나로 해결할 수 있음
Stack보다 성능 우수(ArrayDeque 사용)
BFS, DFS 등 다양한 문제에서 활용 가능