반응형

 

덱(Deque)이란?

STL 컨테이너 라이브러리 중 하나인 Deque(Double Ended Queue) 덱은 큐(Queue)와 비슷하지만 큐와 다르게 삽입과 삭제가 앞, 뒤 양쪽으로 모두 가능합니다.

  • 덱의 삽입과 삭제는 양쪽 끝(앞, 뒤)에서 이루어진다.
  • 크기가 가변적이다.
  • 인덱스가 존재하기 때문에 임의의 원소에 접근이 가능하다. 

덱의 자료구조

 

덱의 멤버 함수

  • dq.begin() : dq의 첫 번째 원소를 가리키는 iterator

  • dq.end() : dq의 마지막 원소를 가리키는 iterator

  • dq.front() : dq의 첫 번째 원소

  • dq.back() : dq의 마지막 원소

  • dq.at(n) : dq의 n번째 원소

  • dq.assign(n) : 원소 n개를 0으로 초기화

  • dq.assign(n,1) : 원소 n개를 1로 초기화

  • dq.push_front(x) : dq의 첫 번째 원소에 'x' 추가

  • dq.push_back(x) : dq의 마지막 원소에 'x' 추가

  • dq.pop_front() : dq의 첫 번째 원소 삭제

  • dq.pop_back() : dq의 마지막 원소 삭제

  • dq.size() : dq의 원소 개수 리턴

  • dq.resize(m) : dq의 메모리 공간 크기를 m으로 변경하고 늘어난 부분은 0으로 초기화

  • dq.clear() : dq 전체 원소 clear!

  • dq.insert(iterator, x) : iterator가 가리키는 위치에 원소 'x' 삽입
    (기존 원소들은 한 칸씩 뒤로 밀려난다.)

  • dq.erase(iterator) : iterator가 가리키는 위치의 dq원소를 삭제

 

 

예제 코드

#include<iostream>
#include<deque>
using namespace std;

int N;
deque<int> dq;

void print_dq()
{
	cout << "dq의 원소 : ";
	for (int i = 0; i < dq.size(); i++)
		cout << dq.at(i) << " ";
}

int main()
{
	cout << "\ndq에 1~3까지 삽입\n";
	dq.push_back(1);
	dq.push_back(2);
	dq.push_back(3);
	print_dq(); // 1 2 3

	cout << "\n\ndq의 1번째 위치에 4 삽입\n";
	dq.insert(dq.begin()+1, 4);
	print_dq(); // 1 4 2 3

	cout << "\n\ndq의 첫번째와 마지막 원소 삭제\n";
	dq.pop_front();
	dq.pop_back();
	print_dq(); // 4 2

	cout << "\n\ndq의 첫번째와 마지막 원소에 각각 5와 6 삽입\n";
	dq.push_front(5);
	dq.push_back(6);
	print_dq(); // 5 4 2 6

	cout << "\n\ndq 원소 전체 clear!\n";
	dq.clear();
	print_dq(); // empty

}

실행결과

 

스택이나 큐와 다르게 원소에 접근하여 출력할 수 있고, 원하는 대로 스택처럼 혹은 큐처럼 사용이 가능하기 때문에 활용도가 높을 것 같다. (이 편한걸 이제야 알다니....)

 

 

덱 연습용 추천 문제

cocoon1787.tistory.com/236?category=831127

 

[C/C++] 백준 10866번 - 덱

문제 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여덟 가지이다. push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를

cocoon1787.tistory.com

 

반응형

+ Recent posts