[자료구조] 덱 (Deque)

덱의 개념

덱(deque)은 double-ended queue를 줄여서 표현한 것으로 양방향으로 넣고 뺄 수 있다는 사실에 초점이 맞춰진 자료구조로 스택과 큐의 특성을 모두 갖는 특징을 가지고 있다.
즉 덱은 rear와 front 어느 곳에서든 삽입 삭제가 모두 이루어 질 수 있다.

이러한 덱의 특징을 이용해 문서 편집 프로그램에서 사용자의 작업 이력을 관리하는 데 활용할 수 있다. 사용자가 작업을 실행하거나 취소할 때마다 덱에 해당 작업을 추가하고 제거함으로써 Undo와 Redo 기능을 구현할 수 있다.

덱 연산

• push_front : 맨 앞에 원소 삽입
• push_back : 맨 뒤에 원소 삽입
• pop_front : 맨 앞의 원소 제거
• pop_back : 맨 뒤의 원소 제거

시간복잡도

• push_front : $O(1)$
• push_back : $O(1)$
• pop_front : $O(1)$
• pop_back : $O(1)$

덱의 장단점

장점

• 크기가 가변적이다.
• 데이터의 삽입, 삭제가 빠르다.
• 원하는 요소에 바로 접근이 가능하다.

단점

• 구현이 어렵다.
• 중간에 삽입, 삭제가 용이하지 않다.

덱을 사용하는 경우

보통 스케줄링에 사용하게 되는데 스케줄링이 복잡해질수록 큐와 스택보다 덱이 더 효율이 잘나오는 경우가 있다.
또한 우선순위를 조절하게 될 때 큐나 스택보다는 덱의 사용이 더 유용하다.

구현

include <iostream>
using namespace std;

const int MAX = 1e5;

class Deque {
private:
    int data[MAX];
    int index_front;
    int index_back;
public:
    Deque();
    bool empty();
    void push_front(int x);
    void push_back(int x);
    void pop_front();
    void pop_back();
    int front();
    int back();
    int size();
};

Deque::Deque() {
    index_front = 0;
    index_back = 0;
}

bool Deque::empty() {
    return index_front == index_back;
}

void Deque::push_front(int x) {
    data[index_front] = x;
    index_front = (index_front-1+MAX) % MAX;
}

void Deque::push_back(int x) {
    index_back = (index_back+1) % MAX;
    data[index_back] = x;
}

void Deque::pop_front() {
    index_front = (index_front+1) % MAX;
}

void Deque::pop_back() {
    index_back = (index_back-1+MAX) % MAX;
}

int Deque::front() {
    return data[(index_front+1)%MAX];
}

int Deque::back() {
    return data[index_back];
}

int Deque::size() {
    return (index_back-index_front+MAX)%MAX;
}

int main() {
    Deque dq;
    for (int i=1; i<=3; i++) dq.push_front(i);  // Push front 1~3
    dq.pop_front();     // Pop front
    for (int i=4; i<=6; i++) dq.push_back(i);   // Push back 4~6
    dq.pop_back();      // Pop back
    dq.push_front(7);   // Push front 7
    Deque dq2 = dq;     // Copy deque
    cout << "* Pop Back: ";
    while (!dq.empty()) {
        cout << dq.back() << " -> ";
        dq.pop_back();  // Pop back all
    }
    cout << "\n* Pop Front: ";
    while (!dq2.empty()) {
        cout << dq2.front() << " -> ";
        dq2.pop_front();  // Pop front all
    }
    return 0;
}