[ 자료구조 ] Deque

덱(Deque)은 Double-Ended Queue의 약자이며, 양쪽에서 원소의 삽입과 삭제가 가능한 선형 자료구조입니다.

큐와 스택을 합친 형태와 같다. 앞 뒤로 push와 pop이 가능

 

1. 구현 사항

#include <iostream>
#define MAXSIZE 100
 
using namespace std;
 
template<typename T>
class Deque
{
public:
    int front;
    int back;
    int size;
    T* values;
 
    Deque()
    {
        size = MAXSIZE;
        values = new T[size];
        front = 0;
        back = 0;
    }
 
    ~Deque()
    {
        delete[] values;
    }
 
    void push_front(T value)
    {
        if (!isFull())
        {
            front = (front - 1 + size) % size;
            values[front] = value;
        }
        else
            cout << "Stack is Full" << endl;
    }
 
    void push_back(T value)
    {
        if (!isFull())
        {
            values[back] = value;
            back = (back + 1) % size;
        }
        else
            cout << "Stack is Full" << endl;
    }
 
    void pop_front()
    {
        if (!empty())
            front = (front + 1) % size;
        else
            cout << "Stack is Empty" << endl;
    }
 
    void pop_back()
    {
        if (!empty())
            back = (back - 1 + size) % size;
        else
            cout << "Stack is Empty" << endl;
    }
 
    bool empty()
    {
        if (back == front)
            return true;
        else
            return false;
    }
 
    bool isFull()
    {
        if ((back + 1) % size == front)
            return true;
        else
            return false;
    }
};

2. STL 활용

#include <iostream>
#include <deque>
 
using namespace std;
 
int main()
{
    deque<int> dq; 
 
    dq.push_back(1);  // dq의 뒤에 값을 넣는다.
    dq.push_front(1);  // dq의 앞에 값을 넣는다.
 
    dq.pop_back();  // dq의 back을 삭제한다.
    dq.pop_front();  // dq의 front를 삭제한다.
 
    dq.begin();
    dq.end();  // dq의 시작과 끝을 iterator로 리턴합니다.
 
    dq.front();  // dq의 front를 리턴한다.(peek기능)
    dq.back();  // dq의 back를 리턴한다. (peek기능)
 
    dq.at(0);  // dq의 n번째 요소를 리턴한다.
 
    dq.clear();  // dq의 구성요소를 모두 제거한다.
 
    dq.size();  // dq의 크기를 리턴한다.
 
    dq.empty();  // dq가 비어있으면 1 리턴하고 비어있지 않으면 0을 리턴한다.
    
    return 0;
 
}