[자료구조][C++] Deque 자료구조와 STL에서의 사용

Deque (Double Ended Queue)

Deque은 기존의 Queue에서 양쪽의로의 삽입 및 삭제가 가능해진 자료구조이다.

Queue와의 구분을 위해서 "덱"이라고 부른다.

 

 

deque에서 지원하는 O(1) 수준의 삽입, 삭제를 이용하면 빠른속도의 연산을 지원할 수 있다.

 

추가로 deque의 특징은 아래와 같다.

1. 크기가 가변적이다.
2. 앞,뒤로의 삽입 및 삭제가 용이하나, 중간값에 대한 삽입, 삭제는 용이하지 않다.
3. 인덱스를 통한 랜덤 접근이 가능하다.
     - 연결리스트처럼 해당 값에 바로 접근이 가능!
4. 구현이 어렵다.
     - 스택과 큐가 합쳐진 형태로 연결리스트에 비해 구현이 어렵다. 

 

 

따라서 아래의 경우 deque을 사용하는것이 좋다. (코딩테스트나 문제해결 시 이러한 조건이 주어진다면 덱을 생각해보자! )

1. 앞과 뒤에서 삽입 및 삭제를 진행
    - 가장 크게 덱을 사용하는 이유가 된다!
2. 저장할 데이터의 갯수가 가변적이다.
    - vector와 마찬가지로 덱도 가변적인 크기를 가지고 있다.
3. 검색을 거의 하지 않는다.
     - 검색을 주로 많이 한다면 deque 대신에 hash 혹은 hash_map, set을 사용하는게 좋다. 
4. 값에 랜덤으로 접근하고 싶다.
     - vector와 같이 인덱스를 통해 바로 접근이 가능하다.

 

 

---

 

이제 STL에서 dequq을 사용하는 방법에 대해 간략히 정리하도록 하자.

 

#include <iostream>
// deque을 사용할 경우 아래와 같이 import를 해줘야한다.
#include <deque>

// deque의 선언 : deque <자료형> 이름;
deque <int> dq;

// 추가 및 삭제
dq.push_front(ele); // 맨 앞에 ele 값 삽입   
dq.push_back(ele);  // 맨 뒤에 ele 값 삽입
dq.pop_front();     // 맨 앞의 원소 삭제 
dq.pop_back();      // 맨 뒤의 원소 삭제

// 검색
dq.front();  // 맨 앞의 원소 반환
dq.back();   // 맨 뒤의 원소 반환

// 그 외
dq.empty();  // deque이 비어있는지의 여부 반환(true/false)
dq.size();   // deque의 크기 반환

 

---

 

추가로 더 공부하고 싶다면 아래의 문제를 함께 풀어보는 것도 좋다!

2023.08.31 - [코딩테스트/C++] - [BOJ_11003][C++] 최솟값 찾기

[BOJ_11003][C++] 최솟값 찾기