덱: 양쪽 끝을 모두 사용할 때 생기는 선택지
덱은 양쪽 끝에서 원소를 넣고 뺄 수 있는 자료형이다. 이름은 double-ended queue에서 왔으며 양끝 큐라고도 한다. 앞 추가, 뒤 추가, 앞 제거, 뒤 제거라는 네 연산을 제공하므로 한쪽만 사용하면 스택, 양쪽을 다른 역할로 사용하면 큐가 된다.
덱은 양 끝의 삽입과 삭제를 모두 지원한다.
양끝 연산과 임의 접근은 다르다
[A,B,C]의 앞에 X를 넣으면 [X,A,B,C], 뒤에서 빼면 C가 반환되어 [X,A,B]가 남는다. 이 규칙은 가운데 i번째 원소에 O(1)로 접근할 수 있다는 보장까지 포함하지 않는다. 원형 배열 구현은 임의 접근이 가능할 수 있지만 연결 기반 덱은 순회가 필요하다.
원형 배열 덱은 앞·뒤 인덱스를 모듈러 연산으로 이동시킨다. 이중 연결 리스트는 양끝 노드에 직접 접근하여 연결을 갱신한다. 확장 가능한 구현에서는 가득 찼을 때 재할당 비용이 있고, 고정 용량 구현에서는 실패나 덮어쓰기 정책이 필요하다.
윈도 최댓값에 덱을 쓰는 이유
길이 k인 구간이 오른쪽으로 이동할 때 매번 모든 원소를 살피면 O(nk)가 걸린다. 덱에 최댓값 후보의 인덱스를 넣고, 앞에는 가장 오래된 후보, 뒤에는 가장 새 후보를 놓을 수 있다. 후보 값이 앞에서 뒤로 감소하도록 유지한다.
[4,2,5,3]에서 길이 3 구간을 보자. 4와 2는 후보로 들어간다. 5가 도착하면 뒤의 2와 4는 제거한다. 새 값 5가 더 크고 더 늦게 만료되므로 이 두 값이 앞으로 최댓값이 될 가능성이 없다. 덱에는 인덱스 2만 남고 첫 구간 최댓값은 5다.
다음 3이 도착하면 뒤에 추가한다. 구간 밖으로 나간 인덱스는 앞에서 제거하고 현재 앞 원소의 값을 답으로 사용한다. 인덱스를 저장해야 값이 같은 원소들도 만료 시점을 구별할 수 있다. 동률 제거 정책은 일관되게 정하면 된다.
한 원소는 한 번 들어가고 많아야 한 번 나가므로 총시간은 O(n), 공간은 O(k)다. 한 단계에서 여러 원소가 제거될 수 있어도 전체 제거 횟수가 n 이하라는 점이 분석의 근거다.
덱의 기능이 많다고 모든 문제에서 가장 좋은 선택은 아니다. 순수 스택이나 큐는 더 간단한 계약을 줄 수 있고, 가운데 삽입·검색에는 다른 구조가 맞을 수 있다. 양끝에서 어떤 상태를 유지할지 명확히 정의할 때 덱의 유연성이 실제 이점이 된다.
후보의 뒤쪽을 제거하는 규칙
for each index i:
remove front indices smaller than i - k + 1
while deque is not empty and value[back] <= value[i]:
remove back
append i to back
if i >= k - 1:
emit value[front]
가득 찬 첫 구간이 만들어지기 전에는 답을 출력하지 않는다. 뒤에서 작은 값을 제거하는 기준을 <=로 두면 같은 값 중 더 늦게 만료될 새 원소를 남긴다. <로 두고 동률을 모두 남겨도 올바른 결과를 얻을 수 있지만 후보 상태는 달라진다. 각 인덱스의 수명과 값의 단조 순서가 함께 유지되어야 한다.