Tae-Jun :: 스택

스택은 후입선출(LIFO)으로 창고에 쌓여있는 상자를 생각하면 이해가 쉽다. 만약 상자를 바닥에 A, B, C, D순으로 쌓았다면 하나를 꺼내려면 맨 위에 있는 D 상자를 꺼내야 한다. 스택에서 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라고 하고 반대쪽인 바닥부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element)라 부른다. 스택에 요소가 하나도 없는 스택을 공백 스택(empty stack)이라고 한다.

스택 ADT

객체: 0개 이상의 원소를 가지는 유한 선형 리스트
연산:
    create(size) ::= 최대 크기가 size인 공백 스택을 생성한다.
    is_full(s) ::=
        if(스택의 원소수 == size) return TRUE;
        else return FALSE;
    is_empty(s) ::=
        if(스택의 원소수 == 0) return TRUE;
        else return FALSE;
    push(s, item) ::=
        if( is_full(s) ) return ERROR_STACKFULL;
        else 스택의 맨 위에 item을 추가한다.
    pop(s) ::=
        if( is_empty(s) ) return ERROR_STACKEMPTY;
        else 스택의 맨 위의 원소를 제거해서 반환한다.
    peek(s) ::=
        if( is_empty(s) ) return ERROR_STACKEMPTY;
        else 스택의 맨 위의 원소를 제거하지 않고 반환한다.

is_empty, is_full 연산: 스택이 공백상태에 있는지 포화상태에 있는지를 검사하는 함수
create 연산: 스택을 생성
push 연산: 스택의 top에 요소를 삽입한다. 만약 쌓을 공간이 없다면 오류를 발생
pop 연산: 스택의 top의 요소를 삭제한다. 만약 요소가 없다면 오류를 발생
peek 연산: 요소를 스택에서 삭제하지 않고 출력만 하는 연산

구현 방법: 배열

장점: 간단하고 성능이 우수하다.

단점: 스택의 크기가 고정된다.

구현 방법: 연결리스트

장점: 스택의 크기를 필요에 따라 가변적으로 변경할 수 있다.

단점: 구현이 약간 복잡하다.

스택의 구현

1차원 배열을 이용하여 구현

간단하게 int 타입의 정수가 저장되는 것으로 한다.

stack[MAX_STACK_SIZE]: int형의 1차원 배열이 필요

top:스택에서 가장 최근에 입력되었던 자료를 가리키는 변수, 스택이 비어 있으면 -1의 값을 갖는다.

sCtack[0]부터 요소가 쌓이고 가장 최근에 들어온 요소는 stack[top]에 저장된다.

1차원 배열의 is_empty 연산 알고리즘

is_empty(S):
    if top == -1
        then return TRUE
        else return FALSE

1차원 배열의 is_full 연산 알고리즘

is_full(S):
    if top >= (MAX_STACK_SIZE - 1)
        then return TRUE
        else return FALSE

C언어는 제로 인덱스이기 때문에 top이 MAX_STACK_SIZE에서 -1을 뺀 값이면 배열의 끝까지 요소가 채워져 있음을 의미한다.

1차원 배열의 push 연산 알고리즘

push(S, x):
    if is_full(S)
        then error "overflow"
        else top <- top + 1
            stack[top] <- x

is_full 연산을 사용하여 stack이 차 있는지 검사한다. stack이 모두 차 있으면 overflow 에러를 출력한다. top은 마지막으로 삽입되었던 요소의 위치이므로 먼저 top의 값을 증가시키고 top 인덱스에 값을 삽입해야한다.

1차원 배열의 pop 연산 알고리즘

pop(S, x):
    if is_empty(S)
        then error "underflow"
        else e <- stack[top]
            top <- top - 1
            return e

is_empty 연산을 사용하여 stack이 비어있는지 검사한다. stack이 비어있으면 underflow 에러를 출력한다. 스택이 비어 있지 않으면 top이 가리키는 값을 반환한 후 top을 하나 감소시킨다.

1.1 1차원 배열을 이용하여 구현(전역 변수로..)

코드

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100
typedef int 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(void)
{
    push(1);
    push(2);
    push(3);
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", pop());
    return 0;
}

결과

1.2 1차원 배열을 이용하여 구현(스택의 요소를 구조체로..)

스택에 저장되는 요소의 타입은 항상 element라고 가정한다. element의 타입을 필요에 따라 바꾸면 된다.

코드

#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(void)
{
    element ie = { 20190001,
                    "Hong",
                    "Soeul" };
    element oe;

    push(ie);
    oe = pop();

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

결과

1.3 1차원 배열을 이용하여 구현(데이터를 함수의 매개변수로 전달)

앞의 두 가지 방법은 stack 배열과 top이 전역변수로 선언되어 여러 개의 스택을 사용하기 어렵다.

top과 stack 배열을 하나의 구조체로 결합시키고 이 구조체의 포인터를 함수로 전달한다. 이를 StackType이라고 정의하고 필요에 따라 StackType을 사용하여 구조체를 만들면 여러 개의 스택을 사용할 수 있다.

코드

#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));
    return 0;
}

결과

동적 배열을 이용하여 구현

StackType을 다음과 같이 정의한다.

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

