방송대 자료구조 3강 : 스택 연산과 후위표기식 계산

방송대 자료구조 3강: 스택 연산과 후위표기식 계산

스택 문제는 원소를 많이 그리는 것보다 top이 지금 무엇을 가리키는지 정확히 추적하는 일이 먼저입니다. 이 글은 생성·삽입·삭제 뒤의 상태를 직접 계산하고, ++top과 top--의 순서를 해석하며, 같은 원리가 중위식을 후위식으로 바꾸고 계산하는 과정에 어떻게 쓰이는지 연결합니다.

한쪽 끝만 열어 두면 삭제 순서가 자동으로 정해진다

책을 한쪽에서만 쌓고 꺼낸다고 생각해 보자. 먼저 놓은 책은 아래에 남고, 가장 나중에 놓은 책부터 꺼내게 된다. 스택(stack)은 이처럼 삽입과 삭제가 한곳, 즉 스택의 맨 위(top)에서만 일어나는 유한 순서 리스트다. 그래서 나중에 들어온 원소가 먼저 나오는 후입선출(LIFO) 관계가 만들어진다.

중요한 점은 “거꾸로 저장한다”가 아니다. 원소는 삽입된 순서대로 아래에서 위로 쌓이지만, 접근 가능한 출구가 top 하나뿐이어서 삭제 순서가 삽입 순서의 역순이 된다. 예를 들어 A, B, C, D를 차례로 삽입하면 top은 D이고, 삭제 결과는 D, C, B, A 순서다.

판단 핵심: 스택 그림에서는 가장 먼저 들어온 원소가 어디 있는지보다 현재 top이 어느 원소를 가리키는지 먼저 찾는다. 다음 pop의 대상은 언제나 top의 원소다.

추상 자료형은 저장 모양보다 허용되는 연산을 먼저 약속한다

스택의 추상 자료형(ADT)은 스택을 배열로 구현할지 연결 구조로 구현할지 정하지 않고, 스택 객체와 그 객체에 적용할 연산의 의미를 정의한다. 강의자료의 스택 객체는 0개 이상의 원소를 갖는 유한 순서 리스트이며, 기본 연산은 다음과 같이 읽을 수 있다.

연산	입력과 결과	먼저 확인할 조건
CreateStack(maxStackSize)	최대 크기가 정해진 빈 스택을 생성해 반환	최대 크기는 양의 정수인가?
Push(stack, item)	item을 top 위에 삽입	스택이 가득 차지 않았는가?
Pop(stack)	top 원소를 삭제하고 그 값을 반환	스택이 비어 있지 않은가?
StackIsFull(stack)	현재 원소 수가 최대 크기와 같은지 판정	고정 크기 스택의 용량에 도달했는가?
StackIsEmpty(stack)	생성 직후와 같은 빈 상태인지 판정	삭제할 원소가 하나라도 있는가?

가득 찬 스택에 삽입하려는 상황을 오버플로, 빈 스택에서 삭제하려는 상황을 언더플로라고 부른다. 두 오류는 반대 조건에서 발생한다. push 전에 full을, pop 전에 empty를 검사하는 이유다.

오개념 교정: pop은 top 원소를 “읽기만” 하는 연산이 아니다. 값을 반환하는 동시에 스택에서 제거한다. 반대로 empty와 full 판정은 상태를 검사할 뿐 원소 순서를 바꾸지 않는다.

연산 기록은 원소 목록과 top을 함께 갱신해야 한다

강의자료의 용량 3 스택에 다음 연산을 적용해 보자. CreateStack(3), Push(S), Push(T), Pop(), Push(R), Push(P), Push(Q), Pop() 순서다.

단계	연산	아래→위 원소	top 또는 결과
①	CreateStack(3)	빈 상태	top 없음
②	Push(S)	S	S
③	Push(T)	S, T	T
④	Pop()	S	T 반환, 새 top은 S
⑤	Push(R)	S, R	R
⑥	Push(P)	S, R, P	P, 스택 가득 참
⑦	Push(Q)	S, R, P	full이므로 상태 변화 없음
⑧	Pop()	S, R	P 반환, 새 top은 R

⑦에서 Q가 들어가지 못했다는 점이 핵심이다. 용량 3에 이미 S, R, P가 있으므로 StackIsFull이 참이다. 오류가 발생했는데도 Q를 그려 넣으면 이후 pop의 결과까지 모두 달라진다.

