[자료구조]덱,데크,디큐(dequeue), 덱의 구현

덱/데크/디큐(dequeue)란?

처음 삽입한 데이터 혹은 마지막에 삽입한 데이터를 꺼내거나 혹은 처음/마지막에 데이터를 삽입할 수 있는 자료구조이다.

아래는 동적할당으로 구현하는 방법으로 template을 사용하지 않고, 데이터는 int를 가진 덱 구현 코드이다.

#include<cstdio>
 
class deque {
private:
    struct node {
        int data;
        node* prev;
        node* after;
        node() {
            prev = after = NULL;
        }
        node(int input) :data(input) {
            prev = after = NULL;
        }
    };
    node* pfront;
    node* pend;
    int element;
public:
    deque() {
        pfront = pend = NULL;
    }
    ~deque() {
        while (!empty()) {
            printf("Destructor : %d\n", back());
            pop_back();
        }
    }
    void push_front(int input) {
        node* new_node = new node(input);        
        if (empty()) {
            pfront = pend = new_node;
        }
        else {
            pfront->prev = new_node;
            new_node->after = pfront;
            pfront = pfront->prev;
 
        }
    }
    void push_back(int input) {
        node* new_node = new node(input);
        if (empty()) {
            pfront = pend = new_node;
        }
        else {
            pend->after = new_node;
            new_node->prev = pend;
            pend = pend->after;
        }
    }
    bool pop_front() {
        if (empty()) return false;
        node* del_node = pfront;
        pfront = pfront->after;
        delete del_node;
        if (pfront == NULL) pend = NULL;
        return true;
    }
    bool pop_back() {
        if (empty())return false;
        node* del_node = pend;
        pend = pend->prev;
        delete del_node;
        if (pend == NULL) pfront = NULL;
        return true;
    }
    int front() {
        if (empty()) return -1;
        return pfront->data;
    }
    int back() {
        if (empty()) return -1;
        return pend->data;
    }
    bool empty() {
        if (pfront == NULL  && pend == NULL) return true;
        return false;
    }
};
 
int main() {
    deque* DQ = new deque();
    for (int i = 1; i < 5; i++) {
        DQ->push_front(i);
    }
    while (!DQ->empty()) {
        printf("%d\n", DQ->front());
        DQ->pop_front();
    }
    for (int i = 1; i < 5; i++) {
        DQ->push_back(-i);
    }
    
    while (!DQ->empty()) {
        printf("%d\n", DQ->back());
        DQ->pop_back();
    }
    for (int i = 1; i < 10; i++) {
        DQ->push_back(-i);
    }
    delete DQ;
    return 0;
}