스택이 만들어질 때, 1개의 요소를 저장할 수 있는 저장공간을 확보한다.

//스택 생성 함수
void init_stack(StackType *s)
{
    s->top = -1;
    s->capacity = 1;
    s->data = (element *)malloc(s->capacity*sizeof(element));
}

//스택 삭제 함수
void delete(StackType *s)
{
    free(s);
}

push() 연산에서 공간이 부족하면 메모리를 2배로 더 확보한다.

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;
}

코드

#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;
    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];
}

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가지와 같다.

조건 1:왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
조건 2:같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
조건 3:서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다.

스택을 사용하여 다음 문제를 해결할 수 있다. 스택을 사용하여 왼쪽 괄호들을 만나면 계속 삽입한 후 오른쪽 괄호들이 나오면 스택에서 가장 최근의 왼쪽 괄호를 꺼내어 타입을 맞추면 쉽게 괄호들의 오류를 검사할 수 있다.

괄호 검사 알고리즘

check_matching(expr):
    while(입력 expr의 끝이 아니면)
        ch <- expr의 다음 글자
        switch(ch)
            case '(': case '[': case'{':
                ch를 스택에 삽입
                break
            case ')': case ']': case'}':
                if ( 스택이 비어 있으면 )
                    then 오류
                else
                    then 스택에서 open_ch를 꺼낸다.
                    if (ch와 open_ch가 같은 짝이 아니면)
                        then 오류 보고
            break
    if( 스택이 비어 있지 않으면 )
            then 오류

코드

#include <stdio.h>
#include <stdlib.h>zzz

typedef int element;
typedef struct {
    element* 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 == (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];
}

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;
}

결과

스택의 응용: 후위 표기 수식의 계산

수식은 연산자와 피연산자, 괄호로 이루어져 있다. 이 수식을 표기하는 방법에는 중위, 후위, 전위의 3가지 방법이 있다.

중위 표기법	전위 표기법	후위 표기법
2+3*4	+2*34	234*+
a*b+5	+*ab5	ab*5+
(1+2)*7	*+127	12+7*

중위 표기법을 후위 표기법으로 바꾸는 법을 먼저 알아봤다.

위의 (1+2)*7이라는 수식이 있을 때 후위 표기법으로 고칠 때 순서는 다음과 같다.

연산을 진행하는 순서(우선순위)에 맞게 괄호로 묶는다.

((1+2)*7)

연산자를 해당 괄호 바로 오른쪽으로 옮긴다.

((12)+7)*

불필요한 괄호들을 모두 제거한다.

12+7*

이제 후위 표기법을 스택으로 어떻게 연산하는지를 알아보았다.

먼저 스택에 피연산자를 차례대로 넣는다. 그 후 연산자를 만나면 스택에서 피연산자를 꺼내어 나누기 연산을 한다. 만약 연산 시에 스택에 원하는 만큼의 피연산자가 없으면 오류를 발생 시킨다.

알고리즘

calc_posfix:
    스택 s를 생성하고 초기화한다.
    for item in 후위표기식 do
        if (item이 피연산자이면)
            push(s, item)
        else if (item이 연산자 op이면)
            second <- pop(s)
            first <- pop(s)
            result <- first op second
            push(s, result)
    final_result <- pop(s);

코드

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

typedef char element;
typedef struct {
    element* 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 == (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];
}

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("후위표기식은 12+7*\n");
    result = eval("12+7*");
    printf("결과값은 %d\n", result);
    return 0;
}

결과

스택의 응용: 중위표기수식을 후위표기수식으로 변환

다음 규칙을 따라서 중위표기를 후위표기로 변환한다.

왼쪽 괄호는 무조건 스택에 삽입한다.
그 후 만나는 어떤 연산자도 스택에 삽입한다.
오른쪽 괄호를 만나게 되면 왼쪽 괄호가 삭제될 때까지 왼쪽 괄호 위에 쌓여있는 모든 연산자들을 출력한다.
우선 순위가 높은 연산자가 스택에 있고 우선순위가 낮은 연산자가 들어오면 스택에 있는 연산자를 출력하고 우선순위가 낮은 연산자를 스택에 넣는다.
알고리즘

infix_to_postfix(exp):

스택 s를 생성하고 초기화
while (exp에 처리할 문자가 남아 있으면)
    ch <- 다음에 처리할 문자
    switch (ch)
    case 연산자:
        while ( peek(s)의 우선순위 >= ch의 우선순위) do
            e <- pop(s)
            e를 출력
        push(s, ch);
        break;
    case 왼쪽 괄호:
        push(s, ch);
        break;
    case 오른쪽 괄호:
        e <- pop(s);
        while(e != 왼쪽괄호) do
            e를 출력
            e <- pop(s)
        break;
    case 피연산자:
        ch를 출력
        break;
while (not is_empty(s) ) do
    e <- pop(s)
    e를 출력

코드

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

typedef char element;
typedef struct {
    element* 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 == (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];
}
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;
}

결과

'알고리즘 > 개념' 카테고리의 다른 글

순환 (0)	2023.01.13
알고리즘과 자료구조 (0)	2023.01.13

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

스택 ADT

스택의 구현

'알고리즘 > 개념' 카테고리의 다른 글

검색

티스토리툴바