생성일: 2021년 10월 15일 오후 7:38
(기존의 Stack과 동일한 기능들 필요)
모두 템플릿을 사용하여 구현하였다.
#pragma once
class FullStack
{};
class EmptyStack
{};
//NodeType Forward Declaration
template <class ItemType>
struct NodeType;
template <class ItemType>
class StackType
{
public:
StackType();
~StackType();
bool IsFull() const;
bool IsEmpty() const;
void Push(ItemType newItem);
void Pop();
ItemType Top();
private:
NodeType<ItemType>* topPtr; //NodeType을 꼭 전방선언을 해주어야한다 (NodeType Struct정의는 이 줄보다 아래에 있기 때문에 전방선언 하지 않으면 여기서 에러 뜸)
};
//Node 정의
template<class ItemType>
struct NodeType
{
ItemType info; //저장할 Item의 value
NodeType* next; //다음 Node의 주소
};
//함수들 정의
template<class ItemType>
StackType<ItemType>::StackType()
{
topPtr = nullptr;
//topPtr을 NULL로 초기화
}
//중요!! -> 동적 할당된 메모리 공간을 스택이 필요없어지면 운영체제에 반납히야 함!! 아래의 Destructor가 꼭 필요하다.
template<class ItemType>
StackType<ItemType>::~StackType()
{
NodeType<ItemType>* tempPtr;
while (topPtr != nullptr)
{
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr; //deallocate
}
}
template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
//Node가 더이상 안만들어지면 full인 상태 => Node를 하나 만들어서 되는지 테스트
NodeType<ItemType>* location;
try
{
location = new NodeType<ItemType>;
delete location;
return false;
}
catch (std::bad_alloc exception)
{
return true;
}
}
template<class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
return (topPtr == nullptr);
}
template<class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
if (IsFull())
throw FullStack();
else
{
NodeType<ItemType>* location;
location = new NodeType<ItemType>;
location->info = newItem;
location->next = topPtr;
topPtr = location;
}
}
template<class ItemType>
void StackType<ItemType>::Pop()
{
if (IsEmpty())
throw EmptyStack();
else
{
NodeType<ItemType>* tempPtr;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
}
template<class ItemType>
ItemType StackType<ItemType>::Top()
{
if (IsEmpty())
throw EmptyStack();
else
return topPtr->info;
}
기본적인 형태는 Array로 구현한 Stack과 같다.
다른점은 동적 할당을 사용하였고 이에 따라 destructor에서 모든 item에 대해 delete를 해주어야 한다.
#include <iostream>
#include "StackType.h"
using namespace std;
int main()
{
StackType<char> myStack;
myStack.Push('v');
myStack.Push('c');
myStack.Push('s');
char letter;
while (!myStack.IsEmpty())
{
letter = myStack.Top();
myStack.Pop();
cout << letter << endl;
}
}