직접 구성한 짧은 추적

용량 4인 빈 스택에 push(8), push(3), pop(), push(5)를 적용하면 상태는 빈 상태 → [8] → [8, 3] → [8] → [8, 5]다. 삭제된 값은 3이고 최종 top은 5다. 스택을 풀 때는 각 단계마다 “반환된 값”과 “남은 상태”를 따로 기록하면 삭제된 값을 스택 안에 남겨 두는 실수를 막을 수 있다.

배열 스택의 불변식은 top과 원소 수를 연결한다

강의의 배열 구현은 크기 10인 배열과 정수 top을 사용한다. 빈 스택에서 top=-1로 시작하고 첫 원소는 인덱스 0에 저장된다.

#define STACK_SIZE 10
typedef int element;
element stack[STACK_SIZE];
int top = -1;

이 표현에서는 다음 관계가 모든 정상 상태에서 유지되어야 한다.

• 빈 스택: top=-1
• 원소 수: top+1
• 가장 위 원소: stack[top]
• 가득 찬 상태: top=STACK_SIZE-1

예를 들어 STACK_SIZE=10이면 유효한 인덱스는 0부터 9까지다. 따라서 top=9일 때 이미 가득 찼다. top=10이 된 뒤 full을 검사하면 배열 범위를 벗어난 뒤에야 오류를 발견하게 된다.

상태 검산: 원소가 k개라면 top=k-1이어야 한다. 그림의 원소 수와 top 인덱스가 이 식을 만족하지 않으면 삽입·삭제 중 하나의 갱신 순서가 잘못된 것이다.

삽입은 먼저 올리고 저장하며 삭제는 먼저 읽고 내린다

배열 스택의 핵심 코드는 전위 증가와 후위 감소의 평가 순서에 들어 있다. 개념을 드러내는 의사코드로 먼저 쓰면 다음과 같다.

push(item):
  if top >= STACK_SIZE - 1: full 처리
  else:
    top = top + 1
    stack[top] = item

pop():
  if top == -1: empty 처리
  else:
    item = stack[top]
    top = top - 1
    return item

C 표현 stack[++top] = item은 top을 먼저 1 증가시킨 뒤 그 위치에 item을 저장한다. 빈 상태 top=-1에서 첫 삽입 위치가 0이 되는 이유다. 반면 return stack[top--]은 현재 stack[top]의 값을 먼저 반환 대상으로 정한 뒤 top을 1 감소시킨다.

표현	실행 순서	스택에서의 의미
stack[++top] = item	top 증가 → 새 위치에 저장	기존 top 위에 원소 삽입
stack[top--]	현재 위치의 값 사용 → top 감소	현재 top 원소를 반환하고 삭제
stack[top++] = item	현재 위치에 저장 → top 증가	현재 표현에서는 기존 top을 덮어쓸 수 있어 부적합
stack[--top]	top 감소 → 낮아진 위치의 값 사용	현재 top 원소를 건너뛰므로 부적합

강의의 예처럼 a=5일 때 b=a--는 b에 5를 넣은 뒤 a를 4로 만들고, b=--a는 a를 4로 만든 뒤 b에 4를 넣는다. 같은 감소 연산이라도 값이 사용되는 시점이 다르다.

되돌아갈 지점을 보관해야 하는 작업은 스택과 잘 맞는다

스택은 가장 최근에 중단하거나 시작한 작업을 먼저 복원해야 하는 상황에 쓰인다. 강의자료는 변수 메모리의 할당과 수집을 위한 시스템 스택, 서브루틴 호출 관리, 연산자 우선순위에 따른 수식 계산, 인터럽트 처리 뒤 되돌아갈 명령 위치의 저장, 컴파일러와 순환 호출 관리를 예로 든다.

이 사례들의 공통점은 “최근 작업이 먼저 끝나야 그 이전 작업으로 돌아갈 수 있다”는 중첩 관계다. 함수 A가 B를 호출하고 B가 C를 호출했다면 C가 끝난 뒤 B로, B가 끝난 뒤 A로 돌아가야 한다. 호출 순서 A→B→C와 복귀 순서 C→B→A가 반대이므로 스택의 후입선출 규칙과 맞는다.

선택 기준: 단순히 데이터를 임시 저장한다는 이유만으로 스택을 고르지 않는다. 가장 최근 항목을 먼저 처리하거나, 열린 작업을 역순으로 닫아야 할 때 스택이 적합하다.

