양방향 큐, 덱(Deque) 핵심정리 (구조, 활용사례)

소프트웨어 개발과 알고리즘 최적화 과정에서 자료구조(Data Structure)의 올바른 선택은 시스템 성능을 좌우하는 결정적인 요소입니다. 흔히 사용하는 스택(Stack)은 후입선출(LIFO), 큐(Queue)는 선입선출(FIFO)이라는 고정된 입출력 방식을 가지고 있어 특정 상황에서는 유연성이 떨어질 수 있습니다. 이러한 한계를 극복하기 위해 고안된 것이 바로 덱(Deque, Double-Ended Queue)입니다. 덱은 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 하이브리드 자료구조로, 복잡한 스케줄링이나 슬라이딩 윈도우(Sliding Window) 알고리즘 등에서 필수적으로 사용됩니다. 이 글에서는 덱의 구조적 특징과 시간 복잡도, 그리고 실제 개발 환경에서의 활용 사례를 심층적으로 분석합니다.

1. 덱(Deque)의 핵심 구조와 작동 원리

Deque는 'Double-Ended Queue'의 약자로, 이름 그대로 양쪽 끝(Front, Rear)에서 삽입과 삭제가 모두 가능한 자료구조를 의미합니다. 이는 스택과 큐의 장점을 결합한 형태로 볼 수 있으며, 개발자의 의도에 따라 스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있는 높은 유연성을 제공합니다.

1-1. 스택 및 큐와의 비교 분석

자료구조를 이해할 때는 기존 개념과의 비교가 가장 효과적입니다.

스택(Stack): 한쪽 끝(Top)에서만 삽입/삭제가 발생합니다. (LIFO 구조)
큐(Queue): 한쪽(Rear)에서는 삽입, 다른 한쪽(Front)에서는 삭제만 발생합니다. (FIFO 구조)
덱(Deque): Front와 Rear 양쪽 모두에서 삽입(`push_front`, `push_back`)과 삭제(`pop_front`, `pop_back`)가 가능합니다.

1-2. 메모리 구조와 구현 방식

덱은 물리적으로 두 가지 방식으로 구현될 수 있습니다.

이중 연결 리스트(Doubly Linked List): 각 노드가 이전(Prev)과 다음(Next) 노드의 주소를 가지고 있어, 양쪽 끝에서의 접근이 O(1)로 매우 빠릅니다. 동적 메모리 할당에 유리합니다.
원형 버퍼(Circular Buffer): 고정된 크기의 배열을 사용하며, 양 끝 인덱스를 관리하여 오버헤드를 줄입니다. 메모리 사용이 효율적입니다.

2. 덱을 사용해야 하는 이유: 시간 복잡도(Big-O)

많은 입문자가 "파이썬의 리스트(List)나 자바의 ArrayList로도 양쪽 데이터를 다룰 수 있는데, 굳이 덱을 써야 하는가?"라는 의문을 가집니다. 이에 대한 명확한 해답은 시간 복잡도에 있습니다.

2-1. O(1) vs O(n)의 성능 차이

일반적인 리스트(배열) 기반의 자료구조에서 가장 앞쪽의 데이터(Index 0)를 삭제하거나 삽입하는 경우, 뒤에 있는 모든 데이터를 한 칸씩 이동(Shift)시켜야 하는 오버헤드가 발생합니다. 이 경우 시간 복잡도는 O(n)이 됩니다.

반면, 덱(Deque)은 양쪽 끝의 요소에 접근하고 수정하는 데 최적화되어 있어, 데이터의 양(n)과 상관없이 O(1)의 일정한 시간 복잡도를 보장합니다. 대용량 데이터를 처리하는 큐 프로세스나 알고리즘 문제 풀이에서 덱이 필수적인 이유가 바로 이 성능 차이 때문입니다.

3. 주요 활용 사례 및 기술적 구현 (Python)

덱은 단순한 데이터 저장을 넘어, 특정 알고리즘의 효율성을 극대화하는 데 사용됩니다.

3-1. 실제 활용 시나리오

슬라이딩 윈도우(Sliding Window): 고정된 크기의 창을 이동시키며 최댓값이나 최솟값을 찾을 때, 덱을 이용하면 윈도우 갱신을 O(1)로 처리할 수 있습니다.
웹 브라우저의 방문 기록: '뒤로 가기'와 '앞으로 가기' 기능을 구현할 때 스택 두 개 혹은 덱 하나로 관리할 수 있습니다.
작업 스케줄링(Scheduling): 우선순위가 높은 작업은 앞에 넣고(`push_front`), 일반 작업은 뒤에 넣는(`push_back`) 방식의 유연한 스케줄링이 가능합니다.
회문(Palindrome) 판별: 문자열의 앞과 뒤를 동시에 비교하며 좁혀가는 로직에 적합합니다.

3-2. Python `collections.deque` 구현 예제

파이썬에서는 `collections` 모듈의 `deque`를 사용하여 효율적으로 구현할 수 있습니다. 스레드 안전(Thread-Safe)하며 리스트보다 월등한 성능을 보입니다.


from collections import deque

# 덱 생성
d = deque([1, 2, 3])

# 1. 뒤쪽(Rear) 조작 - O(1)
d.append(4)        # [1, 2, 3, 4]
d.pop()            # 4 반환, 현재: [1, 2, 3]

# 2. 앞쪽(Front) 조작 - O(1) -> 리스트보다 훨씬 빠름
d.appendleft(0)    # [0, 1, 2, 3]
d.popleft()        # 0 반환, 현재: [1, 2, 3]

# 3. 회전 (Rotate) - 유용한 기능
# 양수면 시계 방향(오른쪽), 음수면 반시계 방향
d.rotate(1)        # [3, 1, 2]
print(f"Rotated Deque: {d}")

[핵심 요약 : 덱(Deque) 완전 정복]
1. 정의: 양쪽 끝(Front, Rear) 모두에서 삽입과 삭제가 가능한 하이브리드 자료구조입니다.
2. 성능 우위: 리스트의 앞쪽 데이터 처리 시 발생하는 O(n) 비용을 O(1)로 단축시킵니다.
3. 활용: 슬라이딩 윈도우, 스케줄링, 회문 판별 등 양방향 데이터 처리가 필요한 고성능 알고리즘에 필수적입니다.

kguidebook0001 님의 블로그