스택(Stack)이란?

스택(Stack)이란?

▶ 쌓아놓은 더미

아래 사진처럼 물건을 쌓아놓은 형태를 구현하는 것이다.

스택의 형태

 

스택의 특징

▶ 후입선출(LIFO: Last-In First-Out): 가장 최근에(늦게) 들어온 데이터가 가장 먼저 나감.

 

스택의 구조

스택의 구조

 

위와 같이 상자가 3개 쌓였을 때, 상자 하나 하나가 요소(element)에 해당하고, 맨 밑에 있는 상자를 스택 하단(bottom),

맨 위에 있는 상자를 스택 상단(top)이라고 한다.

 

스택 추상 데이터 타입(ADT)

스택 ADT

 

스택의 연산

▶ push(): 스택에 데이터를 추가

▶ pop(): 스택에서 데이터를 삭제

▶ is_empty(s): 스택이 공백상태인지 검사

▶ is_full(s): 스택이 포화상태인지 검사

▶ create(): 스택을 생성

스택 연산 과정

 

스택의 용도

▶ 입력과 역순의 출력이 필요한 경우

 

예를 들어, 에디터에서 되돌리기(undo) 기능과 함수호출에서 복귀주소를 기억할 때 스택을 사용한다.

함수 호출-복귀에서 스택의 사용

 

그럼, 배열을 이용해서 스택을 구현해보자.

 

1차원 배열 stack[]

▶ top: 스택에서 가장 최근에 입력되었던 자료를 가리키는 top 변수

▶ stack[0]: 가장 먼저 들어온 요소

▶ stack[top]: 가장 최근에 들어온 요소

▶ 스택이 공백상태이면 top은 -1

1차원 배열 스택

 

▶ is_empty, is_full 연산의 구현

is_empty, is_full 연산 알고리즘

 

▶ push 연산

push 연산 알고리즘

 

▶ pop 연산

pop 연산 알고리즘

 

이제 C언어로 스택을 구현해보자.

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

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

// 스택 초기화 함수
void init(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, "Error: stack is full \n");
        return;
    }
    else {
        s->stack[++(s->top)] = item;
    }
}

// 삭제 함수
element pop(StackType *s) {
    if( is_empty(s) ) {
        fprintf(stderr, "Error:stack is empty \n");
        exit(1);
    }
    else {
        return s->stack[(s->top)--];
    }
}

int main() {
    StackType stack;
    init(&stack);

    // 스택에 데이터 넣기
    printf("스택에 데이터 넣기: ");
    for (int i = 1; i <= 5; i++) {
        push(&stack, i);
        printf("%d ", i);
    }
    printf("\n");

    // 스택에서 데이터 꺼내기
    printf("스택에서 데이터 꺼내기: ");
    while (!is_empty(&stack)) {
        printf("%d ", pop(&stack));
    }
    printf("\n");

    return 0;
}

 

왜 int가 아닌 element 타입으로 선언하였나?

-> 추후 데이터가 int가 아닌 double인 경우, 손쉽게 변경이 가능하다.

배열의 요소는 element타입으로 선언하고, 관련 데이터를 구조체로 묶어서 함수의 파라미터로 전달한다.

stack을 pointer로 전달하는 이유는?

-> stack을 복사해서 전달할 경우, stack의 크기가 크면 복사되는 데이터의 양이 너무 많아 비효율적임.

 

스택의 응용 1: 괄호검사

 

괄호의 종류: 대괄호 ('[', ']'), 중괄호 ('{', '}'), 소괄호 ('(', ')')

 

조건:

1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.

2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.

3. 서로 다른 괄호들은 교차하면 안된다.

 

잘못된 괄호 사용의 예

▶ (a(b)

▶ a(b)c)

▶ a{b(c[d]e}f)

 

스택을 이용한 괄호 검사

스택을 이용한 괄호 검사

 

괄호검사 알고리즘

▶ 알고리즘의 개요

문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면

스택에서 top 괄호를 삭제한 후, 오른쪽 괄호와 짝이 맞는지를 검사한다.

이 때, 스택이 비어 있으면 조건 1 또는 조건 2 등을 위배하게 되고, 괄호의 짝이 맞지 않으면 조건 3 등에 위배된다.

마지막 괄호까지를 조사한 후에도 스택에 괄호가 남아 있으면, 조건 1에 위배되므로 0(거짓)을 반환하고,

그렇지 않으면 1(참)을 반환한다.

괄호 검사 알고리즘

 

C언어로 구현

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

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

// 스택 초기화 함수
void init(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, "Error: stack is full \n");
        return;
    }
    else {
        s->stack[++(s->top)] = item;
    }
}

// 삭제 함수
element pop(StackType *s) {
    if( is_empty(s) ) {
        fprintf(stderr, "Error:stack is empty \n");
        exit(1);
    }
    else {
        return s->stack[(s->top)--];
    }
}

