[자료구조] 덱(Dequeue)이란?

1. 덱(Dequeue)이란?

2. 덱의 종류

3. 시간 복잡도

4. C++ 구현 코드

덱(Dequeue)이란?

Dequeue(Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 가능한 선형 자료구조이며, 양방향 큐라고도 불린다. 앞과 뒤에서 데이터를 자유롭게 추가하거나 제거할 수 있다는 점에서 일반적인 큐와는 다르다. 또한, 덱은 스택과 큐의 연산이 가능하기 때문에 스택과 큐의 혼합형 자료구조라고 볼 수 있다.

덱의 종류  

1. 입력 제한 덱 (Input-Restricted Deque): 삭제는 양쪽에서 가능하지만, 삽입은 한쪽 끝에서만 가능한 덱
2. 출력 제한 (Output-Restricted Deque): 삽입은 양쪽에서 가능하지만, 삭제는 한쪽 끝에서만 가능한 덱

시간 복잡도

• 앞/뒤에서 삽입 및 삭제: O(1).
• 앞/뒤 요소 접근: O(1)
• 임의 위치의 요소 접근: O(1)
• 중간에서 삽입/삭제: O(n)

덱은 양쪽 끝에서 삽입, 삭제, 접근 연산에는 효율적이지만, 중간에서 삽입 혹은 삭제는 효율적이지 않고, 선형 시간이 소요된다. 그래서, 덱은 양쪽 끝에서의 연산이 빈번한 경우에 적합한 자료구조이다. 

C++ 구현 코드

C++ 표준 라이브러리에서 deque가 구현되어 있기 때문에 <deque> 헤더를 포함하면 쉽게 사용할 수 있다.

• push_back(): 덱의 뒤쪽에 요소를 추가하는 함수
• push_front(): 덱의 앞쪽에 요소를 추가하는 함수
• pop_front(): 덱의 앞쪽 요소를 제거하는 함수
• pop_back(): 덱의 뒤쪽 요소를 제거하는 함수
• front(): 덱의 앞쪽 요소에 접근하는 함수
• back(): 덱의 뒤쪽 요소에 접근하는 함수

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> dq;

    // 뒤쪽에 요소 추가 -> push_back()
    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);

    // 앞쪽에 요소 추가 -> push_front()
    dq.push_front(0);

    cout << "Deque Element: ";
    for (int e : dq) {
        cout << e << " ";
    }
    cout << endl;

    // 앞쪽에서 삭제 pop_front()
    dq.pop_front();
    // 뒤쪽에서 삭제 pop_back()
    dq.pop_back();
    
    cout << "Deque Element: ";
    for (int e : dq) {
        cout << e << " ";
    }
    cout << endl;

    // 앞쪽과 뒤쪽 값 접근
    cout << "Front element: " << dq.front() << endl;
    cout << "Rear element: " << dq.back() << endl;

    return 0;
}

 

출력 결과는 다음과 같다.