스택(Stack)은 선형 자료구조의 한 종류로, 데이터를 한쪽 끝에서만 삽입하고 삭제할 수 있는 구조입니다. 이러한 LIFO(Last In First Out) 특성 덕분에 수식 계산, 괄호 검사, 함수 호출 관리 등 다양한 분야에서 활용됩니다.
스택 기본 연산 알고리즘
Push( ) — 데이터 삽입
먼저 스택 오버플로우(overflow) 여부를 확인합니다.
if (top == n-1)
printf("stack over flow");오버플로우가 아니라면, top 위치를 하나 증가시킨 후 요소를 삽입합니다.
top++; a[top] = item;
Pop( ) — 데이터 삭제
스택 언더플로우(underflow), 즉 스택이 비어 있는지 먼저 확인합니다.
if (top == -1)
printf("stack under flow");스택에 요소가 있다면 최상단(top)의 값을 꺼내고 top을 감소시킵니다.
item = a[top]; top--;
Display( ) — 전체 출력
스택이 비어 있는지 확인한 뒤,
if (top == -1)
printf("stack is empty");비어 있지 않다면 아래와 같이 모든 요소를 출력합니다.
for (i = 0; i <= top; i++)
printf("%d", a[i]);스택의 대표적인 응용: 수식 표현과 변환
스택은 C 언어에서 수식(expression)의 변환과 평가에 널리 사용됩니다. 여기서 수식이란 피연산자(operand)와 연산자(operator)가 규칙에 맞게 결합된 형태를 의미합니다.
수식의 세 가지 표기법
중위 표기법(Infix) — 연산자가 피연산자 사이에 위치합니다. 예: A+B
전위 표기법(Prefix) — 연산자가 피연산자 앞에 위치합니다. 예: +AB
후위 표기법(Postfix) — 연산자가 피연산자 뒤에 위치합니다. 예: AB+
컴퓨터는 중위 표기법보다 후위 표기법을 평가하는 것이 훨씬 효율적입니다. 괄호나 연산자 우선순위를 고려할 필요 없이 왼쪽부터 차례대로 처리하면 되기 때문입니다.
후위 표기식(Postfix) 평가 알고리즘
후위 표기식을 평가하는 절차는 다음과 같습니다.
- 입력 문자열을 왼쪽에서 오른쪽으로 한 글자씩 스캔합니다.
- 각 입력 문자에 대해 다음을 수행합니다.
- 숫자인 경우: 해당 값을 스택에 push 합니다.
- 연산자인 경우: 스택에서 상위 두 개의 값을 pop 하고, 두 값에 연산자를 적용한 결과를 다시 push 합니다.
- 문자열의 끝('\0')을 만난 경우: 스택에 남아 있는 마지막 값이 곧 최종 결과입니다.
C 언어 구현 예제
다음은 후위 표기식을 평가하는 C 프로그램입니다.
#include<stdio.h>
int top = -1, stack[100];
main() {
char a[50], ch;
int i, op1, op2, res, x;
void push(int);
int pop();
int eval(char, int, int);
printf("enter a postfix expression:");
gets(a);
for (i = 0; a[i] != '\0'; i++) {
ch = a[i];
if (ch >= '0' && ch <= '9')
push(ch - '0'); // 문자를 숫자로 변환하여 push
else {
op2 = pop(); // 두 번째 피연산자
op1 = pop(); // 첫 번째 피연산자
res = eval(ch, op1, op2);
push(res); // 연산 결과를 다시 push
}
}
x = pop();
printf("evaluated value = %d", x);
getch();
}
void push(int n) {
top++;
stack[top] = n;
}
int pop() {
int res;
res = stack[top];
top--;
return res;
}
int eval(char ch, int op1, int op2) {
switch (ch) {
case '+': return (op1 + op2);
case '-': return (op1 - op2);
case '*': return (op1 * op2);
case '/': return (op1 / op2);
}
}참고: 원본 코드에서는 push('0')으로 되어 있지만, 실제 숫자 값을 저장하려면 push(ch - '0')처럼 문자를 정수로 변환해야 올바른 결과를 얻을 수 있습니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Run 1: enter a postfix expression:45+ evaluated value = 9 Run 2: enter a postfix expression:352*+ evaluated value = 13
Run 1에서는 4+5=9가, Run 2에서는 3+(5×2)=13이 계산됩니다. 이처럼 스택을 활용하면 복잡한 수식도 간단한 push/pop 연산만으로 효율적으로 평가할 수 있습니다.