[자료구조] 4. Deque

1. 정의

데크(Deque)는 Doubly-ended Queue의 약자이다. 흔히 Head-Tail Linked List라고도 불리며, List의 양쪽 끝 모두에서 데이터의 삽입과 삭제가 가능한 자료 구조이다. Stack과 Queue의 장점만을 모아 만들어졌다고 한다. 삽입/삭제가 모두 가능한 양쪽 끝을 부르는 명칭은 많으나, Queue와 동일하게 Front와 Rear를 사용하도록 하자.

<The Concept of Deque>

2. 종류

Deque에는 제약조건을 주어서 사용 목적에 따라 다르게 사용할 수 있다. 입력이 한쪽에서만 가능하고 출력은 양쪽에서 모두 가능하도록 하는 Deque는 Scroll이라고 하며, 출력이 한쪽에서만 가능하고 입력이 양쪽에서 모두 가능하도록 한 Deque는 Shelf라고 한다.

1) Scroll(입력제한데크)

2) Shelf(출력제한데크)