자료구조 구현 (3), Stack and Queue

Stack and Queue 구현

C++을 통해서 Stack과 Queue를 구현했다. 이전 실습과 마찬가지로 ItemType, Stack(Queue), Application을 세 파트로 나누어 코드를 구현했다. ItemType과 Application은 Unsorted list와 크게 다른 부분이 없기에 이는 이전 포스팅을 참고하면 좋을 것 같다.

 

2022.05.11 - [강의 내용 정리/자료구조] - 자료구조 구현 (1), Unsorted list

자료구조 구현 (1), Unsorted list

 

해당 실습 역시 이전 실습과 마찬가지로 Array List로 구현했다. 

 

1. Stack

1) Stack.h

#include "ItemType.h"
#include <iostream>
using namespace std;

#define maxStack 10


/**
*	@brief	Exception class thrown by Push when stack is full.
*/
class FullStack
{
public:
	/**
	*	@brief	Display a message for full stack on screen.
	*/
	void print()
	{
		cout << "FullStack exception thrown." << endl;
	}
};


/**
*	@brief	Exception class thrown by Pop and Top when stack is empty.
*/
class EmptyStack
{
public:
	/**
	*	@brief	Display a message for full stack on screen.
	*/
	void print()
	{
		cout << "EmtpyStack exception thrown." << endl;
	}
};


/**
*	@brief	Stack class.
*	@details	This class processes as Last In, First Out (LIFO).
*/
class Stack
{
public:

	/**
	*	@brief	Allocate dynamic array whose size is maxStack.
	*	@pre	The maxStack is defined
	*	@post	Member of items points the allocated array.
	*/
	Stack();

	/**
	*	@brief	Destruct the object. Free the array dynamically allocated.
	*	@pre	Release memory for stack pointer.
	*	@post	none.
	*/
	~Stack();

	/**
	*	@brief	Determines whether the stack is full.
	*	@pre	Stack has been initialized.
	*	@post	Function value = (stack is full)
	*/
	bool IsFull() const;

	/**
	*	@brief	Determines whether the stack is empty.
	*	@pre	Stack has been initialized.
	*	@post	Function value = (stack is empty)
	*/
	bool IsEmpty() const;

	/**
	*	@brief	Adds newItem to the top of the stack.
	*	@pre	Stack has been initialized.
	*	@post	If (stack is full), FullStack exception is thrown; otherwise, newItem is at the top of the stack.
	*/
	void Push(ItemType item);

	/**
	*	@brief	Removes top item from the stack.
	*	@pre	Stack has been initialized.
	*	@post	If (stack is empty), EmptyStack exception is thrown; otherwise, top element has been removed from stack.
	*/
	ItemType Pop();

	/**
	*	@brief	Returns a copy of top item on the stack.
	*	@pre	Stack has been initialized.
	*	@post	If (stack is empty), EmptyStack exception is thrown; otherwise, top element has been removed from stack.
	*/
	ItemType Top();

	/**
	*	@brief	Print all the items in the stack on screen
	*	@pre	Stack has been initialized.
	*	@post	None.
	*/
	void Print();

private:
	int top;	///< Number of elements.
	ItemType* items;	///< Pointer for a stack.
};

 

2) Stack.cpp

#include "Stack.h"


// Allocate dynamic array whose size is maxStack 500.
Stack::Stack()
{
	items = new ItemType[maxStack];
	top = -1;
}


// Destruct the object. Free the array dynamically allocated.
Stack::~Stack()
{
	delete[] items;
}


// Determines whether the stack is full.
bool Stack::IsEmpty() const
{
	if (top <= -1)
		return true;
	else
		return false;
}


// Determines whether the stack is empty.
bool Stack::IsFull() const
{
	if (top >= maxStack - 1)
		return true;
	else
		return false;
}


// Adds newItem to the top of the stack.
void Stack::Push(ItemType newItem)
{
	if (IsFull())
		throw FullStack();
	else
	{
		top++;
		items[top] = newItem;
	}
}


// Removes top item from the stack.
ItemType Stack::Pop()
{
	ItemType temp;

	if (IsEmpty())
		throw EmptyStack();
	else
	{
		temp = Top();
		top--;
		return temp;
	}
}


// Removes top item from the stack.
ItemType Stack::Top()
{
	if (IsEmpty())
		throw EmptyStack();
	else
		return items[top];
}


// Print all the items in the stack on screen
void Stack::Print()
{
	cout << "Stack: ";
	// Stack 내의 모든 element 출력.
	for (int i = top; i >= 0; i--)
	{
		cout << items[i] << " - ";
	}
	cout << endl;
}

- Stack의 공간이 모두 차있는데 push를 하거나, 비어있는데 pop을 할 경우에 대해 예외처리를 해주었다. 이때 생성자를 통해 객체를 만들어서 return 값으로 전달하여 예외처리를 해주었다.

- 기본적인 Stack이기에 어렵지 않게 이해할 수 있다.

