4. Deque

deque(덱)은 벡터와 유사한 시퀀스 컨테이너이며 벡터에 비해 추가적인 기능이 더 있다. 헤더파일 <deque>를 인클루드하면 사용할 수 있고, <deque>에서 인클루드하는 헤더파일 <bits/stl_deque.h>에 deque 클래스가 정의되어 있다.

 

덱의 선언 방법은 기본적으로 벡터의 선언 방법과 같고, 이전 글에서 설명한 다섯 가지 선언 방법을 덱에도 그대로 적용할 수 있다. 연산자 역시 벡터에서 설명한 것과 같이 C 문법에 존재하는 $6$가지 비교, 동등 연산자와 <=>, []까지 $8$가지의 연산자를 쓸 수 있다.

 

멤버 함수는 deque와 vector에서 약간의 차이가 있다. deque는 Double Ended Queue의 줄임말로 이름에서 알 수 있듯이 앞쪽에도 원소를 추가할 수 있기 때문에 이와 관련된 추가적인 멤버 함수가 존재한다. deque의 멤버 함수 중 이전 글에 나오지 않은 것들은 다음과 같다.

d.push_front(x);	d의 맨 앞에 x를 추가한다.
d.pop_front();	d의 첫 번째 원소를 삭제한다.
d.emplace_front(x);	d의 맨 앞에 x를 추가한다.

이 세 함수와 vector의 내장 함수들이 deque에 내장되어 있지만, deque은 vector와 메모리 할당 방식이 달라 용량의 개념이 존재하지 않으므로 deque::capacity, deque::reserve 같은 함수는 존재하지 않는다. deque::shrink_to_fit 함수는 존재하지만 의미는 vector::shrink_to_fit 함수와 약간 다르다.

 

벡터와 덱의 메모리 할당 방식이 어떻게 다른지는 여기에서 잘 설명하고 있다.

 

벡터와 다르게 덱은 이것을 이용하는 알고리즘이 존재한다. 후에 설명할 덱을 이용한 DP나 0-1 BFS가 그 예시이다.

 

[연습문제]

 

BOJ 10866. 덱 (Silver IV)

덱 연습 문제이다. 주어지는 입력에 맞게 동작하도록 멤버 함수를 호출하면 된다.

 

→ solved.ac tag: deque