[CDS] chapter 4 : 스택

1. 스택 기본

스택(stack)이란, 이름에서 알 수 있듯이 데이터를 차곡차곡 쌓아올린 형태의 자료구조이다. 스택은 선형자료구조로 데이터가 연속적으로 연결되어 있는 모양이기에 일종의 리스트라고 할 수 있다. 그러나 스택은 데이터의 삽입 및 삭제가 한쪽 끝(스택의 top이라고 한다)에서만 이루어진다는 점에서 리스트와 차별된다.

스택은 구조상 데이터가 입력순서대로 쌓여있기 때문에 스택에서 빼올 수 있는 데이터는 가장 위에 있는 마지막에 넣어준 데이터이다. 즉, 후입선출(LIFO, Last-In-First-Out) 구조이다.

 

스택은 다음과 같은 분야에서 활용될 수 있다.

• 웹 브라우저의 뒤로가기 기능
• 수식 계산 - 후위 표기법
• 문서 편집기에서 되돌리기 기능
• 함수 호출 - 복귀할 주소를 기억하는데 사용
• DFS 알고리즘

2. 스택의 구현

(1) 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 스택의 맨 위의 원소를 제거하지 않고 반환

(2) 스택 구현

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

typedef struct {
    int size;
    int* stack;
    int top;
} Stack;

Stack* create(int size){
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->size = size;
    s->stack = (int*)malloc(size * sizeof(int));
    s->top = 0;
    printf("\n########## Stack with size %d has been created. ##########\n", size);
    return s;
}

int is_full(Stack* s){
    return s->top == s->size;
}

int is_empty(Stack* s){
    return s->top == 0;
}

void push(Stack* s, int item){
    if (is_full(s) == 1) {
        printf("\n########## the stack is full!!! ##########\n");
    }
    else {
        s->top += 1;
        s->stack[s->top] = item;
        printf("\n########## %d is pushed. ##########\n", item);
    }
}

int pop(Stack* s){
    if (is_empty(s) == 1) {
        printf("\n########## the stack is empty!!! ##########\n");
    }
    else {
        printf("\n########## %d is popped. ##########\n", s->stack[s->top]);
        return s->top--;
    }
}

int peek(Stack* s){
    if (is_empty(s) == 1) {
        printf("\n########## the stack is empty!!! #########\n");
    }
    else {
        printf("\n########## %d is peeked. ##########\n", s->stack[s->top]);
        return s->top;
    }
}

int main(){
    int size;
    printf("Please enter the desired stack size : ");
    scanf("%d", &size);
    Stack* myStack = create(size);

    while (1){
        int order;
        printf("----------------------------------\n");
        printf("Enter the action number to perform\n");
        printf("\n");
        printf("1 Verify that the stack is full\n");
        printf("2 Verify that the stack is empty\n");
        printf("3 Insert an element into the stack\n");
        printf("4 Delete an element in a stack\n");
        printf("5 Check the elements in the stack\n");
        printf("0 Exit\n");
        printf("Your input : ");
        scanf("%d", &order);

        if (order == 0) {
            free(myStack->stack);
            free(myStack);
            break;
        }
        else{
            switch (order){
            case 1:
                if (is_full(myStack)){
                    printf("\n########## the stack is full. ##########\n");
                }
                else{
                    printf("\n########## the stack is NOT full. ##########\n");
                }
                break;
            case 2:
                if (is_empty(myStack) == 1) {
                    printf("\n########## the stack is empty. ##########\n");
                }
                else {
                    printf("\n########## the stack is NOT empty. ##########\n");
                }
                break;
            case 3:
                if (is_full(myStack)){
                    printf("\n########## the stack is full. ##########\n");
                }
                else{
                    int item;
                    printf("\nEnter a number to insert in the stack : ");
                    scanf("%d", &item);
                    push(myStack, item);
                    }
                break;
            case 4:
                pop(myStack);
                break;
            case 5:
                peek(myStack);
                break;
            default:
                printf("\nwrong input!!\n");
                break;
            }
        }
    }
    return 0;
}

(3) 구현 후기

• 스택의 구현은 top이라는 변수를 통해 스택의 끝단을 가리킨다는 아이디어가 포인트인 것 같다.
• 하나의 프로그램에서 여러 개의 스택을 동시에 사용하기 위해서 구조체 타입을 활용할 수 있다는 것을 알게 되었다.
• 이번 프로그래밍은 하나의 C파일에 작성하였으나, 다음부터는 헤더파일과 분리하여 작성하려고 한다.