C++ 링크드 리스트를 이용한 스택 구현 (Single Linked List Stack C++)

LIFO(FILO) 구조

출처- 위키피디아

STL의 STACK의 지원 함수::

PUSH- 스택에 값을 넣음 

POP- 최근에 넣은 값을 리턴하고 삭제

TOP- 가장 최근값을 리턴

EMPTY - STACK이 비어있다면 TRUE  출력

 

/* 싱글링크드 리스트를 이용해 실제 사용되는 stl(standard template library) 스택과 동일하게 구현 - 2019/05/18 xtar.tistory */

#include<iostream>
using namespace std;

template <typename T>
class Node
{
public:
	T value;
	Node<T>* next = nullptr;
	Node() {};
	~Node() {};
};

template <typename T>
class Stack
{
private:
	Node<T>* head;
	Node<T>* tail;
public:
	Stack() :head(nullptr), tail(nullptr) {}
	~Stack() { }
	void Push(T value);
	T Pop();
	bool isEmpty();
	T Top();
};


int main()
{
	Stack<int> stack;
	stack.Push(1);
	stack.Push(2);
	stack.Push(3);
	stack.Push(4);
	stack.Push(5);
	cout << stack.Top() << endl;

	cout << stack.Pop() << endl;
	cout << stack.Pop() << endl;
	cout << stack.Pop() << endl;
	cout << stack.Pop() << endl;
	cout << stack.Pop() << endl;
	cout << stack.Pop() << endl << endl;

}

template<typename T>
bool Stack<T>::isEmpty() //비어있으면 true를 리턴
{
	return tail == nullptr ? true : false;
}

template<typename T>
T Stack<T>::Top()// 마지막에 들어온 노드의 값 리턴
{
	return tail->value;
}


template<typename T>
void Stack<T>::Push(T _value)
{
	Node<T>* node = new Node<T>;
	node->value = _value;

	//만약 머리의 포인터가 비어있으면 새 노드 지정
	if (head == nullptr)
	{
		head = node;
		tail = node;
	}
	else
	{
		tail->next = node;
		tail = tail->next;
	}
}

template<typename T>
T Stack<T>::Pop()
{
	if(isEmpty()) // 만약 stack이 비어있으면
	{
		return -1;
	}
	else
	{
	Node<T>* ptr = head;
	T value = head->value;

	if (head == tail)
	{
		head = nullptr;
		tail = nullptr;
		delete(head);
	}
	else// 데이터가 하나가 아니면
	{
		while (ptr != nullptr)
		{
			//꼬리(top)값 삭제후 새 꼬리 대입
			if (ptr->next == tail)
			{
				value = tail->value;
				ptr->next = nullptr;
				delete(tail);
				tail = ptr;
				break;
			}
			ptr = ptr->next;
		}
		return value;
	}

	return value;
	}
}