220412_자료구조_리스트형 스택(Stack) 구현 및 실행

 

//Stack.h


#pragma once

#include <assert.h>

/*
* FILO(선입 후출): 먼저 들어온 데이터가 나중에 나간다.
	-> 물건을 통에 차곡차곡 담는다고 생각하면 될듯. 
	꺼낼때는 당연히 맨 위의 물건부터 꺼내야 한다.
	메모리의 스택도 비슷한 느낌이다.
	메모리 전체가 통으로 있으면, 메모리의 뒤쪽 부분에 스택 영역을 할당한다.

* 활용처
	- 데이터 뒤집기: 그냥 스택에 데이터를 넣었다 빼면 데이터가 뒤집어지므로
	- 길찾기 알고리즘

* 구현 방법
	- 동적 배열
	- 리스트: 싱글 링크드 리스트면 충분하다.
		반대로 갈 이유가 전혀없음 -> 맨 마지막 데이터에서부터 순서대로 접근할것이므로

* 이런 것들을 구현할 줄 알아야 하는 이유
	- 나중에 멀티스레드를 활용하는 단계에서는, 
		C++의 경우 STL을 사용하면 안정성을 보장할 수 없다...
	- 그러므로 나중에는 직접 안정성을 보장할 수 있게 코드를 수정해서 사용해야 한다.
*/

/*
CF)함수에 인자를 T&(레퍼런스)형으로 주는 이유
- 함수에 포인터 타입으로 인자를 주면 스택에 새 공간을 임시로 할당하여 
인자 주소의 값을 복사해온다 -> 이 과정에서 시간이 추가로 소요된다.
- 하지만 레퍼런스 타입으로 받아오면 이런 과정 없이 참조만 해서 
데이터를 활용하므로 시간이 단축된다.
- 앞에 const를 붙여놓는 이유는 const를 붙이면 인자로 들어온 값을
변경할 수 없게 되기 때문이다.
*/

template <typename T>
class CStackNode
{
	template <typename T>
	friend class CStack;

private:
	CStackNode():
		m_Next(nullptr)
	{
	}
	~CStackNode()
	{
	}

private:
	T	m_Data;
	CStackNode<T>* m_Next;
};



template <typename T>
class CStack
{
public:
	CStack()
	{
		m_Last = nullptr;
		m_Size = 0;
	}

	~CStack()
	{
		//스택을 싹 지워버리는 반복문.
		NODE* Node = m_Last;

		while (Node)
		{
			NODE* Next = m_Last->m_Next;

			delete Node;

			Node = Next;

		}
	}

private:
	typedef CStackNode<T>	NODE;

	//가장 마지막 주소부터 뺄 것이므로 마지막 노드의 주소를 가지고 있을 변수가 필요.
	NODE* m_Last;
	int m_Size;

	//스택을 다 비웠는지 체크 = null 노드를 통해 확인.

public:
	void push(const T& Data)
	{
		//1. 새 노드 생성해주고
		NODE* Node = new NODE;

		//2. 데이터 넣어주고
		Node->m_Data = Data;

		//3. 이전의 마지막 노드와 연결해 주고
		Node->m_Next = m_Last;

		//4. m_Last의 주소를 갱신
		m_Last = Node;

		//5.마지막으로 스택의 사이즈를 저장
		++m_Size;
	}

	T& Top()
	{
		//예외처리
		if (empty())
			assert(false); 
		
		return m_Last->m_Data;
	}

	void pop()
	{
		//예외처리
		if (empty())
		{
			assert(false);
		}

		//지울 노드를 임시로 저장해놓고 주소 변경 작업
		NODE* Temp = m_Last;

		//마지막 노드 주소 변경
		m_Last = Temp->m_Next;

		//노드 제거
		delete Temp;
		
		//사이즈 감소
		--m_Size;
	}

	int size() const
	{
		return m_Size;
	}

	bool empty() const
	{
		return 0 == m_Size;
	}
};

 

 

 

 

//main.cpp

#include <iostream>
#include "Stack.h"

int main()
{
	std::cout << "====== 리스트형 스택 확인 =====" << std::endl;
	CStack<int> stack;

	for (int i = 0; i < 10; ++i)
	{
		stack.push(i);
	}

	while (!stack.empty())
	{
		std::cout << stack.Top() << std::endl;
		stack.pop();
	}
	std::cout << "남은 Size: " << stack.size() << std::endl;
    
	return 0;
}