덱

덱이란

덱은 double-ended queue의 줄임말로서 전단(front)과 후단(rear) 양 끝에서만 출입을 할 수 있는 자료구조다. 즉, 중간에 데이터가 삽입 될 수는 없다.

덱의 특징

스택과 큐의 특징을 동시에 갖고 있다. 스택의 관점에서 보면 한 끝단에서 출입을 할 수 있다. 큐의 관점에서 보면 한 끝단이 데이터가 들어가면 반대 끝단에서 데이터가 나간다.

덱의 구현

덱은 원형큐를 확장해서 구현하는 것이 편리하다. 인덱스로 데이터를 관리하는 것이 메모리 측면에서도 효율적이고 인덱스의 거동만 추가하면 되기 때문이다. 이하 큐를 상속하는 덱의 구현이다.

#pragma once

#include <cassert>
#include <iomanip>
#include <iostream>

template <typename T>
class Queue // Circular Queue
{
  public:
    Queue(int capacity = 2) {
        assert(capacity > 0);

        capacity_ = capacity;
        queue_ = new T[capacity_];
        front_ = rear_ = 0;
    }

    ~Queue() {
        if (queue_)
            delete[] queue_;
    }

    bool IsEmpty() const { return front_ == rear_; }

    bool IsFull() const {
        // 원형 큐에서 꽉 찼다의 기준
        return (rear_ + 1) % capacity_ == front_;
    }

    T &Front() const {
        assert(!IsEmpty());

        return queue_[(front_ + 1) % capacity_]; // 주의 + 1
    }

    T &Rear() const {
        assert(!IsEmpty());

        return queue_[rear_];
    }

    int Size() const {
        if (front_ < rear_) {
            return rear_ - front_;
        } else if (rear_ < front_) {
            return (rear_ + capacity_) - front_;
        } else {
            return capacity_;
        }
    }

    void Resize() // 2배씩 증가
    {
        T *temp = new T[capacity_ * 2];
        // f - r
        if (front_ < rear_) {
            std::memcpy(temp, queue_, capacity_);
        } else {
            // TODO: r - f
            std::memcpy(temp, queue_ + front_ - 1, capacity_ - rear_);
            std::memcpy(temp + capacity_ - rear_, queue_, rear_);
        }
        delete[] queue_;
        queue_ = temp;
        front_ = 0;
        rear_ = capacity_ - 1;
        capacity_ *= 2;
    }

    void Enqueue(const T &item) // 맨 뒤에 추가, Push()
    {
        if (IsFull())
            Resize();

        if (rear_ == capacity_ - 1) {
            rear_ = 0;
            queue_[rear_] = item;
        } else {
            queue_[++rear_] = item;
        }

        return;
    }

    void Dequeue() // 큐의 첫 요소 삭제, Pop()
    {
        assert(!IsEmpty());

        front_ = (front_ + 1) % capacity_;
    }

  protected:        // 뒤에서 상속해서 사용
    T *queue_;      // array for queue elements
    int front_ = 0; // 시작 인덱스보다 하나 작은 값
    int rear_ = 0;  // 마지막 인덱스 (첫 값은 1에 추가)
    int capacity_;  // 빈 칸을 하나 둬야 하기 때문에 필요 메모리는 최대 저장량 + 1
    bool print_debug_ = false;
};

#pragma once

#include "Queue.h"

#include <cassert>
#include <iomanip>
#include <iostream>

// Double Ended Queue (덱, dequeue와 구분)
template <typename T> class Deque : public Queue<T> {

    typedef Queue<T> Base;

  public:
    Deque(int capacity) : Queue<T>(capacity) {}

    T &Front() { return Base::Front(); }

    T &Back() { return Base::Rear(); }

    void PushFront(const T &item) {
        if (Base::IsFull())
            Base::Resize();
        this->queue_[this->front_] = item;
        this->front_ = (this->front_ - 1 + this->capacity_) % this->capacity_;
    }

    void PushBack(const T &item) { Base::Enqueue(item); }

    void PopFront() { Base::Dequeue(); }

    void PopBack() {
        assert(!Base::IsEmpty());

        this->rear_ = (this->rear_ - 1 + this->capacity_) % this->capacity_;
    }

  private:
    // Queue와 동일
};