교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)
4.1 스택이란?
스택이란 '(건초, 밀집 따위를 쌓아놓은) 더미, 낟가리'를 의미한다. 식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등이 스택의 전형적인 예이다. 스택에서 가장 최근에 들어온 것이 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO: Last-In First-Out0이라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 스택에서 입출력이 이루어지는 부분을 스택 상단(Stack top)이라 하고 반대쪽인 바닥 부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element)라 부른다. 스택에 요소가 하나도 없을 때 그러한 스택을 공백 스택(empty stack)이라고 한다. 스택은 특히 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 매우 긴요하게 사용된다.
시스템 스택을 이용한 함수 호출
컴퓨터 안에서는 수많은 함수 호출이 이루어지는데, 함수는 실행이 끝나면 자신을 호출한 함수로 되돌아가야 한다. 이때 스택이 사용된다. 즉 스택은 복귀할 주소를 기억하는 데 사용된다. 함수는 호출된 역순으로 되돌아가야 하기 때문이다.
추상 자료형 스택
스택은 추상 자료형으로 정의하여 보자. 추상 자료형으로서의 스택은 0개 이상의 요소를 가지는 선형 리스트의 일종으로 정의되며 스택에 요소를 추가하거나 삭제하는 연산과 현재 스택 상태를 검사하는 연산들로 구성된다. 스택에는 두 가지의 기본 연산이 있다. 하나는 삽입 연산으로 push 연산이라고 하고 또 하나는 삭제 연산으로 pop연산이라고 한다.
4.2 스택의 구현
스택에는 가장 최근에 업력 되었던 자료를 가리키는 top 변수가 필요하다. top 변수는 스택이 비어 있으면 -1의 값을 갖는다. top의 값이 0이면 배열의 인덱스 0에 데이터가 있다는 것을 의미하기 때문이다. 스택에 저장되는 요소의 타입은 항상 element라고 가정한다. 만약 정수 스택이 필요하면 element 타입을 정수(typedef)로 정의하면 된다. 일반적인 경우에는 element 타입이 구조체가 될 것이다. 구조체 안에는 무엇이든지 넣을 수 있기 때문이다.
#include <stdio.h>
#include <stdlib.h>
// 차후에 스택이 필요하면 여기를 복사하여 붙인다.
// ===== 스택 코드의 시작 =====
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
element data[MAX_STACK_SIZE];
int top;
} StackType;
// 스택 초기화 함수
void init_stack(StackType *s)
{
s->top = -1;
}
// 공백 상태 검출 함수
int is_empty(StackType *s)
{
return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType* s)
{
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)--];
}
//피크함수: top 데이터확인
element peek(StackType* s)
{
if (is_empty(s)) {
fprint(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[s->top];
}
// ===== 스택 코드의 끝 =====
int main(void)
{
StackType s;
init_stack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
}
4.4 스택의 응용: 괄호 검사 문제
프로그램에서는 여러 가지 종류의 괄호들이 사용되는데, 이들이 올바르게 사용되었는지를 스택을 사용하여 검사해 보자. 괄호의 검사 조건은 다음의 3가지이다.
- 조건 1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
- 조건 2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
- 조건 3: 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다.
스택을 사용하여 왼쪽 괄호들을 만나면 계속 삽입하다가 오른쪽 괄호들이 나오면 스택에서 가장 최근의 왼쪽괄호를 꺼내여 타입을 맞추어보면 쉽게 괄호들의 오류를 검사할 수 있다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
// 스택 코드 추가
typedef char element; // 스택 코드 교체
// ...
// 스택 코드 추가
int check_matching(const char* in)
{
StackType s;
char ch, open_ch;
int i, n = strlen(in);
init_stack(&s);
for (i = 0; i < n; i++) {
ch = in[i];
switch (ch) {
case '(': case '[': case '{':
push(&s, ch);
break;
case ')': case ']': case '}':
if (is_empty(&s)) return 0;
else {
open_ch = pop(&s);
if ((open_ch == '(' && ch != ')') ||
(open_ch == '[' && ch != ']') ||
(open_ch == '{' && ch != '}')) {
return 0;
}
break;
}
}
}
if (!is_empty(&s)) return 0;
return 1;
}
int main(void)
{
char* p = "{ A[(i+1)]=0; }";
if (check_matching(p) == 1)
printf("%s 괄호검사성공\n", p);
else
printf("%s 괄호검사실패\n", p);
return 0;
}
4.5 스택의 응용: 후위 표기 수식의 계산
수식은 연산자와 피연산자, 괄호로 이루어져 있다. 연산자들은 우선순위가 있어서 우선순위가 높은 연산자가 먼저 계산된다. 이를 스택을 사용하여 계산해보자. 수식을 표기하는 방법에는 중위(infix), 후위(postfix), 전위(prefix)의 3가지 방법이 있다. 연산자가 피연산자 사이에 있으면 중위이고 연산자가 피연산자 뒤에 있으면 후위이다. 연산자가 피연산자 앞에 있으면 저누이라고 한다. 여기서는 후위 표기 수식을 어떻게 스택을 이용하여 계산할 수 있는지 살펴보자. 후위 표기 수식을 계산하려면 먼저 수식을 왼쪽에서 오른쪽으로 스캔하여 피연산자이면 스택에 저장하고 연산자이면 필요한 수만큼의 피연산자를 스택에서 꺼내 연산을 실행하고 연산의 결과를 다시 스택에 저장하면 된다.
중위표기수식을 후위표기수식으로 변환
프로그래머가 입력하는 수식의 형태는 중위 표기법이다. 따라서 중위 표기 수식을 후위표기 수식으로 변경하는 것이 필요하다. 이를 코드로 살펴보자.
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
// 스택 코드 추가
typedef char element; // 스택 코드 교체
// ...
// 스택 코드 추가 끝
// 연산자 우선순위
int prec(char op)
{
switch (op) {
case '(': case ')': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2;
}
return -1;
}
//중위 표기 수식 -> 후위 표기 수식
void inflx_to_postfix(char exp[])
{
int i = 0;
char ch1, top_op;
int len = strlen(exp);
StackType s1;
init_stack(&s1);
for (i = 0; i < len; i++) {
ch1 = exp[i];
switch (ch1) {
case '+': case '-': case '*': case '/':
while (!is_empty(&s1) && (prec(ch1) <= prec(peek(&s1))))
printf("%c", pop(&s1));
push(&s1, ch1);
break;
case '(':
push(&s1, ch1);
break;
case ')':
top_op = pop(&s1);
while (top_op != '(') {
printf("%c", top_op);
top_op = pop(&s1);
}
break;
default: //피연산자
printf("%c", ch1);
break;
}
}
while (!is_empty(&s1))
printf("%c", pop(&s1));
}
// 후위 표기 수식 계산함수
int eval(char exp[])
{
int op1, op2, value, i = 0;
int len = strlen(exp);
char ch2;
StackType s2;
init_stack(&s2);
for (i = 0; i < len; i++) {
ch2 = exp[i];
if (ch2 != '+' && ch2 != '-' && ch2 != '*' && ch2 != '/') {
value = ch2 - '0';
push(&s2, value);
}
else {
op2 = pop(&s2);
op1 = pop(&s2);
switch (ch2) {
case '+': push(&s2, op1 + op2); break;
case '-': push(&s2, op1 - op2); break;
case '*': push(&s2, op1 * op2); break;
case '/': push(&s2, op1 / op2); break;
}
}
}
return pop(&s2);
}
int main(void)
{
char* s = "(2+3)*4+9";
int result;
printf("중위표시수식 %s \n", s);
printf("후위표기수식 ");
inflx_to_postfix(s);
printf("\n");
result = eval("23+4*9+");
printf("결과값은 %d\n", result);
return 0;
}'CS과목 > 자료구조' 카테고리의 다른 글
| [CS과목/자료구조] 06 연결 리스트 1 (0) | 2024.09.15 |
|---|---|
| [CS과목/자료구조] 05 큐 (0) | 2024.09.15 |
| [CS과목/자료구조] 03 배열, 구조체, 포인터 (0) | 2024.09.15 |
| [CS과목/자료구조] 02 순환 (0) | 2024.09.15 |
| [CS과목/자료구조] 01 자료구조와알고리즘 (0) | 2024.09.15 |