✍️ 데크(Deque)란?
Deque는 double-ended queue의 줄임말로, 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다.
즉, 양방향 데이터를 처리가 가능한 자료구조이다.
스택(FILO)과 큐(FIFO) 둘다 가능하다.
데크는 위 그림과 같이 양쪽에서 삭제, 삽입 처리가 가능하다.
구현
배열이나 연결리스트 모두 구현이 가능하지만, 이중 연결 리스트(Doubly Linked List)로 구현하는 편이 가장 잘 어울린다
이중 연결리스트로 구성하게 되면 위 그림과 같이 투포인터(head, tail) 을 사용하여 새로운 노드(item) 연결 및 삭제 후 포인터를 이동시켜 처리한다.
파이썬에서는 이중연결리스트로 구현된 데크 자료형을 collections 모듈의 deque로 지원하며 아래와 같이 불러와 간편하게 사용가능하다.
from collections import deque
q: Deque = deque()
#시간복잡도: O(1), Stack(FILO)과 동일
append() # 오른쪽 데이터 추가
pop() # 오른쪽 데이터 삭제
#시간복잡도: O(1) Queue(FIFO)과 동일
appendleft() # 왼쪽 데이터 추가
popleft() # 왼쪽 데이터 삭제
...