[Basic C++] #68_deque

 

[Basic C++] #68_deque

 

C++의 STL에서 제공하는 deque 컨테이너에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 개념
2. 선언
3. 멤버 함수
4. 예제

 

#0. 개념

1. 덱?

[자료 구조]#0_선형 자료구조

 

• 덱(Double-Ended Queue)은 스택과 큐의 특성을 모두 가지고 있는 선형 자료구조입니다.
• 덱은 양쪽 끝에서 삽입과 제거 연산이 이루어지며, 이로써 덱은 스택의 LIFO(Last In First Out) 동작 방식과 큐의 FIFO(First In First Out) 동작 방식을 모두 수행할 수 있습니다.
• 덱의 양쪽 끝에서 수행하는 삽입/제거 연산은 선형 시간의 시간 복잡도를 가지며, 임의의 접근이 가능합니다.
• 따라서, 데이터 목록의 끝에서만 제거 연산이 가능한 vector 컨테이너와 달리, 덱은 양쪽 끝에서 제거 연산을 수행하며 이를 비교적 빠른 성능으로 처리할 수 있습니다.

 

2. 특징

장점

1. 양방향 삽입/삭제 : 컨테이너의 양쪽에서 O(1)의 시간 복잡도의 삽입/삭제 연산 수행이 가능합니다.
2. 동적 크기 조절 : vector 컨테이너와 같이 동적으로 크기를 조절합니다.
3. 임의의 접근 : 인덱스를 통한 임의의 접근이 가능해, O(1)의 빠른 접근 성능을 보여줍니다.
4. 메모리 효율성 : vector 컨테이너와 달리 저장 항목의 논리 순서와 물리 순서가 일치하지 않아, 연속된 메모리 블록이 필요하지 않고, 메모리 할당 과정에 유연함을 더해줍니다.

단점

1. 메모리 오버헤드 : deque의 내부 구조는 일반적으로 '청크' 혹은 '블록'이라고 불리는 고정 크기의 배열들로 구성됩니다. 각 블록은 일정 수의 요소를 저장하고 연속된 메모리에 있지 않을 수 있습니다. deque은 이 청크들을 관리하기 위한 Map을 가지며 이에 대한 추가적인 메모리 공간이 필요합니다.
2. 캐시 미스 : deque 컨테이너의 각 청크들은 연속된 메모리에 위치하지 않을 수 있기 때문에, 캐시 효율성이 비교적 떨어질 수 있습니다.

 

#1. 선언

1. 헤더

#include <queue>

 

2. 선언 및 초기화

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
	
	// #1. 기본 생성자
	deque<int> dq1;

	// #2. 복사 생성자
	deque<int> dq2(dq1);

	// #3. 범위 기반 초기화
	vector<int> v = { 1,2,3,4,5 };
	deque<int> dq3(begin(v), end(v));

	// #4. 개수, 값 초기화
	deque<int> dq4(3, 1); // 3개의 원소를 1값으로 초기화

	// #5. 초기화 리스트 활용
	deque<int> dq5 = { 1,2,3,4,5 };

	return 0;
}

 

#1. 멤버 함수

1. 접근

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

int main() {
	deque<int> myDeque = { 1, 2, 3, 4, 5 };

	// #1.[]		: 연산자를 사용한 접근
	cout << "myDeque[3]: " << myDeque[3] << endl; // 네 번째 요소에 접근

	// #2. at()		: 함수를 사용한 접근
	cout << "myDeque.at(2): " << myDeque.at(2) << endl; 

	// #3. front()	: 함수를 사용한 접근
	cout << "myDeque.front(): " << myDeque.front() << endl; // 첫 번째 요소에 접근

	// #4. back()	: 함수를 사용한 접근
	cout << "myDeque.back(): " << myDeque.back() << endl; // 마지막 요소에 접근

	return 0;
}

 

2. 삽입/제거

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque;

    // #1. push_back()	: 함수를 사용한 뒤쪽 삽입
    myDeque.push_back(1);
    myDeque.push_back(2);
    myDeque.push_back(3);

    // #2. push_front()	: 함수를 사용한 앞쪽 삽입
    myDeque.push_front(4);
    myDeque.push_front(5);
    myDeque.push_front(6);

    // #3. pop_back()	: 함수를 사용한 뒤쪽 제거
    myDeque.pop_back();

    // #4. pop_front() 	: 함수를 사용한 앞쪽 제거
    myDeque.pop_front();

    // #5. insert() 	: 함수를 사용한 중간 삽입
    std::deque<int>::iterator it = myDeque.begin() + 2;
    myDeque.insert(it, 7);
    myDeque.insert(it, 8);
    myDeque.insert(it, 9);

    // #6. erase()	: 함수를 사용한 중간 제거
    myDeque.erase(it);

    return 0;
}

 

Details

 

• STL의 queue 혹은 stack 컨테이너와 달리 deque 컨테이너는 "front()" 혹은 "back()"을 통해 컨테이너의 양쪽 끝에 위치하는 요소에 접근하는 방법과 더불어 operator [] 혹은 at()을 통해 임의의 원소에 접근하는 것이 가능합니다. 더불어, deque 컨테이너는 반복자를 통해 컨테이너를 순회하는 기능 또한 제공합니다.

 

3. 그 외 멤버함수

#include <iostream>
#include <deque>

using namespace std;

int main() {
	deque<int> myDeque = { 1, 2, 3, 4, 5 };

	// #1. size()	: deque에 저장된 요소의 개수 출력
	cout << myDeque.size() << endl;

	// #2. empty()	: deque가 비어있는지 확인
	if (myDeque.empty()) {
		cout << "Deque is empty" << endl;
	}
	else {
		cout << "Deque is not empty" << endl;
	}

	// #3. clear()	: deque의 모든 요소 제거
	myDeque.clear();

	// #4. swap()	: 두 개의 deque 교환
	deque<int> anotherDeque = { 10, 20, 30 };
	myDeque.swap(anotherDeque);

	return 0;
}

 

 

#3. 예제

1. BOJ_1021번 문제, 큐의 회전

[BOJ알고리즘, C++]#1021_회전하는 큐, 선형 자료구조, 덱

 

2. BOJ_10866번 문제, deque 컨테이너 활용

[BOJ알고리즘, C++]#10866_덱, 선형 자료구조

 

3. BOJ_5430번 문제, deque 컨테이너 활용

[BOJ알고리즘, C++]#5430_AC, 덱, 양방향 큐