순서가 A, B, C, D로 정해진 입력 자료를 스택에 입력한 후 출력한 결과로 불가능한 것은?
1
D, C, B, A
오답 이유A부터 D까지 모두 push한 뒤 연속 pop하면 D, C, B, A가 출력되므로 가능하다.
2
B, C, D, A
오답 이유A와 B를 push해 B를 pop하고, C와 D를 차례로 push·pop한 뒤 A를 꺼내면 B, C, D, A가 가능하다.
3
C, B, A, D
오답 이유A, B, C를 push한 뒤 C, B, A를 pop하고 마지막에 D를 넣어 꺼내면 C, B, A, D가 가능하다.
4
D, B, C, A
정답 근거D를 먼저 꺼낸 시점의 꼭대기는 C이므로 C보다 아래에 있는 B를 다음에 꺼낼 수 없어 불가능하다.
정답·상세해설
정답 4번
입력 순서를 유지한 단일 스택에서는 D를 먼저 출력하려면 A, B, C, D를 모두 차례로 넣은 뒤 D를 꺼내야 한다. 이때 스택의 꼭대기는 C이므로 다음 출력은 반드시 C여야 한다. 따라서 D 다음에 B를 바로 출력하는 `D, B, C, A`는 만들 수 없다. 나머지 순서는 필요한 지점마다 push와 pop을 번갈아 수행하면 생성할 수 있다.