6. Stack

시퀀스 컨테이너에 이어서 설명할 것은 컨테이너 어댑터이다. 컨테이너 어댑터에는 크게 stack, queue, priority_queue의 세 가지가 있으며 셋 다 자주 쓰이지만 각각의 특징은 꽤 다르다.

 

stack(스택)은 LIFO(Last-In-First-Out) 방식으로 작동하는 템플릿 클래스이다. 헤더파일 <stack>을 인클루드하면 사용이 가능하다. stack 클래스는 <stack>에서 인클루드하는 헤더파일 <bits/stl_stack.h>에 정의되어 있다. (앞서 살펴본 컨테이너들에 비해 컨테이너 어댑터의 클래스 정의는 비교적 짧다.) 또한 스택은 기본적으로 deque 컨테이너를 사용하기 때문에 <stack> 내부에서 <deque>를 인클루드한다. 따라서 <stack>을 인클루드하면 덱을 사용할 수도 있다.

 

여러 가지 선언 방법이 존재하는 컨테이너와는 달리 컨테이너 어댑터는 선언 방법이 한 가지로 제한된다. 이렇게 선언하는 것이다.

stack<int> s;

이렇게 선언하면 비어 있는 int형 스택이 생성된다. 컨테이너 어댑터 역시 템플릿으로 구현되어 있기 때문에 원소의 형식을 지정해야 한다.

 

컨테이너 어댑터는 컨테이너에 비해 멤버 함수가 꽤 제한적이다. 스택의 멤버 함수는 다음과 같다:

s.push(x);	s의 맨 위에 x를 삽입한다.
s.pop();	s의 맨 위 원소를 삭제한다.
s.top();	s의 맨 위 원소를 참조한다.
s.size();	s에 들어 있는 원소의 개수를 반환한다.
s.empty();	s가 비었는지 확인한다.
s.emplace(x);	s의 맨 위에 x를 삽입한다.
s.swap(k);	s와 k를 맞바꾼다.

가장 기본적인 함수밖에 없다. stack::clear과 같은 함수도 존재하지 않기 때문에, 스택의 원소를 모두 삭제해야 한다면 이런 식으로 하거나,

for(;s.size();)s.pop();

이런 식으로 해야 한다.

stack<int> k;
k.swap(s);

이후에 소개할 queue와 priority_queue 역시 clear 함수가 내장되어 있지 않으므로 원소를 모두 삭제하려면 이렇게 해야 한다.

 

스택이 사용되는 알고리즘에는 SCC, BCC 등이 있다.

 

[연습문제]

 

BOJ 10828. 스택 (Silver IV)

스택 연습 문제이다. 주어지는 입력에 맞게 동작하도록 멤버 함수를 호출하면 된다.

 

BOJ 10773. 제로 (Silver IV)

입력받은 수가 0이 아니면 스택에 넣고, 0이면 스택의 맨 위에 있는 원소를 삭제한다. 마지막에 스택에 남아 있는 수의 합이 답이 된다.

 

BOJ 2493. 탑 (Gold V)

스택의 맨 위 원소가 현재 원소보다 커질 때까지 스택의 맨 위 원소를 삭제한다. 남아 있는 맨 위 원소에 해당하는 탑이 현재 탑에서 발사한 신호를 수신하는 탑이 된다. 이 과정을 반복해서 답을 구한다. 또한 발사한 신호를 수신하는 탑이 없는 경우에도 정상적으로 작동해야 하므로 처음에 스택에 충분히 큰 값을 하나 넣어서 스택이 비는 일이 생기지 않도록 한다. 이 문제와 비슷한 문제로 USACO의 유명한 문제 Bad Hair Day가 있다. BOJ에는 '옥상 정원 꾸미기'라는 제목으로 등록되어 있다.

 

CF 1428C. ABBB (1100)

A가 나오면 스택에 넣고, B가 나오면 스택이 비어 있는 경우 스택에 넣고, 비어 있지 않은 경우 스택의 맨 위 원소를 삭제한다. 마지막에 스택에 남아 있는 원소의 수가 답이 된다.

 

→ solved.ac tag: stack