티스토리 뷰
목차
스택(Stack)은 "나중에 들어온 놈이 먼저 나간다(LIFO)", 큐(Queue)는 "먼저 들어온 놈이 먼저 나간다(FIFO)"는 엄밀하고 꽉 막힌 규칙을 가지고 있습니다. 하지만 현실 세계의 문제, 예를 들어 놀이공원 줄을 서는데 VIP가 새치기를 하거나, 줄 맨 뒤에서 기다리다 지친 사람이 포기하고 나가는 복잡한 상황을 모델링하려면 이 둘만으로는 턱없이 부족합니다. 앞으로도 넣고 뺄 수 있으며, 뒤로도 넣고 뺄 수 있는 완전한 자유도를 가진 하이브리드 자료구조가 절실해집니다. 이것이 바로 스택과 큐의 유전자를 완벽하게 융합한 '덱(Deque, Double-Ended Queue)'입니다.
1. 양방향 통행의 절대적 자유 (Front and Rear)
덱은 양쪽 끝이 모두 시원하게 뚫려 있는 원통형 파이프와 같습니다. 데이터를 집어넣을 때 push_front()를 호출하여 맨 앞에 새치기하듯 밀어 넣을 수도 있고, push_back()을 통해 맨 뒤에 점잖게 줄을 세울 수도 있습니다. 데이터를 뺄 때 역시 pop_front()로 맨 앞사람을 빼거나, pop_back()으로 맨 뒷사람을 뺄 수 있습니다. 즉, 알고리즘을 풀다가 스택이 필요하면 앞쪽 입구만 막아버리면 되고, 큐가 필요하면 한쪽으로 넣고 반대쪽으로 빼면 됩니다. 덱 하나만 든든하게 선언해 두면 필요에 따라 완벽한 스택으로도, 완벽한 큐로도 변신할 수 있는 카멜레온 같은 만능 자료구조가 완성됩니다.
2. 언제 덱을 꺼내 들어야 할까? (Sliding Window의 제왕)
단순히 스택과 큐를 합쳐놓은 것만으로는 덱의 진가를 설명할 수 없습니다. 덱이 가장 눈부시게 활약하는 무대는 바로 '슬라이딩 윈도우(Sliding Window)' 최댓값/최솟값 찾기 문제입니다. 길이가 100만 개인 거대한 배열에서, 크기가 10인 창문(Window)을 한 칸씩 오른쪽으로 밀어가며 그 창문 안의 최댓값을 1초 만에 계속 갱신해야 한다고 가정해 봅시다.
2-1. 단조 덱(Monotonic Deque) 테크닉
이때 덱에 데이터의 '인덱스'를 저장하되, "새로운 데이터가 들어올 때, 나보다 작거나 같아서 앞으로 쓸모가 없는 데이터들은 덱의 뒤(Rear)에서 모조리 뽑아 죽여버리고(pop_back), 창문의 범위를 벗어나 수명이 다 된 늙은 데이터는 덱의 앞(Front)에서 방출하는(pop_front)" 잔혹한 최적화 기법을 사용합니다.
이 룰을 지키면 덱의 맨 앞(Front)에는 항상 현재 창문의 최댓값이 $O(1)$의 속도로 왕좌를 차지하고 대기하게 됩니다. 모든 데이터는 덱에 1번 들어가고 1번 나오므로, 전체 배열을 단 한 번 훑는 $O(N)$의 경이로운 시간 복잡도 만에 문제를 박살 낼 수 있습니다. 이 압도적인 최적화 테크닉은 덱의 '양방향 삽입/삭제' 기능이 없었다면 결코 불가능했을 예술입니다.
3. 팰린드롬(회문) 판별기의 정석
"기러기", "토마토", "스위스", "역삼역"처럼 앞으로 읽으나 뒤로 읽으나 똑같은 단어를 팰린드롬(Palindrome)이라고 합니다. 문자열이 팰린드롬인지 검사할 때도 덱은 최고의 무기입니다. 문자열을 덱에 몽땅 집어넣고, "맨 앞 글자와 맨 뒷 글자를 동시에 뽑아서(pop_front, pop_back) 똑같은지 비교"하는 짓을 덱이 텅 빌 때까지 반복하기만 하면 됩니다. 덱의 양방향 추출 특성을 가장 직관적으로 활용하는 사례입니다.
1. 덱(Deque)은 스택(Stack)과 큐(Queue)의 특성을 모두 합쳐, 배열의 양쪽 끝(Front, Rear)에서 데이터의 삽입과 삭제가 모두 $O(1)$에 가능한 만능 하이브리드 자료구조입니다.
2. 양 끝을 자유롭게 제어할 수 있어, 팰린드롬 검사나 최근 사용 기록 관리(Undo/Redo) 등 앞뒤의 데이터가 동시에 필요한 상황에 특화되어 있습니다.
3. 특히 슬라이딩 윈도우(Sliding Window) 내의 최댓값/최솟값을 $O(N)$ 만에 찾아내는 단조 덱(Monotonic Deque) 알고리즘의 핵심 엔진으로 맹활약합니다.