21. C++ STL deque이란

★ deque

  vector는 뒤에서만 추가하고 삭제할 수 있지만, deque(덱)은 앞과 뒤 모두 추가와 삭제가 가능하다. 그림으로 표현하면 다음과 같다.

C++ STL  deque

  deque은 <deque>를 #include 하고 사용해야한다. 컨테이너 기본 연산 외에 deque 연산은 다음과 같다.

연산	동작
deque c	빈 덱 생성
deque c(c1)	c1 덱의 원소를 복사하면서 생성
deque c(n)	n개의 원소를 생성
deque c(n, elem)	n개의 원소를 elem 값으로 초기화하면서 생성
deque c(beg, end)	beg 부터 end-1 까지의 원소를 복사하면서 생성
swap(c1, c2)	c1과 c2를 교환
c.at(idx)	idx 위치의 원소를 얻어온다. 범위 벗어나면 에러 발생
c[idx]	idx 위치의 원소를 얻어온다. 범위 검사 하지 않는다.
c.front()	첫 번째 원소
c.back()	마지막 원소
c.push_back(elem)	마지막에 elem을 추가
c.pop_back(elem)	마지막 원소를 제거
c.push_front(elem)	처음에 elem을 추가
c.pop_front()	첫 번째 원소 제거
c.resize(n)	벡터 크기를 n으로 변경한다.
c.resize(n, elem)	이전 크기보다 늘어나면, 늘어나는 것만 elem으로 초기화하면서 크기를 n으로 변경한다.

 

deque은 앞 뒤로 들어나기 때문에 메모리를 미리 예약할 수 없다. 따라서, vector에서는 제공되는 reserve() 함수가 제공되지 않는다.

 

  vector와 달리 앞에 추가하고 삭제하는 push_front()와 pop_front() 함수가 제공된다. 따라서 큐에서 삽입할 때는 push_back()을 사용하고, 삭제할 때는 pop_front()를 사용하여 구현할 수 있다. 삭제되면 자동으로 메모리가 관리되므로 메모리가 낭비되지 않는다. deque을 사용한 예제를 살펴보자.

 

#include <stdio.h>
#include <deque>
using namespace std;
int main()
{
	int i;
	deque<int> ss;

	ss.push_back(3);  //데이터의 마지막에 삽입
	ss.push_back(4);
	ss.push_back(6);
	ss.push_back(9);
	ss.push_back(12);

	for(i=0;i<ss.size(); i++)  //배열식으로 출력
		printf("%d ", ss[i]);
	printf("\n");

	ss.pop_back();  //뒤쪽에서 하나를 삭제한다.
	ss.pop_front(); //앞쪽에서 하나를 삭제한다.

	ss.push_front(34); //2개를 앞쪽에서 삽입한다.
	ss.push_front(38);

	for(i=0;i<ss.size(); i++)  //배열식으로 출력
		printf("%d ", ss[i]);
	printf("\n");
	return  0;
}

 

[ 문제 1 ] www.acmicpc.net/problem/10866

10866번: 덱