Stack in Linked Structures

생성일: 2021년 10월 15일 오후 7:38

ADT Stack Operation

Transformers

• Push
• Pop

Observers

• IsFull
• IsEmpty
• Top

(기존의 Stack과 동일한 기능들 필요)

구현

모두 템플릿을 사용하여 구현하였다.

StackType.h

#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를 해주어야 한다.

Main.cpp

#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;
	}
}

주의해야 할 점

1. 동적할당 해제
2. Struct 전방선언
   1. c++에 익숙하지 않아서 이 부분에서 발생한 에러 때문에 고생했다.
      에러 문구는 missing ';' before '<' 였고 문제되는 부분은 StackType 클래스의 선언에서 NodeType<ItemType>* topPtr; 이었다. 문제가 되는 이유는 NodeType 구조체가 해당 라인보다 아래에 있기 때문에 컴파일러가 NodeType이 무엇인지 모르는 것이다. 따라서 전방 선언 (Forward Declaration)을 통해 NodeType 구조체의 존재를 밝혀 주어야 한다.
3. NodeType 구조체의 템플릿
   1. NodeType 구조체도 템플릿으로 만들었기 때문에 NodeType의 객체를 만들거나 new를 통해 해당 타입 만큼의 공간을 할당할때도 모두 <ItemType>과 같은 템플릿의 타입을 붙여 주어야 한다.
      ex) NodeType<ItemType>* tempPtr;
      location = new NodeType<ItemType>; 등