Kwangmin Kim - Data Structure (7) Deque

1 덱(Deque)

정의: 덱 (Deque, Double-Ended Queue)

덱은 양쪽 끝(front, rear)에서 삽입과 삭제가 모두 가능한 자료구조다.

왼쪽/오른쪽 삽입: \(O(1)\)
왼쪽/오른쪽 삭제: \(O(1)\)
스택(LIFO)과 큐(FIFO)의 기능을 동시에 제공한다
Python: collections.deque로 제공된다

덱은 스택(stack)과 큐(queue)의 기능을 모두 가지고 있다.
그래서, 스택과 큐대신 덱을 사용해도 괜찮음
다만, 포인터 변수가 더 많이 필요하기 때문에, 메모리는 상대적으로 더 많이 필요하다.
Python에서는 큐(queue)의 기능이 필요할 때 간단히 덱(deque)을 사용한다.
데이터의 삭제와 삽입 모두에서 \(O(1)\) 의 시간 복잡도가 소요된다.
덱에 여러 개의 데이터를 삽입하고 삭제하는 예시를 확인해 보자.

직관적 이해: 양쪽 문이 달린 버스와 같다. 앞문이나 뒷문 어느 쪽으로도 탑승(삽입)하고 하차(삭제)할 수 있다. 일반 큐는 뒷문 승차·앞문 하차만 가능하지만, 덱은 양쪽 모두 자유롭다.

동작 원리 (시각화):

초기:   front → [1]→[2]→[3] ← rear

appendleft(0):  front → [0]→[1]→[2]→[3] ← rear
append(4):      front → [0]→[1]→[2]→[3]→[4] ← rear
popleft():      front → [1]→[2]→[3]→[4] ← rear  (0 반환)
pop():          front → [1]→[2]→[3] ← rear        (4 반환)

2 왜 필요한가

양방향에서 삽입/삭제가 모두 \(O(1)\) 에 가능하여 스택과 큐를 동시에 대체할 수 있다.
슬라이딩 윈도우 문제에서 덱을 활용하면 효율적인 최솟값/최댓값 관리가 가능하다.
BFS 구현 시 파이썬에서 리스트 대신 덱을 사용하면 popleft가 \(O(1)\) 에 동작한다.
회문(palindrome) 검사, 좌우 대칭 연산에 자연스럽게 적용된다.

[12개의 전체 연산]

좌측으로부터 삽입 연산이 가능
우측으로부터 삽입 연산이 가능
삭제 연산시 우측/좌측 선택적 삭제가 가능

3 덱(Deque)의 시간 복잡도

데이터의 삭제와 삽입 모두에서 \(O(1)\) 의 시간 복잡도가 소요된다.

표 1: a list of the deque functions in Python

Number	Methods	Time Complexity	Description
1	append left	\(O(1)\)	덱의 가장 왼쪽에 새 데이터를 삽입
2	pop left	\(O(1)\)	덱의 가장 왼쪽에서 데이터를 추출
3	append right	\(O(1)\)	덱의 가장 오른쪽에 새 데이터를 삽입
4	pop right	\(O(1)\)	덱의 가장 오른쪽에서 데이터를 추출

See 표 1.

4 파이썬의 덱(Deque) 라이브러리

Python에서는 덱(deque) 라이브러리를 사용할 수 있다.
아래의 모든 메서드는 최악의 경우 시간 복잡도 \(O(1)\) 을 보장한다.
우측 삽입: append()
좌측 삽입: appendleft()
우측 추출: pop()
좌측 추출: popleft()

Python의 collections.deque를 사용하면 양쪽 삽입/삭제를 모두 \(O(1)\) 에 처리할 수 있다.

from collections import deque


d = deque()
arr = [5, 6, 7, 8] 
for x in arr:
    d.append(x) # 오른쪽 삽입
arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x) # 좌측 삽입
print(d)

while d:
    print(d.popleft()) # 좌측 삭제

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
print(d)

while True:
    print(d.pop())
    if not d:
        break
    print(d.popleft())
    if not d:
        break
# 출력:
# deque([1, 2, 3, 4, 5, 6, 7, 8])
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8
# deque([8, 7, 6, 5, 4, 3, 2, 1])
# 1
# 8
# 2
# 7
# 3
# 6
# 4
# 5

4.1 Python에서 Deque을 사용하는 경우

