Data Structure : Deque(Double-ended queue)

Deque

---

데크는 앞과 뒤에서 삽입, 삭제를 할 수 있는 자료구조임.

이중 연결 리스트를 이용해서 데크를 구현할 수 있음.

#include <iostream>
using namespace std;

typedef struct Qnode{
	int data;
	struct Qnode* llink;
	struct Qnode* rlink;
} Qnode;

typedef struct PointQ {
	Qnode* front, *rear;
} PointQ;

template <class T>
class Deque {
private :
	int q_size=0;
	PointQ* DQ = new PointQ;
		
public :
	Deque() {
		DQ->front=NULL;
		DQ->rear=NULL;
	}
	
	bool empty() {
		if(DQ->front == NULL ) {
			return true;
		}
		else return false;
	}
	
	void push_front(const T& val) {
		Qnode* newNode = new Qnode;
		newNode->data=val;
		newNode->llink=NULL;
		newNode->rlink=NULL;
		
		if(empty()) {
			DQ->front=newNode;
			DQ->rear=newNode;
		}
		else {
			newNode->rlink=DQ->front;
			DQ->front->llink = newNode;
			DQ->front=newNode;
		}
		q_size++;
	}
	
	void push_back(const T& val) {
		Qnode* newNode = new Qnode;
		newNode->data=val;
		newNode->llink=NULL;
		newNode->rlink=NULL;
		
		if(empty()) {
			DQ->front=newNode;
			DQ->rear=newNode;
		}
		else {
			newNode->llink=DQ->rear;
			DQ->rear->rlink = newNode;
			DQ->rear=newNode;
		}
		q_size++;
	}
	
	void pop_front() {
		if(empty()) {
			cout << "Queue Empty!!" << '\n';
		}
		else {
			Qnode* dNode = DQ->front;
			if(dNode->rlink == NULL) {
				DQ->front = NULL;
				DQ->rear = NULL;
			}
			else {
				DQ->front=dNode->rlink;
				DQ->front->llink=NULL;
			}
			delete dNode;
			q_size--;
		}
	}
	
	void pop_back() {
		if(empty()) {
			cout << "Queue Empty!!" << '\n';
		}
		else {
			Qnode* dNode = DQ->rear;
			if(dNode->llink == NULL) {
				DQ->front = NULL;
				DQ->rear = NULL;
			}
			else {
				DQ->rear=dNode->llink;
				DQ->rear->rlink=NULL;
			}
			delete dNode;
			q_size--;
		}
	}
	
	int size() {
		if(empty()) {
			return 0;
		}
		else
			return q_size;
	}
	
	int front() {
		if(empty()) {
			return -1;
		}
		else {
			return DQ->front->data;
		}
	}
	
	int back() {
		if(empty()) {
			return -1;
		}
		else {
			return DQ->rear->data;
		}
	}
	
	void printDQ() {
		Qnode* pNode = DQ->front;
		cout << "Node : [";
		while(pNode) {
			cout << "  " << pNode->data;
			pNode=pNode->rlink;
		}
		cout << "  ] \n";
	}
	
	~Deque() {
		delete DQ;
	}
};

---