Deque

Deque 는 double ended queued 의 약자로 큐 두개 중 하나를 좌우로 뒤집어서 붙인 구조로 큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할수 있도록 확장한 자료구조이다 .

Deque은 Stack Queue 의 특성을 모두 갖기에 먼저 Stack 과 Queue 를 이해하고 Deque 을 공부하는게 좋을것으로 보였다.
Stack 과 Queue 의 특성을 모두 갖기에 Deque 은 추가 와 start 부분과 end 부분에 다가능하도록 만들어야한다.

구현 코드

#include<iostream>
using namespace std;

template <typename T>
class Deque
{
private:
	struct DNode //이중 연결리스크 노드 구조 
	{
		T data;
		DNode* left; 
		DNode* right;
	};
	DNode* front;
	DNode* rear;
	int size; //deque 안의 원소 수 
public :
	Deque() // 초기화
	{
		front = nullptr;
		rear = nullptr;
		size = 0;
	}
	bool IsEmpty()
	{
		if (front == nullptr)
		{
			return true;
		}
		else
		{
			return false;

		}
	}
	void PushFront( T  data)
	{
		DNode* newNode = new DNode;
		newNode->data = data;
		newNode->right = nullptr;
		newNode->left = nullptr;

		if (front == nullptr) 
		{
			front = newNode;
			rear = newNode;
		}
		else
		{
			front->left = newNode;   //newNode 가 새로운 front 가 되는과정
			newNode->right = front;
			front = newNode;
		}
		size++;
	}
	void PushBack(T data)
	{
		DNode* newNode = new DNode;
		newNode->data = data;
		newNode->right = nullptr;
		newNode->left = nullptr;
		if (rear == nullptr)
		{
			front = newNode;
			rear = newNode;
		}
		else
		{
			rear->right = newNode; //새로운 REAR 갱신
			newNode->left = rear;
			rear = newNode;
		}
		size++;
	}
	T& PopFront() //삭제 및 반환 
	{
		DNode* deleteNode = front;
		T result;
		if (IsEmpty())
		{
			cout << "Deque is Empty" << '\n';
			exit(0);
		}
		else
		{
			result = deleteNode->data; 
			if (front->right==nullptr)//원소의 수가 하나뿐이라면
			{
				front = nullptr;
				rear = nullptr;
			}
			else
			{
				front = front->right; //front의 right 노드를 front 로 갱신
				front->left = nullptr;
			}
			delete deleteNode;
			size--;
			return result; 
		}
		
	}
	T& PopBack()
	{
		DNode* deleteNode = rear;
		T result;
		if (IsEmpty())
		{
			cout << "Deque is Empty" << '\n';
			exit(0);
		}
		else
		{
			result = deleteNode->data;
			if (rear->left == nullptr)//원소의 수가 하나뿐이라면 
			{
				front = nullptr;
				rear = nullptr;
			}
			else
			{
				rear = rear->left;
				rear->right = nullptr;
			}
			delete deleteNode;
			size--;
			return result;
		}

	}
	T& Front() //맨앞 출력
	{
		if (IsEmpty())
		{
			cout << "Deqque is Empty" << '\n';
			exit(0);
		}
		return front->data;
	}
	T& Back() //맨뒤 출력
	{
		if (IsEmpty())
		{
			cout << "Deqque is Empty" << '\n';
			exit(0);
		}
		return rear->data;
	}
	void Print()//모든 노드 출력
	{
		DNode* printNode = front;
		cout << "Deque : [ ";
		while (printNode)
		{
			cout << printNode->data << ' ';
			printNode = printNode->right;
		}
		cout << "]\n";
	}
	int& Size()
	{
		return size;
	}
	~Deque() //소멸자
	{
		while (!IsEmpty())
		{
			PopFront();
		}
		cout << "Release Deque" << '\n';
	}
};
int main()
{
	Deque <int> deque;
	deque.PushFront(1);
	deque.PushFront(2);
	deque.PushFront(3);
	deque.PushBack(4);
	deque.PushBack(5);
	
	deque.Print();

	cout <<"Front : " << deque.Front() << '\n';
	cout << "Back : " << deque.Back() << '\n';
	cout <<"Size : " << deque.Size() << '\n';
	deque.PopBack();
	deque.PopBack();
	deque.PopFront();
	deque.Print();
	cout << "Front : " << deque.Front() << '\n';
	cout << "Back : " << deque.Back() << '\n';
	cout << "Size : " << deque.Size() << '\n';



	return 0;
}

앞 뒤 둘다 push 및 pop 을 해줄수 있어야하기에 배열보다는 리스트 구조를 이용하여 만들어보았다.