[C++] 덱 자료구조 & STL Deque Library 기본 명령어 정리

안녕하세요, 여행벌입니다.

오늘은 자료구조 덱과 덱을 지원해주는 C++ STL deque library에 대해서 알아보겠습니다.

---

1. Deque(덱)이란?

Double-ended Queue의 약자로 Queue에 양쪽에서 삽입, 삭제가 다 이뤄질 수 있다는 점이 추가된 자료구조입니다.

Queue(큐)를 모르시는 분은 하단의 게시물을 먼저 봐주세요!

https://travelbeeee.tistory.com/7?category=807507

Deque(덱)은 다음과 같습니다.

Queue와는 다르게 Front 와 Rear 양쪽에서 삽입, 삭제가 다 이뤄질 수 있는 자료구조로 유용하게 사용할 수 있습니다.

 

2. Deque(덱) Library 기본 함수

#include <deque> // Deque(덱) Library를 불러온다.

다음과 같이 Library를 불러올 수 있습니다.

덱 기본 함수
 
선언
- queue <자료형> 이름;
ex) queue<int> dq;  // int형을 담을 dq라는 이름의 deque(덱)을 선언.

추가 및 삭제
- push_front(element) : 덱의 제일 앞에 element를 추가한다.
- push_back(element) : 덱의 제일 뒤에 element를 추가한다.
- pop_front() : 덱에 있는 원소 중 제일 앞에 있는 원소를 삭제한다.
- pop_back() : 덱에 있는 원소 중 제일 뒤에 있는 원소를 삭제한다.

서칭
- front() : 덱의 제일 앞에 있는 원소를 반환한다.
- back() : 덱의 제일 뒤에 있는 원소를 반환한다.

기타
- empty() : 덱이 비어있으면 treu 아니면 false를 반환한다.
- size() : 덱의 사이즈를 반환한다. ( 원소가 몇 개 들어 있는지 int 형을 반환 )

queue에서 앞, 뒤가 push, pop이 추가되었을 뿐 큰 틀은 바뀐 점이 없습니다!

#include<iostream>
#include<deque>

using namespace std;

int main(void) {
	deque<int> dq;
	for (int i = 1; i <= 5; i++) {
		if (i % 2 == 1)
			dq.push_front(i);
		else
			dq.push_back(i);
	}
	for (int i = 1; i <= 5; i++) {
		cout << dq.front() << '\n';
		dq.pop_front();
	}
}

다음과 같이 1 ~ 5 숫자 중 홀수면 front에 push, 짝수면 back에 push를 한다면,

deque(덱)에는 원소가 어떻게 담겨있을까요?

(front) 5 3 1 2 4 (back)

위와 같이 담겨있겠죠?

---

오늘은 deque(덱)에 대해서 알아보았습니다.

위의 기본 함수들만 익힌다면, deque(덱)을 이용해서 알고리즘 문제를 푸는데 전혀 지장이 없을 겁니다!