[C++ / STL] Stack 분석

평소 알고리즘 문제를 풀면서 Stack의 주로 사용했던 부분들 위주로 설명한 글입니다.

(C++ reference 참고했습니다.)

---

 

1. Stack의 특성

Stack은 LIFO (Last In First Out) 후입 선출입니다. 먼저 들어간 게 먼저 나오는 것이 아닌 늦게 들어간 것이 먼저 나오는 구조입니다. 그리고 자료의 삽입 및 추출(?)이 Stack의 한 곳에서만 이루어집니다.

 

Stack의 표준 컨테이너는 Deque로 되어있습니다.

※ template <class T, class Container = deque<T>> class stack;

 

다른 STL들의 자료구조에 비해서 조금 덜 쓰이는 면이 있는 것 같습니다.

간단히 알아보도록 하겠습니다.

 

 

2. Stack의 구성

 

2.1) 생성자

복사 생성자나, 다른 생성자들이 있지만 Stack은 주로 텅 빈 Stack을 만드는 생성자를 자주 사용합니다.

 

그리고 생성자의 매개변수로 Vector나 deque를 받아올 수 있습니다. Vector로 받아올 경우에는 Stack의 Container에 Vector라고 직접 적어주어야 합니다.

#include <iostream>
#include <stack>
#include <vector>
#include <deque>
using namespace std;

int main()
{
	deque<int> dq(10, 1000);	//1000이 10개
	vector<int> v(5, 100);	//100이 5개

	stack<int> s1;
	stack<int> s2(dq);
	stack<int, vector<int>>s3(v);

	cout << "size of s1 : " << s1.size() << '\n';
	cout << "size of s2 : " << s2.size() << '\n';
	cout << "size of s3 : " << s3.size() << '\n';

	return 0;
}

위 코드의 결과

그 외 생성자도 있지만 위의 생성자가 가장 많이 쓰이는 것 같습니다.

 

2.2) 반복자

없음.

.top()메서드로 원소 접근 가능.

 

 

2.3) 메서드

Stack은 한 점에서 자료의 입출력이 이루어 지기 때문에 입출력 메서드인 .push(), .pop(), 그리고 더 나아가서 .top()메서드만 알면 거의 다 사용하고 있는 것이라고 봐도 됩니다.

 

특별한점은 .top()은 스택의 가장 위에 있는 값의 참조를 반환하기 때문에 lvalue로 쓰일 수 있다는 것입니다.

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	//Push()
	stack<int> s1;
	for (int i = 0; i < 10; ++i)
		s1.push(i);
	cout << "Stack의 상태: 0 1 2 3 4 5 6 7 8 9(top)\n\n";
	//top()
	cout << "s1.top() : "<< s1.top()<<'\n';
	cout << "s1.top() += 100 : " << (s1.top() += 100) << "\n\n";

	//pop()
	cout << "s1.pop()실행" << '\n';
	s1.pop();
	cout << "s1.top() : " << s1.top() << '\n';

	return 0;
}

위 코드의 결과

 

추가적으로 .empty()는 size가 0인 경우 True, 아니면 False를 반환합니다.

 

---

마치며..

Stack은 정말 간단하게 사용할 수 있습니다.

push는 내부적으로 puch_back을 호출합니다.

pop은 내부적으로 pop_back을 호출합니다. 따라서 시간 복잡도는 처음에 선언했던 deque인지, vector인지에 따라서 시간 복잡도가 달라질 것입니다. amortized O(n) 일지..

 

size와 empty는 상수 시간의 시간 복잡도를 가집니다.

 

Stack은 정말 쓰이는 곳에서 만 쓰이고 자주 안 쓰였던 것 같습니다. 솔직히 vector를 알면 stack을 꼭 사용 안 해도 문제 푸는 데는 지장이 없으니까.. 그런데 PS 하는 데가 아닌 개발할 때는 쓰이기 때문에 알아두는 것이 좋습니다.

 

지적, 댓글 환영입니다. :)