반응형
스택이란?
가장 최근에 들어온 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO: Last-In First-Out)이라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.
삽입 연산 push(s, item)
맨위 보여주고 삭제 연산 pop(s)
공백상태? is_empty(s)
포화상태? is_full(s)
맨위 보여주기만 연산 peek(s)
스택의 구현
가장먼저 들어온 요소는 stack[0]에, 가장 최근에 들어온 요소는 stack[top]에 저장된다.
top 변수는 스택이 비어 있으면 -1의 값을 갖는다.
top과 stack 배열을 하나의 구조체로 결합시키고 이 구조체의 포인터를 함수로 전달한다. 즉 stackType이라는 새로운 구조체 타입을 만들고 여기에 stack 배열과 top을 넣는다. 이 방법에서는 StackType 구조체 안에 들어 있는 변수들을 초기화하기 위하여 init_stack()함수가 필요하다.
#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];
}
// ===== 스택 코드의 끝 =====
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));
}실행결과
3
2
1
동적 배열 스택
realloc()은 동적 메모리의 크기를 변경하는 함수로서 현재 내용은 유지하면서 주어진 크기로 동적 메모리를 다시 할당한다. 배열의 크기는 2배씩 늘어난다. 현재는 소스를 간단하게 만들기 위하여 malloc()에서 반환되는 값을 검사하는 코드는 생략하였다. 실제로는 반드시 반환되는 값이 NULL이 아닌지 검사하여야 한다. 간단하게 테스트 코드를 작성해보면 다음과 같다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
element *data; // data은 포인터로 정의된다.
int capacity; // 현재 크기
int top;
} StackType;
// 스택 생성 함수
void init_stack(StackType *s)
{
s->top = -1;
s->capacity = 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 == (MAX_STACK_SIZE - 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)--];
}
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));
free(s.data);
return 0;
}실행결과
3
2
1
스택의 응용: 괄호 검사 문제
조건 1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야한다.
조건 2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
조건 3: 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
typedef char element; // 교체!
// 차후에 스택이 필요하면 여기만 복사하여 붙인다.
// ===== 스택 코드의 시작 =====
#define MAX_STACK_SIZE 100
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];
}
// ===== 스택 코드의 끝 =====
int check_matching(const char *in)
{
StackType s;
char ch, open_ch;
int i, n = strlen(in); // n= 문자열의 길이
init_stack(&s); // 스택의 초기화
for (i = 0; i < n; i++) {
ch = in[i]; // ch = 다음 문자
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;
}실행결과
{ A[(i+1)]=0; } 괄호검사성공
스택의 응용: 후위 표기 수식의 계산
수식을 표기하는 방법에는 중위(infix), 후위(postfix), 전위(prefix)의 3가지 방법이 있다.
| 중위 표기법 | 전위 표기법 | 후위 표기법 |
| 2+3*4 | +2*34 | 234*+ |
| a*b+5 | +*ab5 | ab*5+ |
| (1+2)*7 | *+127 | 12+7* |
후위표기식 계산 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
typedef char element; // 교체!
// 차후에 스택이 필요하면 여기만 복사하여 붙인다.
// ===== 스택 코드의 시작 =====
#define MAX_STACK_SIZE 100
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];
}
// ===== 스택 코드의 끝 =====
// 후위 표기 수식 계산 함수
int eval(char exp[])
{
int op1, op2, value, i = 0;
int len = strlen(exp);
char ch;
StackType s;
init_stack(&s);
for (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);
}
int main(void)
{
int result;
printf("후위표기식은 82/3-32*+\n");
result = eval("82/3-32*+");
printf("결과값은 %d\n", result);
return 0;
}실행결과
후위표기식은 82/3-32*+
결과값은 7
중위 표기 수식을 후위 표기 수식으로 변환하는 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
typedef char element; // 교체!
// 차후에 스택이 필요하면 여기만 복사하여 붙인다.
// ===== 스택 코드의 시작 =====
#define MAX_STACK_SIZE 100
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];
}
// ===== 스택 코드의 끝 =====
// 연산자의 우선순위를 반환한다.
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[])
{
int i = 0;
char ch, top_op;
int len = strlen(exp);
StackType s;
init_stack(&s); // 스택 초기화
for (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));
}
//
int main(void)
{
char *s = "(2+3)*4+9";
printf("중위표시수식 %s \n", s);
printf("후위표시수식 ");
infix_to_postfix(s);
printf("\n");
return 0;
}실행결과
중위표시수식 (2+3)*4+9
후위표시수식 23+4*9+
스택의 응용: 미로문제
여기서는 1을 벽으로 e를 입구로 x를 출구로 표시하였다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6
typedef struct { // 교체!
short r;
short c;
} 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];
}
// ===== 스택 코드의 끝 =====
element here = { 1,0 }, 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");
}
}
int main(void)
{
int r, c;
StackType s;
init_stack(&s);
here = entry;
while (maze[here.r][here.c] != 'x') {
r = here.r;
c = here.c;
maze[r][c] = '.';
maze_print(maze);
push_loc(&s, r - 1, c);
push_loc(&s, r + 1, c);
push_loc(&s, r, c - 1);
push_loc(&s, r, c + 1);
if (is_empty(&s)) {
printf("실패\n");
return;
}
else
here = pop(&s);
}
printf("성공\n");
return 0;
}관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 4장 퀴즈와 연습문제 해설을 가져오도록 하겠습니다.
반응형