전위·중위·후위 표기는 연산자의 위치만 다르게 약속한다

중위표기법(infix)은 연산자를 두 피연산자 사이에, 전위표기법(prefix)은 앞에, 후위표기법(postfix)은 뒤에 놓는다. 같은 A+B는 각각 A+B, +AB, AB+로 표현된다.

표기법	A+B	(A-B)×C	읽는 기준
중위	A+B	(A-B)*C	우선순위와 괄호로 계산 순서 결정
전위	+AB	*-ABC	연산자 뒤의 두 식을 피연산자로 읽음
후위	AB+	AB-C*	연산자 앞에서 완성된 두 식을 꺼내 계산

중위식 A-((B+K)/D)를 후위식으로 바꾸려면 가장 안쪽 계산부터 연산자를 뒤로 보낸다. B+K는 BK+, 이를 D로 나누면 BK+D/, 마지막으로 A에서 빼면 ABK+D/-가 된다. 후위식에는 같은 계산 순서를 나타내기 위한 괄호가 필요하지 않다.

괄호 이동법으로 변환을 검산한다

중위식을 우선순위에 맞춰 (피연산자 연산자 피연산자) 꼴로 완전히 묶고, 각 괄호 안의 연산자를 오른쪽 끝으로 옮긴 뒤 괄호를 제거하면 후위식이 된다. 직접 구성한 A*(B+C)는 (A*(B+C)) → (A(BC+)*) → ABC+* 순서다.

후위식 계산에서는 두 번째 pop이 왼쪽 피연산자다

후위표기식은 왼쪽부터 한 기호씩 읽는다. 피연산자면 스택에 삽입하고, 연산자면 피연산자 두 개를 삭제해 계산한 결과를 다시 삽입한다. 강의자료의 369*+를 따라가면 다음과 같다.

읽은 기호	수행	아래→위 스택
3	피연산자 3 push	3
6	피연산자 6 push	3, 6
9	피연산자 9 push	3, 6, 9
*	9를 oper2, 6을 oper1로 pop하여 6×9=54 push	3, 54
+	54를 oper2, 3을 oper1로 pop하여 3+54=57 push	57
끝	마지막 값 pop	결과 57

교환법칙이 성립하는 덧셈과 곱셈만 보면 pop 순서를 뒤집어도 우연히 같은 답이 나온다. 뺄셈과 나눗셈에서는 오류가 드러난다. 연산자를 만났을 때 첫 번째 pop은 오른쪽 피연산자 oper2, 두 번째 pop은 왼쪽 피연산자 oper1이며 계산은 oper1 연산자 oper2 순서다.

직접 구성한 82/5-를 계산하면 8과 2를 넣고 /에서 8÷2=4를 넣는다. 이어 5를 넣고 -에서 4-5=-1을 넣는다. 첫 pop을 왼쪽 피연산자로 착각하면 2÷8과 5-4가 되어 전혀 다른 결과가 나온다.

후위식 계산 절차: 기호를 왼쪽부터 읽고, 피연산자는 push한다. 연산자라면 oper2=pop(), oper1=pop() 순서로 꺼내 oper1 연산자 oper2를 계산해 push한다. 입력이 끝났을 때 스택에 결과 하나만 남는지 확인한다.

스택 문제는 상태·경계·피연산자 순서로 검산한다

새 문제를 만나면 다음 세 층으로 확인한다.

1. 상태: 연산 전후의 원소 목록과 top을 함께 적고, 원소 수가 top+1인지 확인한다.
2. 경계: push 전에는 top>=size-1, pop 전에는 top==-1인지 검사한다.
3. 순서: 삽입은 top을 먼저 증가시키고, 삭제는 현재 값을 먼저 사용한 뒤 감소시킨다. 후위식에서는 먼저 pop한 값이 오른쪽 피연산자다.

이 세 기준은 서로 연결된다. top 갱신이 틀리면 경계 검사가 한 칸 어긋나고, 잘못된 pop 순서는 후위식의 뺄셈·나눗셈 결과를 바꾼다. 따라서 최종 값만 맞추지 말고 중간 상태가 스택의 불변식을 계속 만족하는지 확인해야 한다.

핵심 개념 정리

