스택
스택은 쌓다라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조로 컴퓨터에서 정말 많이 사용되는 자료구조이다. 기본적으로 후입선출(後入先出 / LIFO: Last In First Out) 특성을 가지며, 접근 방법은 언제나 목록의 끝에서만 일어난다. 즉 스택은 한 쪽 끝(맨 위)에서만 자료를 넣거나 뺄 수 있는 선형 구조으로 되어 있다.
스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고 바닥부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element)라고 하며 스택에 요소가 하나도 없을 때를 공백 스택(empty stack)이라고 한다.
1. 시스템 스택을 이용한 함수 호출
컴퓨터에서 어떤 함수의 실행이 끝나면 자신을 호출한 함수로 되돌아가는데 이때 스택이 사용된다. 즉 스택은 복귀할 주소를 기억하는데 사용된다. 시스템 스택(운영체제가 사용하는 스택)에는 함수가 호출될 때마다 활성 레코드가 만들어지며 여기에 복귀주소가 저장된다. 활성 레코드에는 프로그램 카운터 뿐만 아니라 함수 호출 시 매개변수와 함수 내부에서 선언된 지역 변수들이 같이 생성된다.
2. 스택의 구현
스택을 구현하는 방법에는 배열을 활용하는 방법과 연결 리스트를 활용하는 방법이 있다. 배열을 활용하면 구현이 간단하고 성능이 우수한 반면에 스택의 크기가 고정되는 약점이 있다. 연결 리스트를 활용하면 구현은 복잡하지만 스택의 크기를 필요에 따라 가변적으로 할 수 있다. 여기서는 배열을 활용해 스택을 구현했고 연결 리스트를 활용한 스택은 연결 리스트를 정리한 파트에 구현해 놓았다.
2-1. 전역 변수로 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100 // 스택의 최대 크기
/* 1. 스택의 요소를 int 자료형으로 하기 */
typedef int element;
/* 2. 스택의 요소를 구조체로 하기
#define MAX_STRING 100
typedef struct
{
int student_no;
char name[MAX_STRING];
char address[MAX_STRING];
} element;
*/
element stack[MAX_STACK_SIZE]; // 1차원 배열
int top = -1;
// 공백 상태 검출 함수
int is_empty()
{
return (top == -1);
}
// 포화 상태 검출 함수
int is_full()
{
return (top == (MAX_STACK_SIZE - 1));
}
// 삽입 함수
void push(element item)
{
if (is_full())
{
fprintf(stderr, "스택 포화 에러\n");
return ;
}
else
stack[++top] = item;
}
// 삭제 함수
element pop()
{
if (is_empty())
{
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else
return stack[top--];
}
// 피크 함수
element peek()
{
if (is_empty())
{
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else
return stack[top];
}stack배열과 top을 전역 변수로 선언하면 구현은 쉽지만 하나의 프로그램에서 여러 개의 스택을 동시에 사용하기가 어렵다. 이 문제는 stack배열과 top을 하나의 구조체로 결합시키고 이 구조체의 포인터를 함수로 전달하는 방법으로 해결할 수 있다.
2-2. 스택을 포인터로 전달하는 방법으로 구현
#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)--];
}
// 피크 함수
element peek(StackType *s)
{
if (is_empty(s))
{
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else
return s->data[s->top];
}C언어에서의 함수 매개 변수 전달 방식은 기본적으로 값 전달 방식(call by value)이다. 따라서 함수의 매개 변수로 구조체의 포인터를 전달해야 원본을 수정할 수 있다.
2-3. 동적 배열 스택으로 구현
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct
{
element *data;
int capacity;
int top;
} StackType;
// 스택 초기화 함수
void init_stack(StackType *s)
{
s->capacity = 1;
s->top = -1;
s->data = (element *)malloc(s->capacity * sizeof(element));
}
// 공백 상태 검출 함수
int is_empty(StackType *s)
{
return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
return (s->top == (s->capacity - 1));
}
// 삽입 함수
void push(StackType *s, element item)
{
if (is_full(s))
{
s->capacity *= 2;
s->data = (element *)realloc(s->data, s->capacity * sizeof(element));
}
s->data[++(s->top)] = item;
}
// 삭제 함수
element pop(StackType *s)
{
if (is_empty(s))
{
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else
return s->data[(s->top)--];
}
// 피크 함수
element peek(StackType *s)
{
if (is_empty(s))
{
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else
return s->data[s->top];
}앞에서 배열을 활용한 구현은 스택의 크기가 컴파일 시간에 결정되었다. 위의 구현은 동적할당을 하여 컴파일 시간이 아닌 실행 시간에 메모리를 할당 받을 수 있다. 이 기능을 사용하면 필요할 때마다 스택의 크기를 동적으로 늘릴 수 있다.
3. 스택의 응용
3-1. 괄호 검사 문제
대괄호 [], 중괄호 {}, 소괄호() 등의 괄호는 쌍이 되게끔 사용해야 하고 서로 다른 종류의 괄호의 쌍은 서로를 교차할 수 없다. 괄호가 올바르게 사용되었는지는 스택을 사용하여 검사할 수 있다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
// 2-2에서 구현한 스택 코드를 삽입하되 element는 다음과 같이 변경
typedef char element;
// 2-2의 스택 코드 삽입 끝
int check_matching(const char *in)
{
StackType s;
char ch, open_ch;
int n = strlen(in); // 문자열의 길이
init_stack(&s); // 스택의 초기화
for (int 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;
}3-2. 중위 표기식을 후위 표기식으로 변환
수식은 연산자와 피연산자, 괄호로 이루어져있고, 연산자들은 우선순위가 높은 순서대로 계산이된다. 컴파일러는 스택을 이용하여 수식을 계산한다. 수식을 표현하는 방법에는 중위(infix), 후위(postfix), 전위(prefix)의 3가지 방법이 있다. 인간은 주로 주위 표기법을 사용하지만 컴파일러는 주로 후기 표기법을 사용한다. 따라서 프로그래머가 수식을 중위 표기법으로 작성하면 컴파일러는 이것을 후위 표기법으로 변환 후에 스택을 이용하여 계산한다. 후위 표기식으로 표현된 수식을 계산하기 전에 중위 표기식을 후위 표기식으로 변환해야 한다. 다음은 스택을 이용하여 중위 표기식을 후위 표기로 변환하는 프로그램이다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
// 2-2에서 구현한 스택 코드를 삽입하되 element는 다음과 같이 변경
typedef char element;
// 2-2의 스택 코드 삽입 끝
// 연산자의 우선순위 반환
int prec(char op)
{
switch (op)
{
case '(' : case ')' :
return 0;
case '+' : case '-' :
return 1;
case '*' : case '/' :
return 2;
}
return -1;
}
// 중위 표기 수식 → 후위 표기 수식
void infix_to_postfix(char exp[])
{
char ch, top_op;
int len = strlen(exp);
StackType s;
init_stack(&s);
for (int i = 0; i < len; i++)
{
ch = exp[i];
switch (ch)
{
case '+' : case '-' : case '*' : case '/' : // 연산자
// 스택에 있는 연산자의 우선순위가 더 크거나 같으면 출력
while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
printf("%c", pop(&s));
push(&s, ch);
break ;
case '(' : // 왼쪽 괄호
push(&s, ch);
break ;
case ')' : // 오른쪽 괄호
top_op = pop(&s);
// 왼쪽 괄호를 만날 때까지 출력
while (top_op != '(')
{
printf("%c", top_op);
top_op = pop(&s);
}
break ;
default : // 피연산자
printf("%c", ch);
break ;
}
}
while (!is_empty(&s)) // 스택에 저장된 연산자들 출력
printf("%c", pop(&s));
}3-3. 후위 표기 수식의 계산
중위 표기식을 후위 표기식으로 변환했으면 또 다시 스택을 이용하여 다음과 같이 수식을 계산하면 된다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
// 2-2에서 구현한 스택 코드를 삽입하되 element는 다음과 같이 변경
typedef char element;
// 2-2의 스택 코드 삽입 끝
// 후위 표기 수식 계산 함수
int eval(char exp[])
{
int op1, op2, value;
int len = strlen(exp);
char ch;
StackType s;
init_stack(&s);
for (int i = 0; i < len; i++)
{
ch = exp[i];
if (ch != '+' && ch != '-' && ch != '*' && ch != '/')
{
value = ch - '0'; // 입력이 피연산자이면
push(&s, value);
}
else
{ // 연산자이면 피연산자를 스택에서 제거
op2 = pop(&s);
op1 = pop(&s);
switch (ch)
{ // 연산을 수행하고 스택에 저장
case '+' :
push (&s, op1 + op2);
break ;
case '-' :
push (&s, op1 - op2);
break ;
case '*' :
push (&s, op1 * op2);
break ;
case '/' :
push (&s, op1 / op2);
break ;
}
}
}
return pop(&s);
}3-4. 미로 문제
미로를 탈출하기 위해서는 미로를 체계적으로 탐색하여야 한다. 가장 기본적인 방법은 하나의 경로를 선택하여 한번 시도해보고 안되면 다시 다른 경로를 시도하는 것이다. 현재의 경로가 안 될 경우엔 다른 경로를 선택해야 하는데 다른 경로들이 어딘가에 저장되어 있어야 한다. 가능한 경로 중 가장 가까운 경로를 저장하는 것이 좋을 것이고 가장 최근에 저장한 경로가 추출되는 자료구조인 스택이 적절할 것이다. 현재 위치에서 갈 수 있는 좌표를 기억하였다가 막다른 길을 만나면 아직 가보지 않은 좌표 중 가장 가까운 곳으로 돌아가서 새로운 경로를 찾아보는 것이다. 또 한번 지나간 곳은 다시 가면 안되기 때문에 좌표를 지나갈 때마다 이미 방문했다는 표시를 남겨야 한다.
다음의 프로그램은 현재 위치에서 이동이 가능한 칸들의 위치를 위, 아래, 왼쪽, 오른쪽의 순서로 스택에 저장하고 스택에서 맨위의 위치를 꺼내어 현재의 위치로 한 다음, 같은 작업을 반복한다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6
// 2-2에서 구현한 스택 코드를 삽입하되 element는 다음과 같이 변경
typedef struct
{
short r;
short c;
} element;
// 2-2의 스택 코드 삽입 끝
element here = { 1, 0 };
element entry = { 1, 0 };
char maze[MAZE_SIZE][MAZE_SIZE] = {
{ '1', '1', '1', '1', '1', '1' },
{ 'e', '0', '1', '0', '0', '1' },
{ '1', '0', '0', '0', '1', '1' },
{ '1', '0', '1', '0', '1', '1' },
{ '1', '0', '1', '0', '0', 'x' },
{ '1', '1', '1', '1', '1', '1' }
};
// 위치를 스택에 삽입
void push_loc(StackType *s, int r, int c)
{
if (r < 0 || c < 0)
return ;
if (maze[r][c] != '1' && maze[r][c] != '.')
{
element tmp;
tmp.r = r;
tmp.c = c;
push(s, tmp);
}
}
// 미로를 화면에 출력
void maze_print(char maze[MAZE_SIZE][MAZE_SIZE])
{
printf("\n");
for (int r = 0; r < MAZE_SIZE; r++)
{
for (int c = 0; c < MAZE_SIZE; c++)
printf("%c", maze[r][c]);
}
printf("\n");
}
References
