Deque (덱)

Deque : abbreviation of double-ended queue

front 와 rear에서 양쪽에서 삽입과 삭제가 가능한 queue 

Necessary components

• front : 맨 앞 index
• rear : 맨 뒤 index
• addFront(item)
• deleteFront()
• addRear(item)
• deleteRear()

Additional components

• empty()
• full()
• getFront() : 맨 앞 데이터 값 반환
• gerRear() : 맨 뒤 데이터 값 반환
• size()

---

Implementaition

ArrayDeque

#include <iostream>
#include "ArrayQueue.h"

using namespace std;

class ArrayDeque:public ArrrayQueue{
public:
    ArrayDeque(){}
    ~ArrayDeque(){}
    void addFront(int item){
        if(empty()){
            throw 'deque is full';
        }
        else{
            for(int i=rear; i>=front; i--){
                data[i+1] = data[i];
            }
            data[front] = item;
            rear++;
        }
    }
    void addRear(){enqueue(item);}
    int deleteFront(){dequeue();}
    int deleteRear(){
        int ret = data[rear];
        rear--;
        return ret;
    }
    int getFront(){peek();}
    int getRear(){
        if(empty()){
            throw 'queue is empty'
        }
        else return data[rear];
    }
};

이전 post인 ArrayQueue를 상속받아 구현하였다.

2023.01.12 - [ComputerScience/Data Structrue] - Queue (큐)

Queue (큐)

당연히도 deleteFront(), addFront()에서 for문을 이용해 O(n)의 시간복잡도를 소비하는것을 알 수 있다.

매우 비효율적이므로 deque 또한 CircularDeque으로 구현해보자.

 

CircularDeque

#include <iostream>
#include "CirculaQueue.h"
using namespace std;

class CircularDeque:public CirculaQueue{
public:
    CircularDeque(){}
    void addRear(int item){enqueue(item);}
    int deleteFront(){return dequeue();}
    int getFront(){return peek();}
    int getRear(){
        if(empty()) throw 'deque is empty';
        else return data[rear]
    }
    void addFront(int item){
        if(full()) throw 'deque is full'
        else{
            data[front] = item;
            front = (front - 1 + MAX_SIZE) % MAX_SIZE;
        }
    }
    int deleteRear(){
        if(empty()) throw 'deque is empty'
        else{
            int ret data[rear];
            rear = (rear - 1 +MAX_SIZE) % MAX_SIZE;
            return ret;
        }
    }
};

Time Complexity

ArrayDeque

• addFront(item) : O(n)
• deleteFront() : O(n)
• addRear(item) : O(1)
• deleteRear() : O(1)

CircularDeque

• addFront(item) : O(1)
• deleteFront() : O(1)
• addRear(item) : O(1)
• deleteRear() : O(1)

Pros & Cons

Pros : CircularDeque 는 공간을 추상화 하여 연산의 시간복잡도를 줄였다.

Cons : Array 기반 Deque은 할당받은 공간에 비해 적게 사용한다면 공간 낭비를 하게 된다.

 

Solutions

1. Linked list 이용한 Deque