• 접근 규칙: 삽입과 삭제가 top 한곳에서 일어나므로 나중에 삽입한 원소가 먼저 삭제된다.
• ADT 계약: 생성·push·pop·full·empty는 구현 방법과 분리해 각 연산의 조건과 결과를 정의한다.
• 배열 상태: 빈 상태는 top=-1, 원소 수는 top+1, 가득 찬 상태는 top=size-1이다.
• 갱신 순서: push는 ++top 뒤 저장하고, pop은 현재 stack[top]을 사용한 뒤 top--한다.
• 후위식: 피연산자를 쌓고 연산자에서 두 값을 꺼내며, 두 번째로 꺼낸 값이 왼쪽 피연산자다.

스택을 풀 때는 “가장 위가 무엇인가”에서 시작해 원소 목록과 top을 동시에 갱신하세요. 그다음 빈 상태와 가득 찬 상태의 경계를 검사하고, 코드에서는 값 사용과 top 증감의 선후를 분리해 읽습니다. 수식 문제로 넘어가도 원리는 같습니다. 피연산자를 쌓고, 연산자가 요구하는 최근 두 값을 올바른 좌우 순서로 꺼내면 스택의 후입선출 규칙이 계산 순서를 대신 관리합니다.

예상문제 10선

1. 빈 스택에 A, B, C를 차례로 push한 뒤 두 번 pop할 때 반환되는 순서는?

① A, B ② B, C ③ C, B ④ C, A

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 먼저 들어온 원소부터 꺼내는 선입선출 순서를 적용했다.
• ② 오답: 첫 삭제 전에 top은 C이므로 B가 먼저 반환될 수 없다.
• ③ 정답: top의 C가 먼저 삭제되고 그 아래 B가 다음 top이 된다.
• ④ 오답: C를 꺼낸 뒤 B를 건너뛰고 A를 삭제할 수 없다.

2. 빈 스택에 pop을 적용하기 전에 검사해야 할 연산은?

① StackIsEmpty ② StackIsFull ③ CreateStack ④ Push

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 삭제할 top 원소가 존재하는지 확인해 언더플로를 막는다.
• ② 오답: full 검사는 새 원소를 삽입할 공간이 있는지 확인할 때 필요하다.
• ③ 오답: CreateStack은 빈 스택을 만드는 연산이며 현재 삭제 가능 여부를 판정하지 않는다.
• ④ 오답: Push는 원소를 삽입하므로 pop의 사전 조건 검사가 아니다.

3. 용량 3인 빈 스택에 push(S), push(T), pop(), push(R)를 수행한 최종 상태는?

① 아래부터 T, R이고 top은 R ② 아래부터 S, T, R이고 top은 R ③ 아래부터 R, S이고 top은 S ④ 아래부터 S, R이고 top은 R

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: pop은 top의 T를 제거하므로 T가 남을 수 없다.
• ② 오답: 삭제된 T를 상태에 계속 포함한 결과다.
• ③ 오답: R은 기존 S 위에 삽입되므로 아래에서 위 순서를 뒤집었다.
• ④ 정답: T가 반환된 뒤 S만 남고, R이 그 위에 삽입된다.

4. 배열 스택에 원소가 6개 있고 빈 상태를 top=-1로 표현한다면 현재 top은?

① -1 ② 5 ③ 6 ④ 7

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: -1은 원소가 0개인 빈 상태의 top이다.
• ② 정답: 원소 수가 top+1이므로 6=top+1, 따라서 top은 5다.
• ③ 오답: 원소 수를 top 값과 같다고 보아 인덱스가 0부터 시작한다는 점을 놓쳤다.
• ④ 오답: 빈 상태의 -1과 첫 인덱스 0 사이의 관계를 두 칸 잘못 계산했다.

5. 현재 표현에서 push를 stack[top++] = item으로 작성하면 생길 수 있는 문제는?

① 저장 전에 top이 증가하여 첫 원소가 인덱스 1에 저장된다. ② 저장 뒤 top이 감소하여 방금 넣은 원소가 즉시 삭제된다. ③ 현재 top 위치에 먼저 저장하므로 기존 top 원소를 덮어쓰거나 빈 상태에서 잘못된 인덱스를 사용한다. ④ top 값은 바뀌지 않아 원소 수가 영원히 증가하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 이는 전위 증가 ++top을 한 칸 더 적용했다고 오해한 설명이다.
• ② 오답: 후위 증가 연산은 저장 뒤 top을 증가시키며 감소시키지 않는다.
• ③ 정답: 후위 증가는 기존 top을 인덱스로 먼저 사용하므로 현재 불변식과 맞지 않는다.
• ④ 오답: 문장 실행 뒤 top은 증가하지만 증가 시점이 잘못되었다.

