Deque

Deque

Double-Ended Queue(양쪽 끝 큐)의 약자로, 양쪽 끝에서 삽입과 삭제가 가능한 자료구조

Implementation

Linked List 기반으로 Deque 구현

#include<iostream>

using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;

    explicit Node(int value) : data(value), prev(nullptr), next(nullptr){}
};

class Deque {
private:
    Node* head;
    Node* tail;
    int size;

public:
    explicit Deque() : head(nullptr), tail(nullptr), size(0){}

    // 앞에 요소 추가
    void push_front(int value) {
        Node* newNode = new Node(value);
        if(empty()) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size++;
    }

    // 뒤에 요소 추가
    void push_back(int value) {
        Node* newNode = new Node(value);

        if(empty()){
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        size++;
    }

    // 앞 요소 제거
    void pop_front() {
        if(empty()) {
            return;
        }

        Node* temp = head;
        head = head->next;
        if(head != nullptr) {
            head->prev=nullptr;
        } else {
            tail = nullptr;
        }
        delete temp;
        size--;
    }

    // 뒤 요소 제거
    void pop_back() {
        if(empty()) {
            return;
        }

        Node* temp = tail;
        tail = tail->prev;
        if(tail != nullptr) {
            tail->next = nullptr;
        } else {
            head = nullptr;
        }
        delete temp;
        size--;
    }

    // 앞 요소 반환
    int front() const {
        if(empty()) {
            return -1;
        }
        return head->data;
    }

    // 뒤 요소 변경
    int back() const {
        if(empty()) {
            return -1;
        }
        return tail->data;
    }

    // 비어 있는지 확인
    bool empty() const {
        return size == 0;
    }

    // 크기 반환
    int getSize() const {
        return size;
    }

    ~Deque() {
        while(!empty()) {
            pop_front();
        }
    }
};

int main() {
    Deque deque;

    deque.push_back(10);
    deque.push_front(5);
    deque.push_back(15);

    cout<<"Front element: "<<deque.front()<<endl;
    cout<<"Back element: "<<deque.back()<<endl;

    deque.pop_front();
    cout<<"Front element after pop_front: "<<deque.front()<<endl;

    deque.pop_back();
    cout<<"Back element after pop_back: "<<deque.back()<<endl;

    cout<<"Size: "<<deque.getSize()<<endl;

    return EXIT_SUCCESS;
}

Output

Efficiency

Linked List 기반 효율표

	Time Complexity	Explaination
삽입	O(1)	양 끝에서의 삽입은 O(1)
삭제	O(1)	양 끝에서의 삭제는 O(1)
탐색	O(1)	인덱스로 직접 접근이 가능 O(1)
중간 삽입/삭제	O(n)	중간에 삽입하거나 삭제할 때는 O(n)

Efficiency Summary

양쪽 끝에서 빠른 삽입/삭제할 때 효율
임의 인덱스로 빠르게 접근할 필요가 있을 때 효율

중간 삽입/삭제가 필요한 경우 비효율
순차적으로 많은 데이터를 읽거나 접근할 때 비효율, vector가 더 효율적
일관된 성능이 필요한 경우 비효율, vector가 더 효율적

STL

std::deque

Deque 자료구조를 위한 C++ STL 컨테이너

std::vector와의 비교

std::vector와 비슷한 점이 많은데 차이점을 얘기하자면
std::vector는 데이터를 연속된 메모리 공간에 저장, std::deque는 데이터를 여러 블록에 데이터를 나누어 저장하고 블록을 연결시킨다
이로써 성능이나 접근이 필요한 상황에 따라 바뀐다

std::vector는 동적배열로 공간을 미리 할당해놓고 요소를 뒤에서만 추가가 가능하지만
std::deque는 앞뒤로 요소를 추가가 가능하다
즉, 업그레이드된 std::queue와 vector의 특정부분의 요소를 합친것이 std::deque라고 생각하면 된다