서론
쌓여있는 접시
초밥과 LA갈비를 동시에 먹고 싶었던 나는 뷔페에 갔다. 그리고 음식을 담기 위한 접시를 집으려던 순간, 직원이 내가 집으려던 접시 위에 새로운 접시들을 또 쌓았다. 새로 올려진 접시에는 물기가 가득했다. 물기가 없는 처음 보았던 접시를 가져가고 싶지만 가져갈 수 없다. 이미 그 위에 많은 접시들이 쌓여있기 때문이다.
자료를 쌓는 스택
스택을 번역하면 명사로는 ‘무더기’, 동사로는 ‘쌓다’이다. 즉 접시와 같이 자료를 쌓는 구조다.
스택은 쌓는 구조이므로 가장 먼저 들어간 자료는 가장 아래에 있게 되고 가장 나중에 들어간 자료는 가장 위에 있게 된다. 그리고 자료의 추가(Push)와 제거(Pop)는 가장 위(Top)에서만 이루어진다. 그래서 가장 나중에 들어간 자료는 가장 먼저 나올 수 있고 가장 먼저 들어간 자료는 가장 나중에 나올 수 있다. 이를 LIFO(Last In First Out, 후입 선출이라고 한다.
시간복잡도
C++ STL에 정의되어있는 스택 클래스의 함수는 push, pop, top, size, empty이며 모든 함수의 시간 복잡도는 O(1)이다.
벡터 vs 스택
스택을 사용하기 위해 필요한 행위는 자료를 추가하는 행위, 자료를 제거하는 행위, 가장 위 자료 참조 행위이며 스택 클래스에는 이것이 잘 구현되어있다. 그리고 벡터 클래스에는 push_back, pop_back, back이 구현되어있다. 이 함수들로 벡터를 스택과 똑같이 이용할 수 있다.
스택과 벡터 클래스는 시간 복잡도나 공간 복잡도에서 차이가 없다. 그럼에도 스택을 사용하는 이유는 가독성이다. 내가 만든 자료구조가 스택이라는 것을 명시하여 코드 이해를 명확하게 한다.
[C++, STL] 알고리즘 문제풀이를 위한 벡터(vector)
스택 활용 예시
- 깊이 우선 탐색(DFS, Depth First Search)
- 뒤로 가기(Undo)
- 콜 스택(Call Stack)
헤더파일
스택을 사용하기 위해서는 헤더 파일이 필요하다.
#include <stack>
스택 선언
std::stack<템플릿>이름글의 가독성을 위해 이후에는 std를 생략한다. std는 네임스페이스(Using namespace std)로 대체될 수 있다.
템플릿은 int, string, vector, struct 등 다양하게 들어갈 수 있다. 즉 스택의 원소는 다양한 자료형이 될 수 있다.
스택에는 자료가 오른쪽으로 쌓인다.
stack<int>s; // int를 자료형으로 갖고 이름이 's'인 스택 생성
멤버 함수
push(원소)스택에 자료를 추가한다.
stack<int>s; // s = {}
s.push(4); // s = {4}
s.push(3); // s = {4, 3}
pop()스택에서 자료를 제거한다.
stack<int>s; // s = {}
s.push(4); // s = {4}
s.push(3); // s = {4, 3}
s.pop(); // s = {4}
top()스택의 최상단(오른쪽) 자료를 참조한다.
stack<int>s; // s = {}
s.push(4); // s = {4}
s.push(3); // s = {4, 3}
cout<<s.top() // 출력 : 3
size()스택의 원소 개수를 리턴한다.
stack<int>s; // s = {}
s.push(4); // s = {4}
s.push(3); // s = {4, 3}
cout<<s.size(); // 출력 : 2
empty()스택이 비어있으면 1(True), 비어있지 않으면 0(False)을 출력한다.
stack<int>s; // s = {}
cout<<s.empty(); // 출력 : 1
s.push(4); // s = {4}
cout<<s.empty(); // 출력 : 0
empty는 반복문과 함께 유용하게 쓰일 수 있다. 스택의 원소가 하나씩 제거되는 반복문에서 조건문이 !empty()라면 스택의 원소가 모두 제거될 때까지 반복하고 빠져나온다.
while(!s.empty()){
s.pop();
}
참고
https://docs.microsoft.com/en-us/cpp/standard-library/stack-class?view=vs-2019