Deque

contents

데크(Deque) 는 "덱"이라고 발음하며, Double-Ended Queue(양방향 큐) 의 약자입니다. 양쪽 끝(머리-front/head와 꼬리-rear/tail) 에서 요소를 추가하거나 제거할 수 있는 선형 자료 구조입니다.

이는 스택(후입선출, LIFO)과 큐(선입선출, FIFO)라는 두 가지 기본 자료 구조의 기능을 모두 일반화한 유연한 구조입니다.

데크 vs. 스택 및 큐

데크는 다른 두 가지 기본 구조의 상위 집합으로 간주됩니다.

데크는 연산을 제한함으로써 둘 중 하나를 흉내 낼 수 있습니다.

• 스택처럼: addFirst와 removeFirst만 사용.
• 큐처럼: addLast와 removeFirst만 사용.

핵심 연산 및 메서드

데크 메서드는 일반적으로 **앞(머리)**에서 작동하는지 **뒤(꼬리)**에서 작동하는지에 따라 분류되며, 연산이 실패할 경우 예외를 던질지(add/remove) 특별한 값을 반환할지(offer/poll)에 따라 구분됩니다.

• 참고: 자바에서 push()(스택의 푸시)와 같은 메서드는 addFirst()에 매핑되고, pop()(스택의 팝)과 같은 메서드는 removeFirst()에 매핑됩니다.

구현 방식 및 시간 복잡도 ⏱️

잘 설계된 데크 구현의 목표는 데크 크기에 관계없이 모든 삽입 및 삭제 연산이 **$O(1)$ (상수 시간)**에 실행되도록 보장하는 것입니다.

1. 이중 연결 리스트 구현 (가장 일반적)

데크를 구축하는 가장 유연하고 일반적인 방법입니다.

• 구조: 각 노드는 다음 요소와 이전 요소를 가리키는 포인터를 포함합니다. 데크 자체는 head와 tail 모두에 대한 직접적인 포인터를 유지합니다.
• 이중 연결 리스트를 사용하는 이유: 단일 연결 리스트를 사용하면 마지막 요소를 제거(removeLast)할 때 끝에서 두 번째 요소를 찾기 위해 전체 리스트를 순회해야 하므로 $O(n)$ 연산이 됩니다. 이중 연결 구조는 이를 방지합니다.
• 복잡도: 네 가지 주요 연산(addFirst, removeFirst, addLast, removeLast) 모두 head와 tail 포인터를 업데이트하는 작업만 포함하므로 $O(1)$ 시간 복잡도를 달성합니다.

2. 배열 기반 구현 (원형 배열)

배열을 사용할 수도 있지만, 원형 배열로 관리되어야 합니다.

• 구조: 배열을 링처럼 취급하여, front 포인터가 배열의 시작 부분이 가득 찼을 때 배열의 끝으로 돌아갈 수 있도록 합니다.
• 원형 배열을 사용하는 이유: 앞에서 항목을 추가하거나 제거할 때 모든 요소를 이동할 필요가 없도록 하기 위함입니다(이는 $O(n)$ 시간이 걸림).
• 복잡도: 양쪽 끝에서의 삽입 및 삭제는 $O(1)$ 시간 복잡도입니다. 하지만 배열이 가득 찼을 때 기본 배열의 크기를 재조정하는 것은 여전히 $O(n)$ 연산입니다.

실제 사용 사례

데크의 유연한 특성은 복잡한 알고리즘 문제와 시스템 설계에 적합합니다.

1. 슬라이딩 윈도우 알고리즘 (대표적인 용도): 고정된 크기의 슬라이딩 윈도우 내에서 최소값 또는 최대값을 찾는 문제를 해결할 때, 데크는 인덱스(값이 아님)를 오름차순 또는 내림차순으로 저장하는 데 사용됩니다. 이를 통해 각 단계에서 최소값/최대값을 $O(1)$ 시간에 찾을 수 있어, 전체적으로 $O(n)$ 해법을 달성합니다.
2. 실행 취소/재실행 (Undo/Redo) 기능: 데크를 사용하여 명령 기록을 관리할 수 있습니다. "실행 취소"는 한쪽 끝에서 작업을 꺼내고(pop), 반대쪽 끝(데크의 뒤쪽)의 "재실행" 스택에 넣습니다(push).
3. 작업 스케줄링 (작업 훔치기): 병렬 처리에서 한 워커 스레드가 작업이 부족할 때, 다른 워커의 데크 꼬리 부분에서 작업을 "훔칠" 수 있습니다. 이는 작업 훔치기(work stealing) 라고 불리며 작업 부하의 균형을 맞추는 데 도움이 됩니다.
4. 팰린드롬 (회문) 및 괄호 매칭: 데크는 앞에서부터와 뒤에서부터 동시에 제거/검사가 가능하여 단어가 팰린드롬인지 확인하는 등의 문제에 이상적입니다.

references