자료구조 - 스택

이번에는 스택(Stack) 자료구조에 대해서 알아보도록 하겠습니다.

 

 스택이란 LIFO(Last In First Out) 구조를 가진 자료 구조입니다.

말 그대로, 가장 마지막에 들어간 데이터가 가장 먼저 나오는 구조를 의미합니다.

 

 예를 들어, [1] -> [2] -> [3] -> [4] 순서로 스택에 데이터를 넣게 되면 { [1], [2], [3], [4] } 가 될 것입니다. 이 상태에서 데이터를 꺼내게 되면 [4] -> [3] -> [2] -> [1] 의 순서로 나오게 되는 것 입니다.

 

 가장 대표적인 예로 일상적으로 Ctrl + Z 단축키로 많이 사용하는 "뒤로 가기" 기능입니다. 사용자가 조작한 정보값들을 스택의 형태로 저장한 후, "뒤로 가기" 기능을 사용 시, 가장 최근에 작업한 내용(즉, 가장 마지막으로 스택에 들어온 데이터를 의미한다.)이 꺼내져 나오며 해당 상황으로 되돌아가게 되는 것입니다. 

 

이처럼, 여러 상황에서 적절히 사용한다면 매우 유용하게 사용 가능한 스택 자료구조를 코드로 구현한 내용입니다.

template<typename T, typename Container = vector<T> >
class Stack
{
public:
	void push(const T& value)
	{
		_container.push_back(value);
	}
	
	void pop()
	{
		_container.pop_back();
	}

	T& top() const
	{
		return _container.back();
	}

	bool empty() const { return _container.empty(); }
	int size() const { return _container.size(); }

private:
	Container _container;
};

C++에서 제공하는 vector 혹은 List 두 STL 모두 해당 클래스를 구현하는데 사용된 메소드들을 지원하므로 두 컨테이너 모두 사용이 가능하도록 Container에 대해서도 템플릿 프로그래밍을 통해서 구현하였습니다.

 

이것으로 스택 자료구조에 대한 설명을 마치도록 하겠습니다. 포바~!