[자료구조] 5. 덱(Deque)

덱(Deque)

Deque(덱)은 Double-ended queue의 줄임말입니다. 이는 큐와 매우 비슷한 자료구조입니다. 큐가 front에서 dequeue를 하고 rear에서만 enqueue를 했다면, 덱에서는 양쪽으로 enqueue와 dequeue가 가능합니다. 파이썬 Collections 기준으로는 enqueue 시에 append()와 appendleft() 함수를 사용하고, dequeue 시에는 pop()와 popleft()를 사용합니다.

이러한 특성으로 덱은 스택과 큐 모두를 대체 가능한 자료구조입니다. 그렇다면 왜 큐와 스택 대신 항상 덱을 사용하지 않을까요? 이에 대한 답은 굳이 두 가지의 특성을 합친 것이 필요하지 않은 경우가 많기 때문입니다. 또한 덱을 사용하면 오버헤드가 발생할 수 있는 경우도 있습니다.

다만 알아두어야 할 것은, 정말로 중요한 것은 어떻게 구현되었는가입니다. 예를 들면 파이썬에서는 기본 제공되는 덱이 큐보다 빠를 수 있는데, 이는 큐는 멀티스레드 환경을 지원을 염두에 두고 설계하였기 때문에 멀티스레드를 사용하지 않고 단순하게 작성할 경우 덱보다 더 느릴 수 있다는 것입니다. 또한 자바에서는 스택보다 덱을 사용하는 것을 권장하는 글도 스택 오버플로우에서 찾아볼 수 있습니다. 이처럼 대부분의 문제는 단지 기본 라이브러리의 구현이 어떻게 되었는가의 차이로 나타납니다.

구현

큐를 구현할 때에는 연결 리스트를 사용하면 단일 연결 리스트(Singly linked list)로도 쉽게 구현 가능합니다. 그러나 덱(Deque)은 양방향에서의 pop과 push 연산이 필요하므로 이중 연결 리스트(Doubly linked list)가 필요합니다. 또는 배열을 활용하여 큐를 구현할 수도 있으며, 이 경우 양쪽 방향으로의 enqueue와 dequeue 모두 시간 복잡도가 O(1)입니다.

또한 큐를 구현할떄처럼 배열을 순환하는 방식으로도 구현이 가능합니다.