[문제해설] 스택 S에서 B, A, D, C를 순서대로 입력시킬 때, 출력을 A, B, C, D 순으로 하기 위한 push와 pop의 횟수는?

전자계산기조직응용기사 필기 기출문제 해설(2과목 자료구조 및 데이터통신-스택) - 2019년1회

---

스택 S에서 B, A, D, C를 순서대로 입력시킬 때, 출력을 A, B, C, D 순으로 하기 위한 push와 pop의 횟수는?

 

① push : 4, pop : 4         ② push : 3, pop : 5

③ push : 2, pop : 6         ④ push : 5, pop : 3

 

 

 

 

---

-문제 해설-

스택(stack)은 자료구조의 선형구조 중에서 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 구조입니다.  단어 자체가 '쌓다'라는 뜻이듯, 동전을 쌓을 때, 동전을 하나씩 올리는 것을 입력, 맨 위에 것을 하나씩 들어내는 것을 상상하시면 됩니다.(중간에 있는 동전을 빼낼 수 없다는 가정)

컴퓨터 구조에서는 서브루틴 호출 시 복귀 주소를 저장하는 자료구조로 주로 사용되기도 합니다.

스택에서의 주요 용어는 다음 표와 같습니다.

 

본 문제에서는 B, A, D, C 순으로 입력을 하되, 출력은 A, B, C, D로 할 때, push와 pop의 횟수를 묻고 있습니다. 스택에서 push는 입력을 뜻하고, pop은 출력을 뜻합니다. 사실 이 문제는 잘못 만든 문제입니다. 보통 push와 pop의 순서를 묻는 문제로 출제되거나, 반대로 push와 pop의 순서를 제시하고, 출력 결과를 묻는 문제로 출제가 됩니다. 순서에 상관없이 횟수를 묻는 문제는 큰 의미가 없습니다. 왜냐하면 입력이 4개이고, 출력이 4개이면 순서에 따라서 결과는 달라지지만, push와 pop의 횟수는 당연히 4개씩이기 때문입니다. 아무래도 출제자가 실수를 한 것 같습니다.

 

답을 이미 구해버렸지만, 순서를 생각하며 문제를 풀어보겠습니다. 스택 문제는 스택을 그려서 푸는 것이 일반적입니다.

위 그림에서 흰색 원통은 스택 리스트입니다. 위에 뚫린 구멍으로 입력과 출력이 이루어지고, 문제에서 주어진 입력 순서 B, A, D, C 순대로 줄을 서있습니다. 출력(pop)이 되면 왼쪽 테이블에 왼쪽부터 출력 순으로 배치가 될 것입니다.

 

먼저 한 번의 입력(PUSH)이 실행되었습니다. 스택의 상태는 위 그림처럼 B가 저장되어있고, 문제 조건으로 제일 먼저 출력(POP)되어야 할 것은 A이므로 스택의 탑(top)이 A가 될때까지는 출력을 하지 않고 입력만 계속합니다.

위 그림은 한번의 입력(PUSH)가 더 실행된 상태입니다. 스택의 TOP가 A가 되었네요 그럼 다음번에 출력(POP)을 해야 되겠죠?

출력(POP)을 한번 실행하자 스택의 TOP은 B가 되었습니다. 다음 출력해야 할 것은 B이므로 다음에도 출력(POP)을 해야 합니다.

출력(POP)을 하니 스택이 위 그림처럼 텅텅 비었습니다. 다음번엔 생각할 것도 없이 입력을 해야 합니다.

 

스택의 TOP이 D가 되었습니다. 이번에 출력해야 될 것은 C이므로, TOP이 C가 될 때까지 입력(PUSH)을 계속합니다.

이제 스택의 TOP이 C가 되었습니다. 다음번엔 출력(POP)을 해야 합니다.

이제 스택의 TOP은 D입니다. 다음 출력해야 할 순서도 D이므로 출력(POP)을 한번 더 해주면 됩니다.

문제의 조건대로 A, B, C, D 순으로 출력을 마쳤습니다.

그럼 총 PUSH는 4번, POP도 4번 실행되었으므로 정답은 1번입니다.

 

 

 

 

https://youtube.com/playlist?list=PLboXycXmAIDuukQ2A6EvMZI-x1IMy3Xc-

전자계산기조직응용기사 필기