[Data Structure] 덱(Deque)

덱

• 선형 자료 구조
• Deque : Double Ended Queue
• 데이터의 삽입과 삭제가 양쪽에서 일어남
• 스택과 큐를 합친 형태

덱의 기본 연산

• 데이터 추가
  • 덱에 데이터 추가
  • C++(deque STL)
    • push_front(), push_back()
  • Java(ArrayDeque)
    • add() : addLast()와 동일
    • addFirst(), addLast()
    • offer() : offer()와 동일
    • offerFirst(), offerLast() : 용량 초과 시 false 리턴
• 데이터 삭제
  • 덱에서 데이터 삭제
  • C++(deque STL)
    • pop_front(), pop_back()
  • Java(ArrayDeque)
    • remove() : removeFirst()와 동일
    • removeFirst(), removeLast() : 덱이 비어있는 경우 예외 발생
    • poll() : pollFirst()와 동일
    • pollFirst(), pollLast() : 덱이 비어있는 경우 null 리턴

덱의 시간 복잡도

• 제일 앞/뒤의 원소 추가/제거 : $O(1)$
• 제일 앞/뒤의 원소 확인 : $O(1)$
  • 제일 앞/뒤 이외의 원소 확인이 원칙적으로는 불가능하다

C++ STL vs Java

• C++에서 덱 선언
  • C++에서 deque은 vector의 기능을 모두 사용 가능하다

#include <deque>

deque<T> dq;
...
dq[0] // 인덱스 접근 가능

• Java에서 덱 선언

import java.util.ArrayDeque;
import java.util.Deque;

Deque deque = new ArrayDeque();

• 메소드 비교

	C++	Java(Stack 클래스 기준)
앞쪽 원소 삽입	push_front(ITEM)	addFirst(ITEM), offerFirst(ITEM)
뒤쪽 원소 삽입	push_back(ITEM)	add(ITEM), addLast(ITEM), offer(ITEM), offerLast(ITEM)
앞쪽 원소 삭제	pop_front()	remove(), removeFirst(), poll(), pollFirst()
뒤쪽 원소 삭제	pop_back()	removeLast(), pollLast()
앞쪽 원소 확인	front(ITEM)	getFirst(ITEM)
뒤쪽 원소 확인	back(ITEM)	getLast(ITEM)
크기	size()	size()
비어있는지 여부	empty()	isEmpty()
초기화	clear()	clear()