---

2. Queue

1) Queue.h

#include "ItemType.h"
#include <iostream>
using namespace std;

#define maxQueue 10


/**
*	@brief	Exception class thrown by Enqueue when queue is full.
*/
class FullQueue
{
public:
	/**
	*	@brief	Display a message for full queue on screen.
	*/
	void print()
	{
		cout << "FullQueue exception thrown." << endl;
	}
};


/**
*	@brief	Exception class thrown by Dequeue when queue is empty.
*/
class EmptyQueue
{
public:
	/**
	*	@brief	Display a message for empty queue on screen.
	*/
	void print()
	{
		cout << "EmtpyQueue exception thrown." << endl;
	}
};

/**
*	@brief	Queue class.
*	@details	This class processes as First In, First Out (FIFO), 템플릿을 적용해 다양한 변수 타입을 저장할 수 있다.
*/
template <typename T>
class CircularQueueType
{
public:
	/**
	*	@brief	Allocate dynamic array whose size is maxQueue.
	*	@pre	The maxQueue is defined
	*	@post	Member of items points the allocated array.
	*/
	CircularQueueType() {
		m_nMaxQueue = maxQueue + 1;
		m_iRear = m_nMaxQueue - 1;
		m_iFront = m_nMaxQueue - 1;
		m_pItems = new T[m_nMaxQueue];
	}

	/**
	*	@brief	Allocate dynamic array whose size is max.
	*	@pre	none.
	*	@post	Member of items points the allocated array.
	*/
	CircularQueueType(int max) {
		m_nMaxQueue = max + 1;
		m_iRear = m_nMaxQueue -1;
		m_iFront = m_nMaxQueue -1;
		m_pItems = new T[m_nMaxQueue];
	}

	/**
	*	@brief	Destruct the object. Free the array dynamically allocated.
	*	@pre	Release memory for queue pointer.
	*	@post	none.
	*/
	~CircularQueueType() {
		delete[] m_pItems;
	}


	/**
	*	@brief	Determines whether the queue is full.
	*	@pre	Queue has been initialized.
	*	@post	Function value = (queue is full)
	*/
	bool IsFull() {
		return (m_iRear + 1) % m_nMaxQueue == m_iFront;
	}

	/**
	*	@brief	Determines whether the queue is empty.
	*	@pre	Queue has been initialized.
	*	@post	Function value = (queue is empty)
	*/
	bool IsEmpty() {
		return m_iRear == m_iFront;
	}

	/**
	*	@brief	Makes the queue empty.
	*	@pre	Queue has been initialized.
	*	@post	m_iFront와 m_iRear is set same value as Constructer.
	*/
	void MakeEmpty() {
		m_iRear = m_nMaxQueue - 1;
		m_iFront = m_nMaxQueue - 1;
	}

	/**
	*	@brief	Adds newItem to the last of the queue.
	*	@pre	Queue has been initialized.
	*	@post	If (queue is full), FullQueue exception is thrown; otherwise, newItem is at the last.
	*/
	void EnQueue(T item) {
		if (IsFull()) throw FullQueue();
		else {
			m_iRear = (m_iRear + 1) % m_nMaxQueue;
			m_pItems[m_iRear] = item;
		}
	}

	/**
	*	@brief	Removes first item from the queue.
	*	@pre	Queue has been initialized.
	*	@post	If (queue is empty), EmptyQueue exception is thrown; otherwise, first element has been removed from queue. item gets value of removed item.
	*/
	void DeQueue(T& item) {
		if (IsEmpty()) throw EmptyQueue();
		else {
			m_iFront = (m_iFront + 1) % m_nMaxQueue;
			item = m_pItems[m_iFront];
		}
	}

	/**
	*	@brief	Print all the items in the queue on screen
	*	@pre	Queue has been initialized.
	*	@post	None.
	*/
	void Print() {
		if (!IsEmpty())  {
			int front = (m_iFront + 1) % m_nMaxQueue;
			while (true) {
				cout << m_pItems[front];
				if (front == m_iRear) break;
				front = (front + 1) % m_nMaxQueue;
				cout << " - ";
			}
			cout << endl;
		}
	}

private:
	int m_iFront;	//index of one infront of the first element.
	int m_iRear;	//index of the last element.
	int m_nMaxQueue;	//max size of the queue.
	T* m_pItems;	//pointer for dynamic allocation.
};

- 템플릿 클래스를 통해 Queue를 구현했기에 h 파일만으로 이를 구현했다. 템플릿 클래스인 경우 h와 cpp 파일을 구분해서 작성하면 심볼을 찾을 수 없어 에러가 발생할 수 있다. 따라서 템플릿 클래스인 경우에는 h 혹은 hpp 파일로 만들어서 구현하는 것이 좋다.

- Stack과 마찬가지로 클래스를 통해 예외처리를 해주었다.

- 기본적인 Queue이기에 그리 어려운 점은 없다.