[자료구조] Deque(Double-Ended Queue)

Deque(덱, Double-Ended Queue)란?

양쪽(앞, 뒤)에서 삽입과 삭제가 모두 가능한 큐이며 스택과 큐의 특성이 동시에 있는 자료구조입니다.

 

Deque 특징

1. 앞, 뒤로 삽입, 삭제 가능

일반적인 큐는 한 쪽으로만 삽입이 가능하고 반대편으로 삭제만 가능했다면 Deque는 양 옆으로 삽입, 삭제가 가능한 자료구조입니다.

 

2. 빠른 연산 속도

일반적으로 LinkedList 또는 Array로 구현되며 삽입/삭제 연산이 O(1)로 수행됩니다.

 

3. 두 가지 형태로 사용 가능

• Stack
• Queue

 

Deque 주요 연산

연산	설명
pushFront(element)	앞쪽에 요소 추가
pushBack(element)	뒷쪽에 요소 추가
popFront()	앞쪽 원소 제거 및 반환
popBack()	뒷쪽 원소 제거 및 반환
peekFront()	앞쪽 원소 확인(제거하지 않음)
peekBack()	뒷쪽 원소 확인(제거하지 않음)
isEmpty()	비어 있는지 확인(true/false)
size()	저장한 요소 개수 반

 

 

구현 2가지 방식 장단점

1. 배열 기반 Deque

고정된 크기의 배열을 사용하여 Dequq 구현

배열의 앞, 뒤에 삽입/삭제를 해야하기 때문에 요소를 이동해야 하는 단점이 존재

 

2. LinkedList 기반 Deque

이중 연결 리스트를 사용하여 구현

노드를 앞, 뒤에서 추가, 삭제가 가능

메모리 사용량이 증가(포인터를 저장하기 위한 공간)