이전 내용에서의 Stack과 Queue는, 배열을 이용하여 구현하였음 => 저장할 수 있는 데이터의 양에 한계 존재
Push할 때마다 메모리 할당을 받을 순 없을까?
=> Dynamic Array를 이용한 구현
이런 식으로, 현재의 값과 다음 노드로 향하는 포인터를 포함하는 Node를 만들면 됨
new & delete
- new: 요청된 object를 할당하고, 적합한 pointer를 반환함.
int *p = new int;
- delete: 동적으로 할당된 해당 pointer가 가리키는 오브젝트 할당을 해제함.
delete p;
new로 할당해 주었으면, delete까지 해야 가비지가 생기지 않는다.
구현
NodeType.h
#pragma once
template<class ItemType>
struct NodeType
{
ItemType info;
NodeType* next;
};DynamicAllocStackType.h
#pragma once
#include "NodeType.h"
class FullStack {};
class EmptyStack {};
template<class ItemType>
class StackType
{
public:
StackType();
~StackType();
bool IsEmpty() const;
bool IsFull() const;
void Pop();
void Push(ItemType newItem);
ItemType Top();
private:
NodeType<ItemType>* topPtr;
};DynamicAllocStackType.cpp
#include "DynamicAllocStackType.h"
#include <stdexcept>
template<class ItemType>
StackType<ItemType>::StackType()
{
topPtr = nullptr;
}
template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
NodeType<ItemType>* location;
try
{
// 새로운 Node를 받는 것이 가능함 => false
location = new NodeType<ItemType>;
delete location;
return false;
}
catch (std::bad_alloc exception)
{
// Node를 받으려 해도 안 받아질 때 => true
return true;
}
}
template<class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
return (topPtr == nullptr);
}
template<class ItemType>
ItemType StackType<ItemType>::Top()
{
if (IsEmpty())
throw EmptyStack();
else
return topPtr->info;
}중요한 점
- Push를 할 땐, new 키워드를 이용하여 새로운 Node를 만들고, topPtr이 해당 Node를 가리키게 한다.
template<class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
if (IsFull())
throw FullStack();
NodeType<ItemType>* location;
location = new NodeType<ItemType>;
location->info = newItem;
location->next = topPtr;
topPtr = location;
}- 해당 Stack이 지역 변수로 선언되고, 해당 범위를 벗어나게 되면, 멤버변수 topPtr은 자동적으로 할당 해제된다.
그러나 topPtr이 가리키는 노드는 자동적으로 할당 해제되지 않으며, 우리가 이를 해제해 줘야 한다.
=> 소멸자에서, 멤버변수 topPtr이 가리키는 dynamic memory들을 해제해 주어야 한다.
template<class ItemType>
StackType<ItemType>::~StackType()
{
NodeType<ItemType>* tempPtr;
while (topPtr != nullptr)
{
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
}이는 Pop을 할 때에도 마찬가지
template<class ItemType>
void StackType<ItemType>::Pop()
{
if (IsEmpty())
throw EmptyStack();
else
{
NodeType<ItemType>* tempPtr;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
}이후 메인 함수에서 아래와 같이 쓰면, 5와 3이 연달아 프린트된다.
int main()
{
StackType<int> stack;
stack.Push(3);
stack.Push(5);
cout << stack.Top() << endl;
stack.Pop();
cout << stack.Top() << endl;
stack.Pop();
}비교
배열로 구현했을 때보다 시간복잡도에서 더 느릴 수 있다.
그러나 Linked로 구현하면 메모리를 적게 소요할 수 있다.
