데크 구현하기

데크란 무엇일까

큐/스택/데크는 모두 일렬로 늘어선 같은 형태의 자료들을 저장한다.
이때 이 세개를 구분짓는 기준은 어디에서 자료를 넣고 뺄 수 있느냐이다.
데크의 경우 양쪽 끝에서 자료를 넣고 뺴는 것이 가능하다.

직접 구현시 생기는 문제

데크는 양방향에서 모두 작동을 해야하기 때문에, queue구현 당시 겪었던 문제들은 데크 구현시에도 동일하게 생길 수 있다.
따라서 직접 구현을 할 때에는 tail 부분 처리를 신경쓰며 작업해야하며, 버려지는 공간의 관리를 위해 동적 배열을 재할당하는 방법을 사용할 수도 있다.

직접 구현하기

데크를 직접 구현하는 방법은 크게 두 가지로 연결리스트로 구현하기/동적 배열로 구현하기가 있다.

연결리스트로 구현하기

#include<iostream>
using namespace std;

class Deque {
private:
    struct Node {
        int data;
        struct Node* next_Node;
    };

    Node* frontNode;
    Node* backNode;

public:
    class iterator {
    private:
        Node* current;

    public:
        iterator(Node* start) : current(start) {}

        int& operator*() {
            return current->data;
        }

        iterator& operator++() {
            current = current->next_Node;
            return *this;
        }

        bool operator!=(const iterator& other) const {
            return current != other.current;
        }
    };

    Deque() : frontNode(nullptr), backNode(nullptr) {}

    iterator begin() {
        return iterator(frontNode);
    }

    iterator end() {
        return iterator(nullptr);
    }
    iterator rbegin() {
        return iterator(backNode);
    }
    iterator rend() {
        return iterator(nullptr);
    }

    void assign(int count, int data) {
        clear();

        for (int i = 0; i < count; i++) {
            Node* newNode = new Node;
            newNode->data = data;
            newNode->next_Node = nullptr;

            if (isEmpty()) {
                frontNode = backNode = newNode;
            }
            else {
                backNode->next_Node = newNode;
                backNode = newNode;
            }
        }
    }
    void clear() {
        while (!isEmpty()) {
            Node* temp = frontNode;
            frontNode->next_Node;
            delete temp;
        }
        backNode = nullptr;
    }

    void push_front(int data) {
        Node* newNode = new Node;
        newNode->data = data;
        newNode->next_Node = nullptr;
        if (isEmpty()) {
            frontNode = backNode = newNode;
        }
        else {
            // 이미 자료가 있다면 front 노드에 data를 넣고 back은 하나씩 밀려야
            newNode->next_Node = frontNode;
            frontNode = newNode;
        }
    }
    void push_back(int data) {
        Node* newNode = new Node;
        newNode->data = data;
        newNode->next_Node = nullptr;
        if (isEmpty()) {
            backNode = frontNode = newNode;
        }
        else {
            newNode->next_Node = backNode;
            backNode = newNode;
        }
    }
    void pop_back() {
        if (isEmpty()) {
            cout << "deque가 비어있습니다" << "\n";
        }
        if (frontNode == backNode) {
            frontNode = backNode = nullptr;
        }
        else {
            Node* temp = backNode;
            backNode = nullptr;
            Node* current = frontNode;
            while (temp->next_Node != nullptr) {
                //마지막 노드를 삭제한다면 마지막의 바로 앞에 있는 노드가 마지막 노드로 변경된다.
                temp = temp->next_Node;
            }
            if (current != temp) {
                backNode = current;
            }
            delete temp;

        }
    }
    void pop_front() {
        if (isEmpty()) {
            cout << "deque가 비었습니다" << "\n";
        }
        if (frontNode == backNode) {
            frontNode = backNode = nullptr;
        }
        else {
            Node* temp = frontNode;
            frontNode = nullptr;
            Node* current = backNode;
            while (temp->next_Node != nullptr) {
                temp = temp->next_Node;
            }
            if (current != temp) {
                frontNode = current;
            }
            delete temp;
        }
    }
    int size() {
        int count = 0;
        Node* current = frontNode;
        while (current != nullptr) {
            count++;
            current = current->next_Node;
        }
        return count;
    }

    bool isEmpty() const {
        return frontNode == nullptr;
    }
};

이터레이터 부분을 굳이 직접 구현할까 고민을 했지만, 공부하는 차원에서 직접 구현을 진행하였다.

동적 배열을 통한 구현하기

우선, 동적 배열이 무엇인지부터 알아야한다.
동적배열이란 말 그대로 메모리의 절약을 위해 크기를 유동적으로 조절해나가는 배열이다.
c/c++에서는 malloc/calloc/new를 사용하여 메모리를 동적으로 할당받을 수 있다.
또한 vector역시 내부에서 이러한 작업을 해주기 때문에 vector로 구현을 하여도 동적 배열로 구현한 것과 비슷한 효과를 낼 수 있다.

용도

데크는 양방향에서 모두 접근이 가능하다는 특징이 있다.
그래서 한쪽 끝값이 아닌 양쪽의 끝값이 모두 필요할 때에 사용하면 편리한데 복잡한 스케줄링을 한다거나 우선순위를 세밀하게 조절하는 용도로 사용가능하다.
그리고 스택 큐와 마찬가지로 stl상으로 이미 구현이 되어있는 구조이기 때문에 문제풀이를 할 때에는 나처럼 직접 구현을 하는데에 시간을 쓰기보단 deque 헤더파일을 include해주는 것이 좋다.