[#2] Stack

데이터들의 관리 방법중 후입선출(Last In - First Out)의 특성을 지닌 Stack을 템플릿으로 구현해봤다. 1시간동안 간단하게 구현해본 코드라 아직 제대로 대응하지 못하는 자료형이나 요소들이 있을 수 있다.   

 

 

---

목차

• Stack이란?
• Stack의 기능 구현
• 전체코드

 

 

---

Stack이란?

Stack이란 본래 건초나 짚더미처럼 무언가 쌓아올리는 더미를 뜻하는 낱말이다. 가장 먼저 들어온 데이터를 꺼내려면 뒤에 있는 모든 데이터를 들춰내야하는 FILO(First-In Last Out) 또는 LIFO(Last - In First - Out)의 특성을 가진다. 쉽게 생각해서 쌓아올린 접시들을 생각하면 된다. 가장 아래에 위치한 접시를 꺼내려면 위에 덮고있는 모든 접시들을 다 꺼내야만 하는 것처럼 Stack도 그러한 구조로 이루어져 있다. Stack의 기능은 삽입(push)와 삭제(pop)의 두 가지 기능이 있으면 된다. 흔히 지역 변수들을 저장하는 공간을 Stack이라고 부르는데 마찬가지로 지역 변수를 관리하는 자동메모리 공간이 Stack으로 이루어져있기 때문이다. 

 

• Stack의 장점
  일반적으로 데이터를 다루는 속도가 빠르며, 노드를 통해 구현할 시 데이터들의 크기를 유동적으로 관리할 수 있다.
• Stack의 단점
  배열의 인덱스 요소처럼 원하는대로 데이터를 꺼내오려면 그 데이터보다 나중에 들어온 데이터들을 모두 꺼내야하는 단점이 있다.

 

 

---

 

Stack의 기능 구현

Stack의 기능 push, pop 외에 생성자 or 소멸자 또는 tagNode에 대한 연결리스트에 대한 부분은 앞서 포스팅한 연결리스트 의 내용과 동일하므로 다루지 않을 생각이다.

 

 

push 삽입 기능

	template<typename T>
	inline void Stack<T>::push(T* newData)
	{
		CreateNode();
		node->Add_Data(newData);
	}

 

• CreateNode();
  새로운 노드를 생성한다.
• node->Add_Data(newData);
  새로운 노드 생성 후 내포 클래스 tagNode의 Add_Data 함수를 이용해 데이터를 삽입한다.

 

 

pop  삭제 기능

	template<typename T>
	inline T& Stack<T>::pop(void)
	{
		return DeleteNode();
	}
    
    	template <typename T>
	T& Stack<T>::DeleteNode()
	{
		if (node == nullptr)
		{
			std::cout << "Empty Stack!!" << std::endl;
			exit(EXIT_FAILURE);
		}
		else
		{
			T* dTemp = nullptr;
			if (nSize > 1)
			{
				dTemp = node->data;
				NODE* nTemp = node->prevNode;
				node->prevNode->nextNode = nullptr;
				delete node;
				node = nTemp;
			}
			else
			{
				dTemp = node->data;
				delete node;
				node = nullptr;
			}
			nSize--;
			top--;
			return (*dTemp);
		}
	}

 

• T& Stack<T>::DeleteNode()
  pop의 기능은 DeleteNode 함수를 그대로 사용한다. Node를 삭제하는 권한은 protected로 설정해두었기 때문에 Node를 삭제하는 기능인 DeleteNode 함수를 따로 분리해두었다. 해당 함수의 핵심 동작은 데이터의 개수가 1개 이상일 경우 기존 데이터를 temp에 보관한 후 이전 노드를 디폴트로 설정한다. 그 다음 삭제하고자 했던 노드의 힙공간을 회수 한 후 보관해두었던 데이터를 반환한다.

 

 

---

전체 코드

 

// 2022-07-02 푸바오 Stack.h
#ifndef __F_STACK_H__
#define __F_STACK_H__

#include <iostream>
namespace FU
{
	template <typename T = int>
	class Stack
	{
	protected:
		class tagNode
		{
		public:
			T* data = nullptr;
			tagNode* prevNode = nullptr;
			tagNode* nextNode = nullptr;
			bool Add_Data(T* newData)
			{
				if (data == nullptr)
				{
					data = newData;
					return true;
				}
				else
				{
					std::cout << "push error!" << std::endl;
					return false;
				}
			}
		};
		typedef tagNode NODE;
		void CreateNode();
		T&   DeleteNode();
	public:
		explicit Stack() {};
		explicit Stack(T* newData);
		~Stack();
		void     push(T* newData);
		T&       pop(void);
		size_t   size() const { return nSize; }
	private:
		size_t   nSize = 0;
		size_t   top = 0;
		NODE*    node = nullptr;
	};

	template <typename T>
	void Stack<T>::CreateNode()
	{
		if (node == nullptr)
		{
			node = new NODE;
		}
		else
		{
			NODE* temp = node;
			node->nextNode = new NODE;
			node = node->nextNode;
			node->prevNode = temp;
		}
		nSize++;
		top++;
	}

	template <typename T>
	T& Stack<T>::DeleteNode()
	{
		if (node == nullptr)
		{
			std::cout << "Empty Stack!!" << std::endl;
			exit(EXIT_FAILURE);
		}
		else
		{
			T* dTemp = nullptr;
			if (nSize > 1)
			{
				dTemp = node->data;
				NODE* nTemp = node->prevNode;
				node->prevNode->nextNode = nullptr;
				delete node;
				node = nTemp;
			}
			else
			{
				dTemp = node->data;
				delete node;
				node = nullptr;
			}
			nSize--;
			top--;
			return (*dTemp);
		}
	}

	template <typename T>
	Stack<T>::Stack(T* newData)
	{
		push(newData);
	}
	
	template <typename T>
	Stack<T>::~Stack()
	{
		if (node != nullptr)
		{
			for (int i = 0; i < nSize; i++)
			{
				NODE* temp = node->prevNode;
				delete node;
				node = temp;
			}
		}
	}
	template<typename T>
	inline void Stack<T>::push(T* newData)
	{
		CreateNode();
		node->Add_Data(newData);
	}

	template<typename T>
	inline T& Stack<T>::pop(void)
	{
		return DeleteNode();
	}

}
#endif

 

 

 

---