6. return stack[top--]의 실행 의미로 옳은 것은?

① top을 먼저 감소시킨 뒤 그 아래 원소를 반환한다. ② top 원소를 반환하지만 top 값은 유지한다. ③ top을 먼저 증가시킨 뒤 새 위치의 원소를 반환한다. ④ 현재 top 원소의 값을 사용한 뒤 top을 1 감소시킨다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 먼저 감소하는 표현은 --top이며 현재 top 원소를 건너뛴다.
• ② 오답: 후위 감소이므로 값 사용 후 top은 1 줄어든다.
• ③ 오답: 증가 연산이 아니라 후위 감소 연산이다.
• ④ 정답: 삭제할 현재 top 값을 반환 대상으로 정한 뒤 스택 높이를 한 칸 낮춘다.

7. 중위식 A*(B+C)의 올바른 후위표기식은?

① ABC+* ② AB*C+ ③ *A+BC ④ AB+C*

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 괄호 안 B+C를 BC+로 완성한 뒤 A와 곱하므로 ABC+*다.
• ② 오답: A×B를 먼저 계산하게 되어 원래 괄호의 우선순위를 바꾼다.
• ③ 오답: 연산자를 피연산자 앞에 둔 전위표기식이다.
• ④ 오답: A+B를 먼저 계산한 뒤 C와 곱하는 식을 나타낸다.

8. 후위표기식 82/5-의 계산 결과는?

① 1 ② 3 ③ -1 ④ 15

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 마지막 뺄셈의 좌우를 바꾸어 5-4로 계산한 결과다.
• ② 오답: 나눗셈 대신 8-5처럼 일부 기호만 사용한 값이다.
• ③ 정답: 먼저 8÷2=4를 만든 뒤 4-5=-1을 계산한다.
• ④ 오답: 연산자 순서와 종류를 보존하지 않고 피연산자를 임의로 결합한 값이다.

9. 후위식 계산에서 -를 만났고 첫 pop이 2, 두 번째 pop이 8이었다. 올바른 계산은?

① 2-8=-6 ② 8-2=6 ③ 8+2=10 ④ 8÷2=4

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 첫 pop을 왼쪽 피연산자로 놓아 좌우 순서를 뒤집었다.
• ② 정답: 첫 pop은 오른쪽 oper2, 두 번째 pop은 왼쪽 oper1이므로 oper1-oper2다.
• ③ 오답: 피연산자 순서는 맞지만 주어진 뺄셈 연산자를 덧셈으로 바꿨다.
• ④ 오답: 피연산자 순서는 맞지만 연산자를 나눗셈으로 바꿨다.

10. 함수 A가 B를 호출하고 B가 C를 호출했을 때 호출 스택에서 C의 복귀 지점을 먼저 처리하는 이유는?

① 가장 오래된 호출을 먼저 종료해야 다음 호출을 시작할 수 있기 때문이다. ② 함수 이름의 알파벳 순서가 복귀 순서를 결정하기 때문이다. ③ 호출 깊이와 관계없이 메모리 주소가 작은 함수부터 끝내기 때문이다. ④ 가장 최근에 시작한 C를 끝내야 중단된 B로 돌아가고, 이후 A로 복귀할 수 있기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 중첩 호출은 가장 오래된 A가 아니라 가장 최근 호출 C부터 완료해야 한다.
• ② 오답: 복귀 순서는 이름이 아니라 호출의 중첩 순서로 결정된다.
• ③ 오답: 주소 크기가 아니라 가장 최근에 저장한 복귀 정보가 top에 있다는 점이 기준이다.
• ④ 정답: 호출 A→B→C와 복귀 C→B→A가 역순이므로 후입선출 구조가 알맞다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 용량 4 스택과 A*(B+C), 82/5- 예제는 연산을 재현하도록 직접 구성했으며 강의자료의 예와 구분했습니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 컴퓨터과학과 「자료구조」 3강 ‘스택’ 강의자료(2023)
• 외부 보충 자료: 별도 외부 자료를 사용하지 않음
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-08-18