덱은 양 끝에서 원소를 넣고 꺼낼 수 있는 양방향 큐이다. 스택과 큐의 접근 방식을 함께 표현할 수 있다.
원리
원형 배열이나 이중 연결 리스트로 구현한다. 양 끝 연산을 효율적으로 지원한다는 뜻이며, 중간 원소 검색이나 임의 위치 삽입까지 항상 빠르다는 뜻은 아니다.
예시
최근 본 항목을 앞에 넣고 오래된 항목을 뒤에서 제거할 수 있다. 슬라이딩 윈도의 최댓값을 유지하는 단조 덱은 순서 조건을 추가로 관리하는 응용이다.
주의할 점
자료구조마다 인덱스 접근과 확장 비용이 다르다. 이름이 비슷한 dequeue는 큐에서 꺼내는 연산이고, deque는 양방향 큐 자체를 가리킨다.