내가 사용하는 STL (1) - 스택 (stack)

서론

STL. Standard Template Library. C++을 위한 라이브러리로 사용자의 편의를 위해서 기본적으로 제공되는 라이브러리이다. 코딩을 함에 있어 STL과는 떼려야 뗄 수 없는 관계이고, STL 사용능력은 곧 코딩 능력과 코딩 속도로 직결되게 된다. 

하지만, 나는 STL 활용을 잘 하지 못한다. 일단 제대로 많이 알고 있는 것도 아니고, 별로 익숙하지도 않아서, 사용할 수 있는 각을 잘 보지 못하고, 막상 사용을 한다고 하더라도 기억을 제대로 못해서 꼭 디버깅을 몇 번 해보거나 코딩에 머뭇거림이 굉장히 심해진다. 이는 빠른 속도의 코딩을 요구하는 몇 개의 대회에서의 성적 하락으로 이어졌다. 마침, 조만간 빠른 속도의 코딩을 요구하는 대회가 좀 있고, 한 번쯤은 정리했어야 할 내용이기 때문에, 나만의 방식으로, 내가 사용하는 방식위주로, 까먹지 않도록 확실히 정리하는 글들을 작성하려고 한다. 

전체적으로 크게 두가지 파트로 나눠서 적으려고 한다. 한 파트는 활용법, 사용 하는 이유와 같은 부분이고 다른 한파트는 문법이다. 

stack

LIFO. Last In First Out의 자료구조이다. 즉 탑에 쌓는 것과 같은 이치이다. 가장 위에 올려놓고, 꺼낼 때도 가장 위에 있는 것 부터 꺼내게 된다. 당연히 임의의 순서에 있는 값은 꺼낼 수 없게 된다. 

이 그림과 같이 가장 위에서 넣고 꺼내게 된다.

문법

stack<ll> s	ll 형식의 stack s 생성
s.push(x)	s에 x원소를 가장 위에 삽입
s.top()	s의 가장 위에 있는 원소 참조
s.pop()	s의 가장 위에 있는 원소 삭제
s.size()	s에 들어있는 원소의 수 반환
s.empty()	s에 원소가 없는지(비었는지) 판별
while(!s.empty()) or while(s.size())	s가 빌 때까지. 보통 s의 원소를 하나씩 모두 뺄 때 사용
s1=s2	s1에 그대로 s2를 대입
swap(s1,s2)	s1와 s2의 원소를 전부 서로 교체

stack의 활용

일단 기본적으로 원하는 위치의 참조가 불가능 하다. 또한 stack의 가장 큰 장점이자 단점이자 특징은, 쭉 넣어놓고 쭉 다시 뺄 때 순서가 거꾸로 뒤집힌다는 것이다. DFS 같은 곳에서 stack을 활용할 수는 있겠지만, 당연하게도 재귀함수를 활용하는 것이 훨씬 편하다. 그래서 사실 별로 잘 사용하지는 않는다. 전체를 뒤집어서 출력하거나, 거꾸로 출력할 때. 즉 DP에서 역추적을 할 때 가끔 이용을 하는 정도이다.