Stack

생성일: 2021년 10월 1일 오후 6:03

ADT Stack Operation

Transformers

• Push
• Pop

Observers

• IsFull
• IsEmpty
• Top

구현

ItemType.h

#pragma once
#include <iostream>

const int MAX_ITEM = 5;
enum RelationType
{
	LESS,
	EQUAL,
	GREATER
};

class ItemType
{
public:
	RelationType ComparedTo(ItemType otherItem) const;
	void Print() const;
	void Initialize(int number);

private:
	int value;
};

RelationType ItemType::ComparedTo(ItemType otherItem) const
{
	if (value < otherItem.value)
		return LESS;
	else if (value > otherItem.value)
		return GREATER;
	else
		return EQUAL;
} //두 아이템을 비교하여 enum을 리턴

void ItemType::Print() const
{
	using namespace std;
	cout << value << endl;
}

void ItemType::Initialize(int number)
{
	value = number;
}

StackType.h

#pragma once
#include "ItemType.h"
//template를 사용 generic하게 작성
//template를 사용할 때에는 .h와 .cpp를 한 파일에 작성할 것.

class FullStack
{
	//stack이 full일때 Exception handling 위해 생성
};
class EmptyStack
{
	//stack이 empty일때 Exception handling 위해 생성
};

//template<typename T> 이렇게 작성하고 Itemtype을 전부 T로 바꾸어도 동일하게 작동함.
template<class ItemType>  //여기서 ItemType은 formal parameter
class StackType
{
public:
	StackType(); //Constructor
	bool IsFull() const;	//Observer
	bool IsEmpty() const;	//Observer
	void Push(ItemType item);	//Transformer
	void Pop();	//Transformer
	ItemType Top();	//Observer

private:
	int top; //Stack Pointer(제일 위의 위치를 가르킴)
	ItemType items[MAX_ITEM];
};

template<class ItemType>
StackType<ItemType>::StackType()
{
	top = -1; 
  //stack pointer가 -1부터 시작하기 때문에 새로운 item을 넣기전에 +1을 해주고 넣어야한다.
}

template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
	return (top == MAX_ITEM - 1);
}

template<class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
	return (top == -1);
}

template<class ItemType>
void StackType<ItemType>::Push(ItemType item)
{
	if (IsFull())
		throw FullStack();
	top++;
	items[top] = item;
}

template<class ItemType>
void StackType<ItemType>::Pop()
{
	if (IsEmpty())
		throw EmptyStack();
	top--;
}

template<class ItemType>
ItemType StackType<ItemType>::Top()
{
	if (IsEmpty())
		throw EmptyStack();
	return items[top];
}

Template를 사용하여 다양한 data type을 담을 수 있게 stack을 구현하였다.

여기서 주의해야할 점은 이 파일에서 사용된 ItemType은 ItemType.h에서 정의된 ItemType이 아니라 generic한 data type을 나타내는 변수이다. 따라서 파일 내의 ItemType을 전부 T로 바꾸어도 동일하게 작동한다. (교재에서 template 변수를 ItemType으로 작성하여 이를 옮긴 것이다. 미리 선언한 ItemType class와 이름이 동일하여 헷갈릴 수 있으니 주의해야한다.)

Main.cpp

#include "StackType.h"
#include <iostream>

using namespace std;

int main()
{
	ItemType item1;
	ItemType item2;
	ItemType item3;
	item1.Initialize(1);
	item2.Initialize(2);
	item3.Initialize(3);

	StackType<ItemType> myStack;  //template을 사용했다면 이런식으로 data type을 <>안에 작성해야함
	myStack.Push(item1);
	myStack.Push(item2);

	ItemType temp = myStack.Top();
	temp.Print();

	while (!myStack.IsEmpty())
	{
		myStack.Pop();
	}

	cout << "Empty: " << myStack.IsEmpty() << endl;
	cout << "Full: " << myStack.IsFull() << endl;

	StackType<char> charStack;   //template을 사용했다면 이런식으로 data type을 <>안에 작성해야함
	charStack.Push('A');
	charStack.Push('B');
	char topLetter = charStack.Top();
	cout << topLetter << endl;
	cout << "Empty: " << charStack.IsEmpty() << endl;
	cout << "Full: " << charStack.IsFull() << endl;
}

Main.cpp에서 사용된 ItemType은 ItemType.h 에서 정의한 ItemType class의 instance가 맞다.

StackType을 템플릿을 이용해 구현했기 때문에 다양한 데이터 타입들이 저장될 수 있다는 것을 알 수 있다.