순서가 A, B, C, D로 정해진 입력 자료를 스택에 입력한 후 출력한 결과로 불가능한 것은?

정답 4번

스택은 입력과 출력이 번갈아 일어날 수 있지만, 아직 스택 안에 있는 원소는 마지막에 넣은 것부터 꺼내야 한다. D를 먼저 출력하려면 A·B·C·D를 모두 push해야 하므로 다음 top은 C이다. 따라서 D 다음에 B를 꺼내는 ④의 순서는 만들 수 없다. ①은 전부 push한 뒤 역순 pop, ②와 ③은 중간 pop을 섞어 만들 수 있다.