Deque

데크는 양쪽에서 삭제와 삽입을 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있다. 구현은 배열이나 연결 리스트 모두 가능하지만 이중 연결 리스트로 구현하는 편이 가장 잘 어울린다.

이중 연결 리스트

이중 연결 리스트로 구현하게 되면 양쪽으로 head와 tail이라는 이름의 두 포인터를 갖고 있다가 새로운 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결 시켜주기만 하면 된다. 당연히 연결 후에는 포인터를 이동하면 된다. 

 

파이썬에서는 데크 자료형을 다음과 같이 collections 모듈에서 deque라는 이름으로 지원한다.

데크

collections.deque는 그림 10-1과 마찬가지로 이중 연결 리스트로 구현되어 있다.

Deque를 사용하면 맨 앞과 맨 뒤에 엔티티를 추가하거나 삭제할 때 모두 O(1)에 실행이 가능하다.