Deque 구현

백준 알고리즘 문제를 풀어보는 중이다.

덱의 경우 스택과 큐 2개의 기능을 다 할 수 있다.
앞 뒤로 넣었다 뺐다 가능하다.
LIFO와 FIFO 둘 다 가능한 형태이다.

배열로 구현중인데 배열보다는 연결리스트로 구현하는 것이 쉽다.
요소가 1개일 때와 0개일 때 구별하는데 있어서 연결리스트가 훨씬 용이하다.

* 배열로 구현

///* 배열로 deque구현
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define MAX 10000
template <class T>
class Deque
{
private:
    T element[MAX];
    int size;
    int head;
    int tail;
public:
    Deque()
        : size(0), head(0), tail(0)
    {}
    void push_front(T _element)
    {
        if (getSize() == MAX - 1){
            //cout << "size error" << endl;
            return;
        }
        if (size++ > 0){
            head = (head - 1 + MAX) % MAX;
        }
        element[head] = _element;
    }
    void push_back(T _element)
    {
        if (getSize() == MAX - 1){
            //cout << "size error" << endl;
            return;
        }
        if (size++ > 0)
            tail = (tail + 1) % MAX;
        element[tail] = _element;
    }
    T front()
    {
        //cout << element[head] << endl;
        return isEmpty() ? -1 : element[head];
    }
    T back()
    {
        //cout << element[tail] << endl;
        return isEmpty() ? -1 : element[tail];
    }
    T pop_front()
    {
        if (isEmpty()){
        //    cout << "size error" << endl;
            return -1;
        }
        size--;
        int temp = head;
        if (size > 0)
            head = (head + 1) % MAX;
        return element[temp];
    }
    T pop_back()
    {
        if (isEmpty()){
            //cout << "size error" << endl;
            return -1;
        }
        size--;
        int temp = tail;
        if (size > 0)
            tail = (MAX + tail - 1) % MAX;
        return element[temp];
    }
    int getSize()
    {
        return size;
    }
    bool isEmpty()
    {
        //return getSize() ? false : true;
        return getSize() ? 0 : 1;
    }
    ~Deque(){}
};

int main()
{
    int testcase;
    cin >> testcase;
    string cmnd;
    Deque<int> deque;
    int element;
    for (int i = 0; i < testcase; i++)
    {
        cin >> cmnd;
        if (!cmnd.compare("push_front")){
            cin >> element;
            deque.push_front(element);
        }
        else if (!cmnd.compare("push_back")){
            cin >> element;
            deque.push_back(element);
        }
        else if (!cmnd.compare("pop_front"))
            cout << deque.pop_front() << endl;
        else if (!cmnd.compare("pop_back"))
            cout << deque.pop_back() << endl;
        else if (!cmnd.compare("size"))
            cout << deque.getSize() << endl;
        else if (!cmnd.compare("empty"))
            cout << deque.isEmpty() << endl;
        else if(!cmnd.compare("front"))
            cout << deque.front() << endl;
        else if(!cmnd.compare("back"))
            cout << deque.back() << endl;
    }
    return 0;
}

* 이중 연결리스트

///*이중 연결리스트로 deck구현하기!
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class DequeNode
{
private:
public:
	int data;
	DequeNode* rLink;
	DequeNode* lLink;
	DequeNode(int _data = 0)
		: data(_data), rLink(NULL), lLink(NULL)
	{}
	~DequeNode()
	{}
};


class Deque
{
private:
	DequeNode* head;
	DequeNode* tail;
public:
	Deque()
		: head(NULL), tail(NULL)
	{}
	~Deque()
	{}
	void push_front(int _element)
	{
		DequeNode* newNode = new DequeNode(_element);
		//if (head)//head != NULL
		if (isEmpty())
			head = tail = newNode;
		else
		{
			head->lLink = newNode;
			newNode->rLink = head;
			head = newNode;
		}
	}
	void push_back(int _element)
	{
		DequeNode* newNode = new DequeNode(_element);
		if (isEmpty())
			tail = head = newNode;
		else
		{
			tail->rLink = newNode;
			newNode->lLink = tail;
			tail = newNode;
		}
	}
	int pop_front()
	{
		if (isEmpty())
			return -1;
		int data = head->data;
		//요소가 2개 이상이면
		if (head != tail)
		{
			head = head->rLink;
			head->lLink = NULL;
			delete head->lLink;
		}
		//요소가 1개라면
		else{
			delete head;
			tail = head = NULL;
		}
		return data;
	}
	int pop_back()
	{
		if (isEmpty())
			return -1;
		int data = tail->data;
		
		//요소가 2개 이상이면
		if (head != tail){
			tail = tail->lLink;
			tail->rLink = NULL;
			delete tail->rLink;
		}
		//요소가 1개이면
		else
		{
			delete head;
			head = tail = NULL;
		}
		return data;
	}
	bool isEmpty()
	{
		//return (head == NULL) ? true : false;
		return (head == NULL) ? 1 : 0;
	}
	int front()
	{
		if (isEmpty())
			return -1;
		return head->data;
	}
	int back()
	{
		if (isEmpty())
			return -1;
		return tail->data;
	}
	int getSize()
	{
		if (isEmpty())
			return 0;
		int cnt = 1;
		DequeNode* node = head;
		while (node = node->rLink)
			cnt++; 
		return cnt;
	}
};
int main()
{
	int testcase;
	cin >> testcase;
	string cmnd;
	Deque deque;
	int element;
	for (int i = 0; i < testcase; i++)
	{
		cin >> cmnd;
		if (!cmnd.compare("push_front")){
			cin >> element;
			deque.push_front(element);
		}
		else if (!cmnd.compare("push_back")){
			cin >> element;
			deque.push_back(element);
		}
		else if (!cmnd.compare("pop_front"))
			cout << deque.pop_front() << endl;
		else if (!cmnd.compare("pop_back"))
			cout << deque.pop_back() << endl;
		else if (!cmnd.compare("size"))
			cout << deque.getSize() << endl;
		else if (!cmnd.compare("empty"))
			cout << deque.isEmpty() << endl;
		else if (!cmnd.compare("front"))
			cout << deque.front() << endl;
		else if (!cmnd.compare("back"))
			cout << deque.back() << endl;
	}
	return 0;
}
//*/