스택 (Stack)
스택은 Last In First Out 구조이다.
기본 동작으로
push, pop, empty, size, top 등의 연산이 있고 다음 소스코드를 통해 어떻게 스택이 동작되는지 보자.
다음은 스택의 동작 구현에 관한 기본적인 문제이다.
출처:https://www.acmicpc.net/problem/10828
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
www.acmicpc.net
소스코드
또한 스택을 활용하는 대표적인 문제는 괄호계산기이다. 다음 문제를 보자
출처:https://www.acmicpc.net/problem/2504
2504번: 괄호의 값
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()(
www.acmicpc.net
((()))([])로 괄호를 주고 괄호 연산을 적용한 후의 값을 출력하는 문제이다.
이 문제는 물론 재귀로 풀 수 있지만 재귀도 스택영역에서 함수호출로 계속해서 스택처럼 쌓이는 구조이기때문에 일종의 스택이라고 할 수 있다. 그래서 좀더 직관적으로 이해하기 쉽게 문제를 해결할려면 스택으로 구현하는편이 훨씬 낫다.
이 문제에서 핵심은 스택을 사용하고 어떻게 스택안에 숫자와 괄호값을 동시에 관리할지를 해결하는 것이 가장 큰 문제이다.
1. 문제에서 음수의 값이 없어서 (,[값을 -2, -3으로 설정한 후 스택을 int형으로 놓고 관리하였다.
2. 그리고 괄호 연산을 마칠때 ( '('또는 '['을 만날때 ) 안에 숫자가 없는 경우와 있는 경우가 있다. ),]를 뽑고 ( 또는 [를 만나면 2와 3을 push하면 되고 만약 숫자가 나오면 더하기를 계속 수행한 후 마지막에 ( 나 [를 만났을때 *2 또는 *3 연산을 수행하면 된다.
3. 오류조건이다. 오류조건은 )를 뽑았을때 스택이 비어있거나 top값이 '(' (-2) 또는 자연수가 아니면 false를 리턴시켜 종료한다. 이는 ]를 뽑았을때도 같은 방식으로 오류조건을 설정한다.
소스코드