[Java] Deque

Deque, java.util.Deque, Java Deque, double-ended queue, 양방향 큐, 덱

정의

java.util.Deque<E> (Double-Ended Queue) 는 Queue 의 확장 인터페이스. 양쪽 끝 (head, tail) 모두에서 add/remove/examine 가능한 자료구조.

JDK 1.6 도입. Queue, Stack, 일반 List 의 양 끝 연산을 모두 한 인터페이스로 통합.

메서드 매트릭스

위치	insert (throw)	insert (특수값)	remove (throw)	remove (특수값)	examine
head	addFirst(e)	offerFirst(e)	removeFirst()	pollFirst()	peekFirst()
tail	addLast(e)	offerLast(e)	removeLast()	pollLast()	peekLast()
Queue (= tail/head)	add(e)	offer(e)	remove()	poll()	peek()
Stack (= head)	push(e)	(= addFirst)	pop()	(= removeFirst)	peek()

push / pop 이 head 쪽에 동작하는 점이 중요. Stack 으로 쓸 때 head 가 top 이 된다.

구현체

구현	특징
ArrayDeque	권장 기본, 원형 배열
LinkedList	양방향 연결 리스트, 메모리 多
ConcurrentLinkedDeque	thread-safe (lock-free)
LinkedBlockingDeque	thread-safe + blocking

// Stack 패턴
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.push(3);
stack.peek();    // 3
stack.pop();     // 3

// Queue 패턴
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2); queue.offer(3);
queue.peek();    // 1
queue.poll();    // 1

참고

• Object
• Iterable
• Collection
• Queue
• ArrayDeque
• LinkedList
• ConcurrentLinkedDeque