Deque

데크(Deque)는 스택과 큐의 결합체라고 생각할 수 있다. 스택, 큐와는 다르게 양쪽 끝에서 항목의 조회, 삽입, 삭제가 모두 가능한 자료구조이다. 데크는 앞서 작성한 큐를 바탕으로 구현할 수 있다.

from queue import Queue #이전에 작성한 Queue 코드를 이용

class Deque(Queue):
	def enqueue_back(self, item):
    	self.items.append(item)
    
    def dequeue_front(self):
    	value = self.items.pop(0)
        if value is not None:
        	return value
        else:
        	print("Deque is empty.")

이 데크 코드에서 항목을 삽입하거나 삭제할 때, 앞서 구현한 큐의 코드를 이용하기 때문에, insert() 메소드를 사용하게 된다. 따라서 이 코드에서 끝이 아닌 다른 위치에 있는 항목을 삽입하거나 삭제할 때는 비효율적이다. 이 문제를 해결하기 위해서, python에서 제공하는 collections 패키지의 deque 모듈을 사용한다.

출처: 파이썬 자료구조와 알고리즘, 미아 스타인 지음, 최길우 옮김