자료구조 Deque

Deque (Double Ended Queue, 양방향 대기열)

Deque는 Stack과 Queue의 특성들이 혼합된 느낌이다

• Stack : 데이터가 한 방향으로 추가되고 삭제할 수 있음
• Queue : 데이터가 한방향으로 추가되고 다른 방향으로 데이터가 삭제됨

자료구조 스택 Stack

자료구조 큐 Queue

 

양방향으로 열려있는 구조로, Queue와 외형적으로 비슷하다

하지만 Deque는 Stack, Queue와 달리 LIFO, FIFO 같은 순서에 얽매이지 않는다

---

Deque의 특징

1. Stack과 Queue를 모두 사용할 수 있음

• 추가를 제한하는 구조

한쪽에서만 데이터 추가가 가능하고 삭제는 양방향에서 가능하게 구현한다면 아래와 같은 구조가 된다

왼쪽에서 삭제하면 Stack과 같고 오른쪽으로 삭제하면 Queue와 같다

 

• 삭제를 제한하는 구조

데이터 추가는 양쪽에서 가능하지만, 삭제는 한 방향만 가능하게 구현한다면

왼쪽에서 데이터를 추가하면 Stack과 같고 오른쪽에서 추가하면 Queue와 같아진다

 

 

2. 양방향 끝에서 데이터 추가, 삭제가 용이함

 

3. 양방향 끝이 아닌 임의의 인덱스값으로 추가 삭제가 불가능

• 양쪽 끝을 제외한 인덱스 정보를 갖고 있지 않다