데이터를 관리하는 가장 기본적인 방식인 스택(Stack)과 큐(Queue)는 프로그래밍의 기초 중의 기초입니다. 하지만 실제 복잡한 알고리즘을 구현하다 보면, 한쪽 방향에서만 데이터를 넣고 빼는 제약이 오히려 효율성을 저해하는 상황을 마주하게 됩니다. 이때 등장하는 것이 바로 덱(Deque, Double Ended Queue)입니다. 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 유연한 구조를 가지고 있어, 스택과 큐의 장점을 모두 취한 '하이브리드' 자료구조라고 할 수 있습니다. 오늘 이 글에서는 덱의 내부 동작 원리와 실제 활용 사례를 심도 있게 분석해 보겠습니다.
1. 덱(Deque)의 개념과 구조적 특징
덱은 이름 그대로 'Double Ended Queue'의 약자로, 양방향에서 데이터 입출력이 가능한 선형 자료구조입니다. 일반적인 큐가 FIFO(First-In-First-Out)를 따르고, 스택이 LIFO(Last-In-First-Out)를 따르는 것과 달리, 덱은 구현 방식에 따라 스택처럼 사용할 수도, 큐처럼 사용할 수도 있습니다.
1-1. 덱의 주요 연산 모음
- push_front: 덱의 앞부분에 데이터를 삽입합니다.
- push_back: 덱의 뒷부분에 데이터를 삽입합니다.
- pop_front: 덱의 앞부분에 있는 데이터를 삭제하고 반환합니다.
- pop_back: 덱의 뒷부분에 있는 데이터를 삭제하고 반환합니다.
- peek_front / peek_back: 데이터를 삭제하지 않고 앞뒤의 값을 확인합니다.
2. 덱의 내부 구현 원리: 배열 vs 연결 리스트
덱을 구현하는 방식은 크게 두 가지로 나뉩니다. 첫 번째는 가변 배열(Dynamic Array)을 사용하는 방식이고, 두 번째는 이중 연결 리스트(Doubly Linked List)를 사용하는 방식입니다.
2-1. 이중 연결 리스트 방식
각 노드가 이전 노드와 다음 노드의 주소를 모두 가지고 있는 구조입니다. 양방향 포인터를 활용하기 때문에 삽입과 삭제가 항상 O(1)의 시간 복잡도를 보장한다는 강력한 장점이 있습니다. 메모리 할당이 불연속적으로 일어나므로 중간에 데이터를 삽입하는 작업은 없지만, 양 끝단 작업에서는 가장 안정적인 성능을 보여줍니다.
2-2. 원형 배열 방식
고정된 크기의 배열을 원형으로 연결하여 인덱스를 관리하는 방식입니다. 메모리 지역성(Locality) 측면에서 연결 리스트보다 우수하여 캐시 효율이 높습니다. 다만, 배열의 크기가 꽉 찼을 때 발생하는 Resizing(크기 재조정) 비용이 발생할 수 있다는 점을 유의해야 합니다.
3. 덱은 언제 활용되는가?
덱은 단순한 이론적 구조에 그치지 않고 실무 알고리즘에서 매우 빈번하게 사용됩니다. 가장 대표적인 사례는 슬라이딩 윈도우(Sliding Window) 알고리즘입니다. 특정 구간 내의 최댓값이나 최솟값을 구할 때, 구간을 벗어난 데이터는 앞에서 빼고 새로운 데이터는 뒤로 넣는 과정에서 덱이 최적의 성능을 발휘합니다.
// Python의 collections.deque를 활용한 간단한 예시
from collections import deque
d = deque([1, 2, 3])
d.appendleft(0) # 앞쪽 삽입
d.append(4) # 뒤쪽 삽입
print(d.popleft()) # 앞쪽 삭제 -> 0 반환
print(d.pop()) # 뒤쪽 삭제 -> 4 반환
1. 양방향 입출력: 스택과 큐의 기능을 동시에 수행할 수 있는 유연한 자료구조입니다.
2. 성능 최적화: 양 끝단의 삽입 및 삭제 연산은 O(1)의 시간 복잡도를 가집니다.
3. 다양한 응용: 슬라이딩 윈도우, 데이터 스케줄링, 브라우저 방문 기록 관리 등에 필수적입니다.