6. 스택(stack) -b. 연결 리스트 기반

연결 리스트 기반 스택

  # 스택을 연결 리스트를 이용해서 구현하면 스택의 크기를 신경쓰지 않아도 된다는 장점이 있다.

  # 연결 리스트 기반의 스택은 pTop(=pHead) 포인터가 가리키는 노드를 바꿔주는 것으로 구현이 가능하다.

  # push가 되면 새로운 노드를 리스트의 맨 앞에 연결한 뒤 pTop을 새로운 노드를 가리키게 한다.

  # Pop이 되면 pTop의 노드를 삭제하고 pTop이 그 다음 노드를 가리키게 한다.

  

STL의 스택

  # STL에서는 선형 구조의 컨테이너를 통해 스택 구조를 이용할 수 있다. (배열 기반도 가능하고, 연결 리스트 기반도 가능하다는 뜻)

연결 리스트 기반 스택의 ADT

  1. 스택에 데이터를 넣는다. (Push)

  2. 스택에서 데이터를 뺀다. (Pop) 

  3. 스택 맨 위의 데이터를 확인한다. (Peek)

    (Pop과 Peek 모두 데이터를 반환하게 하였는데, Stack이 비어있으면 컴파일 에러가 난다. 그러므로 사용시 스택이 비었는지 확인할 필요가 있다.)

  4. 스택에 들어있는 데이터의 개수를 확인한다. (Count) 

    (스택이 비었는지는 Count가 0인지 확인하면 가능하다. 가득 차는 경우는 응용 프로그램이 사용 가능한 메모리 자체가 부족한 경우로 극히 드므니 신경쓰지 않았다.)

C++로 구현한 연결 리스트 기반 스택

#pragma once

template <typename T>
class StackList
{
	template <typename T>
	struct node {
		T data;
		node<T>* next;
	};

	node<T>* pTop;

	int iCount;

public:
	int Push(T data);
	T& Pop();
	T& Peek();
	int Count();

public:
	StackList();
	virtual ~StackList();
};

template <typename T>
StackList<T>::StackList()
{
	pTop = nullptr;
	int iCount = 0;
}

template <typename T>
int StackList<T>::Push(T data)
{
	node<T>* newnode = new node<T>;
	newnode->data = data;
	newnode->next = nullptr;

	if (pTop != nullptr) {
		newnode->next = pTop;
	}

	pTop = newnode;
	return ++iCount;
}

template <typename T>
T& StackList<T>::Pop()
{
	T tRet = pTop->data;

	if (pTop != nullptr) {
		node<T>* pDel = pTop;
		pTop = pTop->next;
		delete pDel;
	}
	
	iCount--;
	return tRet;
}

template <typename T>
T& StackList<T>::Peek()
{
	T tRet = pTop->data;
	return tRet;
}

template <typename T>
int StackList<T>::Count()
{
	return iCount;
}

template <typename T>
StackList<T>::~StackList()
{
	while (pTop != nullptr) {
		node<T>* pDel = pTop;
		pTop = pTop->next;
		delete pDel;
	}
}