내가 사용하는 STL (4) - 덱 (Deque)

이번에 소개할 STL은 Deque이다. 

Deque

덱 Deque. 간단히 줄여서 dq라고도 한다. 덱은 queue와 stack을 합쳐놓았다고 생각하면 된다. 정확히는 가능한 부분을 더했다고 생각해야 한다. 덱에서는 앞 또는 뒤로 넣고, 앞 또는 뒤로 뺄 수 있다. 즉, 출입의 경우의 수가 4가지가 된다는 것이다. 이는 아래의 그림과 같이 행동한다. 

이와 같이 4가지 행동을 모두 할 수 있는 자료구조이다. 그러면 stack이나 queue를 쓸 바에 무조건 deque을 쓰면 되지 않냐고 생각할 수 있다. 사실 맞는 말이다. 하지만 stack이나 queue가 더 익숙하고, 코드가 더 짧기 때문에 (이 이유가 크다) stack이나 queue를 많이 사용을 한다.

위와 같이 생각을 했었으나 조사를 해보니 deque은 오히려 vector와 비슷한 특성을 가지고 있었다. 문법적인 부분 자체도 오히려 vector와 비슷한 부분을 많이 보여주었다. 

문법

deque<int> dq	int 자료형의 deque dq를 생성한다.
deque<int> dq(5)	int 자료형의 0이 5개 들어있는 deque dq를 생성한다.
deque<int> dq(5,3)	int 자료형의 3이 5개 들어있는 deque dq를 생성한다
dq[x]	dq의 x번째 원소를 참조한다.
dq.clear()	dq를 초기화 시킵니다.
dq.front()	dq의 가장 앞에 있는 원소 반환
dq.back()	dq의 가장 뒤에 있는 원소 반환
dq.push_front(x)	dq의 앞에 x를 삽입한다.
dq.push_back(x)	dq의 뒤에 x를 삽입한다.
dq.pop_front()	dq의 가장 앞의 원소를 삭제한다
dq.pop_back()	dq의 가장 뒤의 원소를 삭제한다
for(auto k:dq)	dq에 있는 모든 원소를 순서대로 k가 되어 for문을 실행
dq.size()	dq안에 있는 원소의 갯수 반환
dq.empty()	dq가 비어있는지 판별

사용

위에서도 언급했지만, dq를 많이 사용해 본 적이 없었다. 기본적으로 코드의 길이가 길어서 앞뒤로 모두 삽입과 삭제가 필요할때만 사용을 했었다. 그래서 랜덤 위치 참조가 O(1)만에 이루어질 수 있다는 사실을 처음 알게 되었다. 사실 그래도 많이 이용할지는 모르겠다.

Monotone Queue Technique

어떤 값들을 sweeping 하면서 queue에 넣는데, 이때 queue를 Monotone하게 관리하는 technique이다. 이를 구현할 때 주로 deque을 사용한다. Monotone queue Technique에 대해서 좀 더 자세히 알고 싶으면 이 글을 참고하면 된다.