[STL] 07. std::deque

std::deque은 C++ 표준 라이브러리(STL)에서 제공하는 양방향 큐(Double-Ended-Queue)를 구현한 클래스다.

덱은 큐와 스택을 섞어놓은 듯한 동작 방식을 가지고 있으며 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료구조로

std::deque 역시 동일한 동작을 하며 다음은 std::deque의 주요 특징과 사용법이다.

 

 

특징

 

1. 표준 라이브러리의 일부 : std::deque는 C++ STL의 일부이며 <deque> 헤더에 정의되어 있다.

 

2. 양방향 큐 : std::deque는 큐와 스택의 두 가지 동작을 모두 제공하며

양쪽 끝에서 데이터를 추가하거나 제거할 수 있어 양방향 데이터 접근을 제공한다.

 

3. 동적 배열 구조 : std::deque는 동적 배열 구조로 구현되어 있어 큐의 크기를 동적으로 조절할 수 있으며,

큐가 가득 차면 크기를 자동으로 확장한다.

 

4. 인덱스 기반 접근 : std::deque는 인덱스를 사용하여 임의의 위치에 빠르게 접근할 수 있는 기능을 제공한다.

 

 

사용법

 

#include <iostream>
#include <deque>

int main() {

	std::deque<int> deq;

	deq.push_back(10);	// 10
	deq.push_back(20);	// 10 -> 20
	deq.push_back(30);	// 10 -> 20 -> 30

	deq.push_front(40);	// 40 <- 10 - 20 - 30
	deq.push_front(50);	// 50 <- 40 <- 10 - 20 - 30
	deq.push_front(60);	// 60 <- 50 <- 40 <- 10 - 20 - 30

	deq.pop_front(); // 50 <- 40 <- 10 - 20 - 30
	deq.pop_back();	// 50 <- 40 <- 10 - 20

	for (const auto& element : deq) {

		std::cout << element << std::endl;
	}

	std::cout << "size : " << deq.size() << std::endl; // 덱의 사이즈 출력
}

 

 

덱의 주요 멤버 함수와 기능

 

멤버 함수	설명	시간 복잡도
push_back()	덱 뒤쪽에 요소를 추가	O(1)
push_front(e)	덱 앞쪽에 요소를 추가	O(1)
pop_back()	덱 뒤쪽의 요소를 제거	O(1)
pop_front()	덱 앞쪽의 요소를 제거	O(1)
front()	덱 앞쪽의 요소를 참조	O(1)
back()	덱 뒤쪽의 요소를 참조	O(1)
empty()	덱이 비었는지 확인	O(1)
size()	덱에 저장된 요소의 수를 반환	O(1)
insert()	덱의 특정 위치에 요소를 삽입	O(n)
erase()	덱의 특정 위치에서 요소를 제거	O(n)

 

std::deque은 동적 배열 구조로 구현되어 있어 std::vector와 상당히 유사하며

양쪽에서 빠르게 데이터를 추가하거나 제거해야 하는 상황에서 효과적으로 사용할 수 있다.