[C++] STL 컨테이너 - deque (Double-Ended Queue, 덱)

• STL 컨테이너란?
  • Standard Template Library
  • 템플릿 기반으로 모든 컨테이너에 적용되는 표준 인터페이스
  • 메모리 자동관리 -> 메모리 단편화

---

💡 std::queue

• deque란?
  • 양쪽 끝에서 삽입/삭제가 가능한 동적 배열 컨테이너
  • 빠른 삽입과 삭제 연산이 필요할때 사용한다.
  • deque는 스택과 큐의 장점을 결합한 자료구조
• 특징
  • 시간 복잡도 
    • 인덱스 접근 O(N)
    • 삽입 / 삭제 O(1)
  • 양방향 삽입 & 삭제
  • 랜덤 엑세스 지원 : 인덱스로 접근 가능
  • 메모리 분할 저장 : 연속된 메모리 블록이 아닌 여러 블록을 연결하여 저장
  • 중간 삽입/삭제시 속도 향상 : 랜덤접근이 가능하며, vector 보다 효율적
  • 자동 크기 조절 : vector 처럼 동적으로 크기가 조정된다.

 

📍 queue 사용 예제

#include <iostream>
#include <deque>

using namespace std;

int main() {

	deque<int> dq; // 빈 덱 선언
    deque<int> dq2(5, 10); // 크기 5, 모든 원소 10 
    deque<int> dq3 = {1, 2, 3, 4}; 
    
    // 뒤쪽 삽입/삭제
    dq.push_back(1);   // [1]
    dq.push_back(2);   // [1, 2]
    dq.pop_back();     // [1]

    // 앞쪽 삽입/삭제
    dq.push_front(3);  // [3, 1]
    dq.push_front(4);  // [4, 3, 1]
    dq.pop_front();    // [3, 1]
    
    dq.clear();
    dq = {1, 2, 3, 4, 5};

    cout << dq[2] << "\n";       // O(1) 접근
    cout << dq.front() << "\n";  // 첫 번째 원소
    cout << dq.back() << "\n";   // 마지막 원소

    // 순회
    for (int num : dq) {
        cout << num << " ";
    }
    
    auto it = dq.begin() + 2;  // 3번째 원소 (3) 위치
    dq.insert(it, 10);         // [1, 2, 10, 3, 4, 5]
    
    dq.erase(dq.begin() + 3);  // [1, 2, 10, 4, 5]
    
    
    return 0;
}

 

📍 queue 주요 함수 및 시간 복잡도

함수	설명	시간복잡도
push_front()	맨 앞 요소 삽입	O(1)
push_back()	맨 뒤 요소 삽입	O(1)
pop_front()	맨 앞 요소 삭제	O(1)
pop_back()	맨 뒤 요소 삭제	O(1)
[n]	n번째 요소 접근 (범위 체크 x)	O(1)
at(n)	n번째 요소 접근 (범위체크 o -> 범위를 벗어나면 예외 발생)	O(1)
front()	첫 번째 요소 반환	O(1)
back()	마지막 요소 반환	O(1)
insert(n)	n번째 위치에 원소 삽입 - 삽입 후 이동 발생	O(N)
erase(n) erase(a, b)	n번째 위치의 원소 삭제 - 삭제 후 이동 발생 범위를 지정하여 여러 원소 삭제	O(N)
find(begin, end, value)	범위 지정 후 value 찾기	O(N)

 

🚀 vector보다는 중간 삽입/삭제가 빠르다.

🚀 랜덤접근이 필요하다면 deque, 중간 삽입/삭제가 많다면 list가 적절하다.

---

📌 deque vs vector vs list

연산	deque	vector	list
인덱스 접근	O(1)	O(1)	O(N)
앞쪽 삽입/삭제	O(1)	O(N)	O(1)
뒤쪽 삽입/삭제	O(1)	O(1)	O(1)
중간 삽입/삭제	O(N)	O(N)	O(1)

 

🔹 vector는 인덱스 접근 속도가 가장 빠르지만, 앞쪽 삽입/삭제가 느림
🔹 list는 중간 삽입/삭제가 O(1)이지만, 랜덤 액세스가 불가능하여 느림
🔹 deque는 앞/뒤 삽입과 인덱스 접근이 빠르지만, 중간 삽입은 느림

 

---

✅ 덱을 활용하는 알고리즘

• 슬라이딩 윈도우 : 주어진 배열에서 크기가 k인 윈도우에서 최소 또는 최대 값을 빠르게 찾기
• BFS (너비우선탐색) 
• 최적화 문제 - 덱을 활용한 그리디 최적화 (O(N))

 

💡 요약

 

✅ 빠른 앞/뒤 삽입과 삭제가 필요하면 deque
✅ 인덱스 접근이 많고 중간 삽입이 적다면 vector
✅ 중간 삽입/삭제가 많다면 list
✅ deque는 메모리를 연속적으로 할당하지 않음 (vector보다 덜 메모리 효율적)

 

🪄

deque는 vector와 list의 중간 정도의 성능 - 상황에 따라 queue나 vector보다 더 나은 성능을 제공
입력 크기가 크거나 삽입/삭제 연산이 많으면 deque을 사용하자.