int check_matching(char *in) {
    StackType s;
    char ch, open_ch;
    int i, n = strlen(in);

    init(&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() {
    if( check_matching("{ A[(i+1)]=0; }") == 1)
        printf("괄호검사 성공\n");
    else
        printf("괄호검사 실패\n");
}

 

 

스택의 응용 2: 수식의 계산

 

수식의 표기방법은 전위(prefix), 중위(infix), 후위(postfix) 표기법이 있다.

중위 표기법	전위 표기법	후위 표기법
2 + 3 * 4	+ 2 * 3 4	2 3 4 * +
a * b + 5	+ 5 * a b	a b * 5 +
(1 + 2) + 7	+ 7 + 1 2	1 2 + 7 +

 

후위 표기법은 컴파일러에서 주로 사용하며, 괄호가 없어도 우선순위를 반영한다.

 

컴퓨터에서의 수식 계산순서

▶ 중위 표기식 -> 후위 표기식 -> 계산

▶ 2 + 3 * 4 -> 2 3 4 * + -> 1 4

▶ 모두 스택을 사용한다

 

중위 표기식을 후위 표기식으로 변환

▶ 중위 표기와 후위 표기

중위 표기법과 후위 표기법의 공통점은 피연산자의 순서는 동일

연산자들의 순서만 다름(우선순위순서) -> 연산자만 스택에 저장했다가 출력하면 된다.

예) 2 + 3 * 4 -> 2 3 4 * +

 

▶ 알고리즘

피연산자를 만나면 그대로 출력

연산자를 만나면 스택에 저장했다가 스택의 top에 저장된 연산자보다 우선 순위가 낮은 연산자가 나오면 그 때 출력.

왼쪽 괄호는 무조건 스택에 저장.

스택 안에서 왼쪽 괄호는 우선 순위가 가장 낮은 연산자로 취급

오른쪽 괄호가 나오면 스택에서 왼쪽 괄호위에 쌓여 있는 모든 연산자를 출력.

중위 표기식 -> 후위 표기식 변환 알고리즘

 

C언어로 구현

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

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

// 스택 초기화 함수
void init(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, "Error: stack is full \n");
        return;
    }
    else {
        s->stack[++(s->top)] = item;
    }
}

// 삭제 함수
element pop(StackType *s) {
    if( is_empty(s) ) {
        fprintf(stderr, "Error:stack is empty \n");
        exit(1);
    }
    else {
        return s->stack[(s->top)--];
    }
}

// 중위 표기 수식 -> 후위 표기 수식
void infix_to_postfix(char exp[]) {
    int i = 0;
    char ch, top_op;
    int len = strlen(exp);
    StackType s;

    init(&s); // 스택 초기화
    for(i = 0 ; i < len ; i++) {
        ch = exp[i];

        switch(ch) {
            case '+': case '-': case '*': case '/':     // 연산자
                // 스택에 있는 연산자의 우선 순위가 더 크거나 같으면 출력
                while( !is_empty(&s) && (prec(ch) <= prec(s.stack[s.top])) )  // prec: 우선 순위 함수
                    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 prec(char op) {
    switch(op) {
        case '(': case ')': return 0;
        case '+': case '-': return 1;
        case '*': case '/': return 2;
    }
    return -1;
}

int main() {
    infix_to_postfix("(2+3)*4+9");

    return 0;
}

 

그렇다면 후위 표기식의 계산은 어떻게 할까?

 

▶ 수식을 왼쪽에서 오른쪽으로 스캔하여 피연산자이면 스택에 저장하고, 연산자이면 필요한 수만큼 피연산자를 스택에서 꺼내 연산을 실행하고 연산의 결과를 다시 스택에 저장

▶ (예) 82 / 3 - 32 * +

후위 표기식의 계산

 

계산 과정은 다음과 같다.

 

후위 표기식 계산 알고리즘

후위 표기식 계산 알고리즘

 

C언어로 구현

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

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

// 스택 초기화 함수
void init(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, "Error: stack is full \n");
        return;
    }
    else {
        s->stack[++(s->top)] = item;
    }
}


// 삭제 함수
element pop(StackType *s) {
    if( is_empty(s) ) {
        fprintf(stderr, "Error:stack is empty \n");
        exit(1);
    }
    else {
        return s->stack[(s->top)--];
    }
}

// 후위 표기 수식 계산 함수
int eval(char exp[]) {
    int op1, op2, value, i = 0;
    int len = strlen(exp);
    char ch;
    StackType s;

    init(&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 '/':
                    if (op2 == 0) {
                        fprintf(stderr, "Error: divide by zero\n");
                        exit(1);
                    }
                    push(&s, op1 / op2);
                    break;
            }
        }
    }
    return pop(&s);
}

int main() {
    char exp[] = "52+3*+";
    int result = eval(exp);
    printf("후위 표기식 \"%s\"의 결과는 %d입니다.\n", exp, result);
    return 0;
}

 

 

 

다음에 계속...