[자료구조] Stack

분류:

- 선형 자료구조

- LIFO(Last In Frist Out) 구조

 

특징:
- 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조

- 데이터 삽입(push)과 삭제(pop)가 한쪽 끝(top)에서만 이루어짐

- 각 원소의 위치를 스택 포인터(SP)로 표시

- 스택이 비어있는 상태에서 원소를 꺼내려고 하면 'Stack Underflow' 발생

- 스택이 가득 찬 상태에서 원소를 추가하려고 하면 'Stack Overflow' 발생

 

사용처:

- 함수 호출 관리 (콜 스택)

- 웹 브라우저의 뒤로 가기 기능

- 괄호 검사 등 구문 분석

- 실행 취소 (Undo) 기능

- 깊이 우선 탐색(DFS) 알고리즘 구현

- 후위 표기법 계산

 

코드 구현

#pragma once
/*
	Stack
*/
template<typename T>
class Stack
{
private:
	int _size;		// stack 사이즈
	int _capacity;	// stack 용량
	T*  _data;		// stack data arr

public:
	// 생성자
	Stack() : _size(0), _capacity(0), _data(nullptr) 
	{

	};	 

	// 소멸자
	~Stack() 
	{
		if (_data)
			delete[] _data;
	};

public:
	// 메모리 할당
	void Reserve(int newCapacity) 
	{
		T* newData = new T[newCapacity];	// 새로운 버퍼를 할당받는다.

		if (_data)
			::memcpy(newData, _data, sizeof(T) * _size); // 이전 버퍼의 값을 새로운 메모리에 복사
		_capacity = newCapacity;	// capacity 갱신

		if (_data) // 이전 버퍼 메모리 할당 해제
			delete[] _data;

		_data = newData; // 새로 할당받은 버퍼를 가리키도록 갱신
	}

	// 데이터 추가
	void Push(const T& data) 
	{
		int newSize = _size + 1; // 값이 추가되면 1 늘어난다.
		if (_capacity < newSize) // 이미 할당된 메모리를 overflow 될 경우
		{
			int newCapacity = newSize * 1.5;
			Reserve(newCapacity);
		}
		_data[_size] = data; // 새로 삽입될 위치에 데이터를 복사한다.
		_size = newSize;	// _size 갱신
	}

	// 데이터 삭제
	void Pop()
	{
		if (Empty())
		{
			// data가 없는데 Pop을 했다는 것은, Error
			throw std::runtime_error("Stack is Empty");
		}
		_size -= 1; // 사이즈만 감소시켜준다. capacity는 그대로 둔다.
	}

	// Stack 비어있는지 체크
	bool Empty() 
	{
		if (_size == 0)
			return true;

		return false;
	}

	// stack의 특징은 가장 최근에 넣은 데이터가 가장 먼저 나온다
	// 후입선출법
	const T& Top() 
	{
		if (Empty())
		{
			// data가 없는데 Top을 했다는 것은, Error
			throw std::runtime_error("Stack is Empty");
		}
			
		return _data[_size - 1]; 
	}
};

#include "Stack.h"

int main() 
{
	Stack<int> s;

	s.Push(1);
	s.Push(2);
	s.Push(3);
	s.Push(4);

	while (!s.Empty()) 
	{
		std::cout << s.Top() << " " << std::endl;
		s.Pop();
	}

	// 예상출력값 4 3 2 1 
	return 0;
}

 

실행 결과

구현 중요 포인트

데이터가 Stack에 추가될 때 메모리가 overflow가 발생하면 새로운 메모리를 할당받고, 기존 메모리의 값들을 새로운 메모리에 복사시켜줍니다. (Reserve 함수가 메모리 재할당 및 복사를 담당합니다.)

새로운 메모리를 할당받고 기존 메모리에 있던 부분을 새로운 메모리에 복사해 주고 이전 메모리는 할당 해제합니다.

후입선출법을 구현하기 위해서 가장 마지막에 추가된 데이터가 필요하므로 Top() 메서드를 호출하면 마지막 인덱스의 있는 값을 리턴합니다.