11. 덱(Deque), 입력제한덱(Scroll), 출력제한덱(Shelp)

덱

  # 리스트의 양쪽 끝 모두에서 입출력을 할 수 있는 자료구조이다.

  # 큐와 스택의 개념을 일반화시킨 자료구조라고 할 수 있다.

  # 연결 리스트나 배열 기반으로 만들 수 있는데 배열 기반으로 하면 원형큐의 형태로 만들어 중앙부분부터 채워넣는다.

  # 덱이 비어있는 상태에서 데이터를 빼려고 하면 널포인터를 반환한다.  

덱의 변형

  # 한 쪽 끝에서의 삽입 작업에 제한을 둔 덱을 입력제한덱(Input restricted deque) 혹은 스크롤(Scroll)이라 한다.

  # 구현은 앞부분에 삽입하는 것을 제한하는 형태로 만들었다.

  # 한 쪽 끝에서의 제거 작업에 제한을 둔 덱을 출력제한덱(Output restricted deque) 혹은 셸프(Shelf)라고 한다.

  # 구현은 뒷부분에서 제거하는 것을 제한하는 형태로 만들었다.

C++로 구현한 덱

#pragma once

template <typename T>
class Deque
{
	template <typename T>
	struct node {
		T data;
		node<T>* prev;
		node<T>* next;
	};

	node<T>* pFirst;
	node<T>* pLast;

	T tRet;

	int iSize;

public:
	int getSize();

	int AddFirst(T data);
	int AddLast(T data);
	
	T& RemoveFirst();
	T& RemoveLast();

public:
	Deque();
	~Deque();
};

template <typename T>
Deque<T>::Deque()
{
	pFirst = nullptr;
	pLast = nullptr;

	iSize = 0;
}

template <typename T>
int Deque<T>::getSize()
{
	return iSize;
}

template <typename T>
int Deque<T>::AddFirst(T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->prev = nullptr;
	newnode->next = pFirst;

	if (pLast == nullptr) { pLast = newnode; }
	else { pFirst->prev = newnode; }
	pFirst = newnode;

	return ++iSize;
}

template <typename T>
int Deque<T>::AddLast(T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->prev = pLast;
	newnode->next = nullptr;

	if (pFirst == nullptr) { pFirst = newnode; }
	else { pLast->next = newnode; }
	pLast = newnode;

	return ++iSize;
}

template <typename T>
T& Deque<T>::RemoveFirst()
{
	node<T>* pDel = nullptr;
	pDel = pFirst;
	tRet = pDel->data;
	
	pFirst = pFirst->next;
	pFirst->prev = nullptr;
	
	delete pDel;
	iSize--;

	return tRet;
}

template <typename T>
T& Deque<T>::RemoveLast()
{
	node<T>* pDel = nullptr;
	pDel = pLast;
	tRet = pDel->data;

	pLast = pLast->prev;
	pLast->next = nullptr;

	delete pDel;
	iSize--;

	return tRet;
}


template <typename T>
Deque<T>::~Deque()
{
	node<T>* pDel = nullptr;
	node<T>* pFind = pFirst;
	while (pFind != nullptr) {
		pDel = pFind;
		pFind = pFind->next;
		delete pDel;
	}

	pFirst = nullptr;
	pLast = nullptr;

	iSize = 0;
}

C++로 구현한 스크롤

#pragma once

template <typename T>
class Scroll
{
	template <typename T>
	struct node {
		T data;
		node<T>* prev;
		node<T>* next;
	};

	node<T>* pFirst;
	node<T>* pLast;

	T tRet;

	int iSize;

public:
	int getSize();

	int AddLast(T data);

	T& RemoveFirst();
	T& RemoveLast();

public:
	Scroll();
	~Scroll();
};

template <typename T>
Scroll<T>::Scroll()
{
	pFirst = nullptr;
	pLast = nullptr;

	iSize = 0;
}

template <typename T>
int Scroll<T>::getSize()
{
	return iSize;
}

template <typename T>
int Scroll<T>::AddLast(T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->prev = pLast;
	newnode->next = nullptr;

	if (pFirst == nullptr) { pFirst = newnode; }
	else { pLast->next = newnode; }
	pLast = newnode;

	return ++iSize;
}

template <typename T>
T& Scroll<T>::RemoveFirst()
{
	node<T>* pDel = nullptr;
	pDel = pFirst;
	tRet = pDel->data;

	pFirst = pFirst->next;
	pFirst->prev = nullptr;

	delete pDel;
	iSize--;

	return tRet;
}

template <typename T>
T& Scroll<T>::RemoveLast()
{
	node<T>* pDel = nullptr;
	pDel = pLast;
	tRet = pDel->data;

	pLast = pLast->prev;
	pLast->next = nullptr;

	delete pDel;
	iSize--;

	return tRet;
}


template <typename T>
Scroll<T>::~Scroll()
{
	node<T>* pDel = nullptr;
	node<T>* pFind = pFirst;
	while (pFind != nullptr) {
		pDel = pFind;
		pFind = pFind->next;
		delete pDel;
	}

	pFirst = nullptr;
	pLast = nullptr;

	iSize = 0;
}

C++로 구현한 셸프

#pragma once

template <typename T>
class Shelf
{
	template <typename T>
	struct node {
		T data;
		node<T>* prev;
		node<T>* next;
	};

	node<T>* pFirst;
	node<T>* pLast;

	T tRet;

	int iSize;

public:
	int getSize();

	int AddFirst(T data);
	int AddLast(T data);

	T& RemoveFirst();

public:
	Shelf();
	~Shelf();
};

template <typename T>
Shelf<T>::Shelf()
{
	pFirst = nullptr;
	pLast = nullptr;

	iSize = 0;
}

template <typename T>
int Shelf<T>::getSize()
{
	return iSize;
}

template <typename T>
int Shelf<T>::AddFirst(T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->prev = nullptr;
	newnode->next = pFirst;

	if (pLast == nullptr) { pLast = newnode; }
	else { pFirst->prev = newnode; }
	pFirst = newnode;

	return ++iSize;
}

template <typename T>
int Shelf<T>::AddLast(T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->prev = pLast;
	newnode->next = nullptr;

	if (pFirst == nullptr) { pFirst = newnode; }
	else { pLast->next = newnode; }
	pLast = newnode;

	return ++iSize;
}

template <typename T>
T& Shelf<T>::RemoveFirst()
{
	node<T>* pDel = nullptr;
	pDel = pFirst;
	tRet = pDel->data;

	pFirst = pFirst->next;
	pFirst->prev = nullptr;

	delete pDel;
	iSize--;

	return tRet;
}

template <typename T>
Shelf<T>::~Shelf()
{
	node<T>* pDel = nullptr;
	node<T>* pFind = pFirst;
	while (pFind != nullptr) {
		pDel = pFind;
		pFind = pFind->next;
		delete pDel;
	}

	pFirst = nullptr;
	pLast = nullptr;

	iSize = 0;
}