---
title: "덱: 양쪽 끝을 모두 사용할 때 생기는 선택지"
author: "Lee"
published_at: "2026-10-14T04:59:04.568Z"
updated_at: "2026-09-30T09:27:33.542Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%8D%B1-%EC%96%91%EC%AA%BD-%EB%81%9D%EC%9D%84-%EB%AA%A8%EB%91%90-%EC%82%AC%EC%9A%A9%ED%95%A0-%EB%95%8C-%EC%83%9D%EA%B8%B0%EB%8A%94-%EC%84%A0%ED%83%9D%EC%A7%80"
ai_assisted: false
---

# 덱: 양쪽 끝을 모두 사용할 때 생기는 선택지

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%8D%B1-%EC%96%91%EC%AA%BD-%EB%81%9D%EC%9D%84-%EB%AA%A8%EB%91%90-%EC%82%AC%EC%9A%A9%ED%95%A0-%EB%95%8C-%EC%83%9D%EA%B8%B0%EB%8A%94-%EC%84%A0%ED%83%9D%EC%A7%80)

덱은 양쪽 끝에서 원소를 넣고 뺄 수 있는 자료형이다. 이름은 double-ended queue에서 왔으며 양끝 큐라고도 한다. 앞 추가, 뒤 추가, 앞 제거, 뒤 제거라는 네 연산을 제공하므로 한쪽만 사용하면 스택, 양쪽을 다른 역할로 사용하면 큐가 된다.

![덱의 앞과 뒤에서 각각 원소를 넣고 꺼내는 두 끝의 연산](/api/v1/media/87fd5b9c-de79-43fb-90b9-2ebdb42e547f)

*덱은 양 끝의 삽입과 삭제를 모두 지원한다.*

### 양끝 연산과 임의 접근은 다르다

[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 이하라는 점이 분석의 근거다.

덱의 기능이 많다고 모든 문제에서 가장 좋은 선택은 아니다. 순수 스택이나 큐는 더 간단한 계약을 줄 수 있고, 가운데 삽입·검색에는 다른 구조가 맞을 수 있다. 양끝에서 어떤 상태를 유지할지 명확히 정의할 때 덱의 유연성이 실제 이점이 된다.

### 후보의 뒤쪽을 제거하는 규칙

```text
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]
```

가득 찬 첫 구간이 만들어지기 전에는 답을 출력하지 않는다. 뒤에서 작은 값을 제거하는 기준을 <=로 두면 같은 값 중 더 늦게 만료될 새 원소를 남긴다. <로 두고 동률을 모두 남겨도 올바른 결과를 얻을 수 있지만 후보 상태는 달라진다. 각 인덱스의 수명과 값의 단조 순서가 함께 유지되어야 한다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)
- [Princeton · Algorithms, 4th edition · Stacks and Queues](https://algs4.cs.princeton.edu/13stacks/)