[기초 자료구조] 스택

Stack이란 LIFO(Last In First Out)의 개념을 가진 자료구조로, 먼저 들어간 것이 나중에 나오는 구조이다. 즉 아래와 같이 바닥이 막힌 유리병을 생각할 수 있다.

STL에서는 <stack> 라이브러리를 포함하여 사용하며, index로 접근이 불가능하다.

#include <stack>
using namespace std;

int main() {
	int a=5, b=6;
	stack<int> stk;
    	return 0;
}

위와 같은 상태에서 stk.push(a); stk.push(b)를 해주면 다음과 같다.

 

 

여기서 stk.pop()을 해주면 다음과 같다.

stk의 원소에 접근하기 위해선 stk.top()을 사용한다. 이 경우 원소를 참조는 하지만 stack에서 빼지는 않는다. 즉 이 상태에서 stk.top() == 5이다.

 

스택은 코딩테스트에서 주로 DFS와 함께 쓰인다. DFS를 깊이를 우선 탐색하는 알고리즘인데, 1의 자식이 2, 3, 4이고, 2의 자식이 21, 22, 23일 때 스택을 사용하면 1->2->21 순으로 탐색한다.