스택 (Stack)

스택은 Last In First Out 구조이다. 

 

기본 동작으로 

push, pop, empty, size, top 등의 연산이 있고 다음 소스코드를 통해 어떻게 스택이 동작되는지 보자.

 

다음은 스택의 동작 구현에 관한 기본적인 문제이다.

출처:https://www.acmicpc.net/problem/10828

10828번: 스택

 

소스코드

 

 

또한 스택을 활용하는 대표적인 문제는 괄호계산기이다. 다음 문제를 보자

출처:https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

((()))([])로 괄호를 주고 괄호 연산을 적용한 후의 값을 출력하는 문제이다.

이 문제는 물론 재귀로 풀 수 있지만 재귀도 스택영역에서 함수호출로 계속해서 스택처럼 쌓이는 구조이기때문에 일종의 스택이라고 할 수 있다. 그래서 좀더 직관적으로 이해하기 쉽게 문제를 해결할려면 스택으로 구현하는편이 훨씬 낫다.

이 문제에서 핵심은 스택을 사용하고 어떻게 스택안에 숫자와 괄호값을 동시에 관리할지를 해결하는 것이 가장 큰 문제이다.

1. 문제에서 음수의 값이 없어서 (,[값을 -2, -3으로 설정한 후 스택을 int형으로 놓고 관리하였다.

2. 그리고 괄호 연산을 마칠때 ( '('또는 '['을 만날때 ) 안에 숫자가 없는 경우와 있는 경우가 있다. ),]를 뽑고 ( 또는 [를 만나면 2와 3을 push하면 되고 만약 숫자가 나오면 더하기를 계속 수행한 후 마지막에 ( 나 [를 만났을때 *2 또는 *3 연산을 수행하면 된다.

 

3. 오류조건이다. 오류조건은 )를 뽑았을때 스택이 비어있거나 top값이 '(' (-2) 또는 자연수가 아니면 false를 리턴시켜 종료한다. 이는 ]를 뽑았을때도 같은 방식으로 오류조건을 설정한다.

 

소스코드