기본적인 Python의 리스트 자료형은 큐(queue)의 기능을 제공하지 않는다.
가능하다면 Python에서 제공하는 덱(deque) 라이브러리를 사용한다.
큐(queue)의 기능이 필요할 때는 덱 라이브러리를 사용하는 것을 추천한다.
삽입과 삭제에 대하여 모두 시간 복잡도 \(O(1)\) 이 요구된다.

5 연결 리스트로 덱 구현하기

덱(deque)을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 \(O(1)\) 을 보장할 수 있다.
연결 리스트로 구현할 때는 앞(front)과 뒤(rear) 두 개의 포인터를 가진다.
앞(front): 가장 좌측에 있는 데이터를 가리키는 포인터
뒤(rear): 가장 우측에 있는 데이터를 가리키는 포인터
삽입과 삭제의 구현 방법은 스택 및 큐와 유사하다.
앞(front)과 뒤(rear)에 대하여 대칭적으로 로직이 구현될 수 있다.

5.1 좌측 삽입 연산

좌측 삽입할 때는 앞(front) 위치에 데이터를 넣는다.
새로운 데이터가 삽입되었을 때 front data와 연결이 먼저 된 후 front data의 이전 노드가 새로운 데이터가 되도록 설정

5.2 좌측 삭제 연산

삭제할 때는 앞(front) 위치에서 데이터를 꺼낸다. 즉, 그냥 front를 그 다음 데이터로 설정하면 됨

아래 코드는 이중 연결 리스트(doubly linked list)로 덱을 직접 구현한다. 각 노드가 prev와 next 두 포인터를 가져 양쪽 탐색이 가능하다.


class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def appendleft(self, data):
        node = Node(data)
        if self.front == None:
            self.front = node
            self.rear = node
        else:
            node.next = self.front
            self.front.prev = node
            self.front = node
        self.size += 1

    def append(self, data):
        node = Node(data)
        if self.rear == None:
            self.front = node
            self.rear = node
        else:
            node.prev = self.rear
            self.rear.next = node
            self.rear = node
        self.size += 1

    def popleft(self):
        if self.size == 0:
            return None
        # 앞에서 노드 꺼내기
        data = self.front.data
        self.front = self.front.next
        # 삭제로 인해 노드가 하나도 없는 경우
        if self.front == None:
            self.rear = None
        else:
            self.front.prev = None
        self.size -= 1
        return data

    def pop(self):
        if self.size == 0:
            return None
        # 뒤에서 노드 꺼내기
        data = self.rear.data
        self.rear = self.rear.prev
        # 삭제로 인해 노드가 하나도 없는 경우
        if self.rear == None:
            self.front = None
        else:
            self.rear.next = None
        self.size -= 1
        return data

    def front(self):
        if self.size == 0:
            return None
        return self.front.data

    def rear(self):
        if self.size == 0:
            return None
        return self.rear.data

    # 앞에서부터 원소 출력
    def show(self):
        cur = self.front
        while cur:
            print(cur.data, end=" ")
            cur = cur.next


d = Deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)
arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
d.show()

print()
while d.size != 0:
    print(d.popleft())

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
d.show()

print()
while True:
    print(d.pop())
    if d.size == 0:
        break
    print(d.popleft())
    if d.size == 0:
        break
# 출력:
# 1 2 3 4 5 6 7 8
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8
# 8 7 6 5 4 3 2 1
# 1
# 8
# 2
# 7
# 3
# 6
# 4
# 5

핵심 포인트

BFS 구현 시 list.pop(0) 대신 deque.popleft()를 반드시 사용한다 (\(O(N)\) → \(O(1)\)).
슬라이딩 윈도우 최대/최소: 단조 덱(monotone deque)으로 \(O(N)\) 구현이 가능하다.
deque(maxlen=k) 옵션을 사용하면 크기 제한 덱을 만들 수 있다 (이동 평균 계산에 유용).

6 응용 분야

BFS 탐색: popleft()로 FIFO 처리하여 레벨 단위 탐색을 구현한다.
슬라이딩 윈도우 최솟값/최댓값: 단조 덱으로 구간 내 최솟값을 \(O(N)\) 에 유지한다.
작업 스케줄링: 양쪽에서 우선순위 높은 작업을 빠르게 꺼낼 수 있다.
텍스트 에디터 커서 이동: 커서 앞뒤 텍스트를 두 스택(덱)으로 분리하여 \(O(1)\) 삽입/삭제를 구현한다.
이동 평균(Moving Average): maxlen 덱으로 최근 k개 데이터만 유지하여 계산한다.