[C언어로 쉽게 풀어쓴 자료구조] Chapter 4 - 스택(Stack)

스택(stack) : 쌓아놓은 더미
특징 - 후입선출(Last-In First-Out)
스택에 저장되는 것 : 요소(element)

스택을 구현하는 방법
1. 배열을 이용하는 방법 - 장점 : 구현이 쉬움 / 단점 : 스택의 크기가 고정
2. 연결 리스트를 이용하는 방법 - 장점 : 구현이 약간 복잡 / 단점 : 스택의 크기가 가변적

 

// 정수 배열 스택 프로그램

// 정수 배열의 스택 프로그램
#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100 // 스택 크기 고정
typedef int element; // 요소의 자료형 : 정수형
element stack[MAX_STACK_SIZE]; // 1차원 배열
int top = -1; // 가장 위에 있는 스택의 인덱스 / 스택이 비어있음을 의미

// 공백 상태 검출 함수
int is_empty()
{
    // 'top==-1'이 True : 공백상태
    return (top==-1);
}

// 포화 상태 검출 함수
int is_full()
{
    return (top==(MAX_STACK_SIZE -1));
}

// 삽입 함수
void push(element item)
{
    // 포화 상태일 경우 오류
    if (is_full()){
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    // top에 +1을 하고 그 자리에 item을 추가
    else stack[++top] = item;
}
/*
fprintf(stderr,"에러 메시지");
stderr : 표준 에러 출력 장치

일반 함수속의 return : return값 반환 후 해당 함수 종료
main 함수속의 return : return값 반환 후 프로그램 전체 종료
*/


// 삭제 함수
element pop()
{
    // 공백 상태일 경우 오류
    if (is_empty()){
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    // top위치에 있는 요소를 반환하고, top을 -1.
    else return stack[top--];
}
/*
exit()함수 : stdlib.h에서 인클루드 해서 사용.
현재 작성된 프로세스내 파일 입출력중인 것을 저장함과 동시에 프로세스 종료
exit(0) : 정상 종료
exit(1) : '에러 메시지' 종료
*/


// 스택내의 최상위 요소 출력
element peek()
{
    if (is_empty()){
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return stack[top];
}

int main()
{
    push(1);
    push(2);
    push(3);
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", pop());
    return 0;
}

/* 출력값
2
1
0
*/

 

 

// 구조체 배열 스택 프로그램

// 구조체 배열 스택 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100

// 구조체 정의
typedef struct {
    int student_no;
    char name[MAX_STRING];
    char address[MAX_STRING];
} element;

// 구조체를 요소로 하는 스택 선언
element stack[MAX_STACK_SIZE];
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];
}

int main()
{
    element ie = {20185468,
                "KIM",
                "BUSAN"};
    element oe; // 스택에서 반환될 요소를 저장할 곳

    push(ie); // 요소 삽입
    oe=pop(); // 스택에서 요소를 삭제 , 반환 되는 값을 oe에 저장

    printf("학번 : %d\n", oe.student_no);
    printf("이름 : %s\n", oe.name);
    printf("주소 : %s\n", oe.address);
    return 0;
}

/* 출력값
학번 : 20185468
이름 : KIM
주소 : BUSAN
*/

 

 

 

// 일반적인 배열 스택 프로그램 (다음에 나올 프로그램들의 기초가 됨)

// 일반적인 스택 배열 프로그램
#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
    element data[MAX_STACK_SIZE];
    int top;
}StackType;

// 스택 초기화 함수 (스택을 초기화 할때, 스택 안에 무엇이 있던지 top을 -1로 바꾸어 주면 초기화가 됨)
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()
{
    StackType s;

    init_stack(&s); // 구조체 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
*/

 

 

// 동적 배열 스택 프로그램

// 필요한 스택의 크기를 미리 알고 적용하는 것은 매우 어렵다.
// 그렇기에 동적 메모리 할당을 이용한다.

// 동적 배열 스택 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
    element *data;
    int capacity; // 현재 스택 크기
    int top;
}StackType;

void init_stack(StackType *s)
{
    s->top = -1;
    s->capacity = 1; // 스택 크기 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)){ // 스택이 full이라면,
        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()
{
    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); // 동적 메모리 반환
}

/*출력값
3
2
1
*/

 

 

// 괄호 검사 프로그램

// 괄호 검사 프로그램 (스택)
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef char 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 check_matching(const char *in)
{
    StackType s;
    char ch, open_ch; // ch : 현재 검사중 인 문자 / open_ch : 왼쪽 괄호 담당
    int i, n =strlen(in); // n = 문자열 길이
    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()
{
    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; } 괄호검사성공
*/

 

 

// 후위표기식 계산

// 후위표기식 계산
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef char 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 eval(char exp[])
{
    // op1,op2 : 피연산자 , value : 숫자
    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()
{
    int result;
    printf("후위 표기식 : 86-9*4+2- \n");
    result = eval("86-9*4+2-");
    printf("결과값은 %d\n", result);
    return 0;
}

/*출력값
후위 표기식 : 82/3-32*+
결과값은 7
*/

/* 다른 예제
중위 표기식 : 4+(8-6)*9-2
후위 표기식 : 86-9*4+2-

입력값 : 86-9*4+2-
출력값
후위 표기식 : 86-9*4+2-
결과값은 20
*/

 

 

// 중위 표기 수식을 후위 표기 수식으로 변환하는 프로그램

// 중위 표기식 -> 후위 표기식 변환
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef char 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 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; // ch : 현재 검사중인 문자
    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()
{
    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+
*/

 

 

// 미로 탐색 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6

typedef struct {
    // 정수형 자료형 short : 2byte
    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)];
}
/* ************************************* */

// 현재 위치 : here , 시작 위치 : entry
element here = {1,0} , entry = {1,0};

// 미로맵 만들기 / e : 시작점 , 1 : 벽 , 0 : 길 , x : 출구
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()
{
    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] = '.';
        printf("\(%d,%d\)\n",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);
    }
    maze_print(maze); // 완성된 경로 출력
    printf("성공\n");
    return 0;
}

/*출력값
(1,0)
(1,1)
(2,1)
(2,2)
(2,3)
(3,3)
(4,3)
(4,4)

111111
..1001
1...11
101.11
101..x
111111
성공
*/