데크에 대한 설명

1. 원형 데크 디자인

우선 순위 큐에 대한 설명

1. k개 정렬 리스트 병합

데크

이전 장에서 원형 큐를 구현하면서 Front()와 Rear()를 모두 구현했는데 , 사실 Rear()는 큐에 정의 되어있지 않은 연산으로, 데크의 연산이다

데크의 정의는 다음과 같다.

데크 (Deque)는 Double-Ended Queue의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다.

데크는 양쪽에서 삭제와 삽입을 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 가지고 있다.

배열이나, 연결 리스트 모두 구현이 가능하지만, 특히 이중 연결 리스트 (Doubly-Linked-List)로 구현하는 편이 가장 잘 어울린다.

이 경우 새로운 요소가 추가 되거나, 삭제될 때, head 노드나 tail 노드, 포인터를 이용하면 되므로 용이하다.

파이썬에서 사용하는 collections.deque또한 이중 연결 리스트로 구현되어 있다.