[TAVE/파이썬 알고리즘] Ch10 | 데크, 우선순위 큐 - 개념 정리

개념 정리

📌데크: 스택과 큐 자료형의 특징을 모두 갖고 있는 복합 자료형이다. 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다.

👉🏻배열이나 연결 리스트로 구현할 수 있다. 

이중 연결 리스트로 구현한 데크 구조

👉🏻그림과 같이 이중 연결 리스트로 구현하면 양쪽처럼 HEAD와 TAIL이라는 이름의 두 포인터를 가지고 있다가 새로운 아이템이 추가될 때마다 앞쪽 혹은 뒤쪽으로 연결시켜준다. 연결 후에는 포인터를 이동하면 된다.

import collections
d = collections.deque()
type(d) #<class 'collections.deque'>

👉🏻파이썬은 collections 모듈에서 deque라는 이름으로 데크 자료형을 지원한다. 이 deque는 이중 연결 리스트로 구현되어 있다.