2021.2.9 TIL : [자료구조] 스택(Stack)

오늘은 스택에 대해서 배웠는데, 지난 CS50 강의에서 메모리 구조를 배우면서 알게 된 힙과 스택에서의 스택과는 조금 다른 뜻인 것 같았다.

스택은 한 쪽으로 들어가서 한 쪽으로 나오는 자료구조를 의미한다. 이는 들어가는 곳과 나오는 곳이 같다는 특징이 있는데, LIFO(Last-In-First-Out) 방식을 떠올리면 쉽게 이해할 수 있다. 이러한 특성 때문에 스택은 수식 계산 등의 다양한 알고리즘에서 다방면으로 활용된다.

 

스택에서 Push는 스택에 새 데이터를 추가하는 것, Pop은 가장 최근에 추가한 데이터를 빼내는 것을 의미한다. 

 

예를 들어 

push(7) - push(3) - push (5) - pop() - push (11) - pop() - push (12)이 스택의 자료구조로 이루어져 있다면, 이 자료는 top부터 12 - 3 - 7로 이어지는 값을 갖는다.

 

스택은 배열을 이용한 구현 방법과 포인터를 사용해 연결리스트로 만드는 구현 방법으로 나누어 진다. 이는 가장 기본적인 형태의 자료구조로 양방향 연결리스트보다 쉽게 구현할 수 있다. (라고 이론 상으로는 나와 있었으나, 초보자의 개인적으로는 양방향 연결리스트가 좀 더 쉽게 떠올릴 수 있었던 것 같다.)

 

다음은 배열을 이용해 스택을 구현하는 코드이다. 

#include <stdio.h>
#define SIZE 10000
#define INF 99999999

int stack[SIZE];
int top = -1;

void push(int data){
    if(top == SIZE - 1){
        printf("스택 오버플로우\n");
        return;
    }
    stack[++top] = data;
}

int pop(void){
    if(top == -1){
        printf("스택 언더플로우\n");
        return -INF;
    }
    return stack[top--];
}

void show(void){
    printf("----스택의 최상단----\n");
    for(int k = top; k >= 0; k--){
        printf("%i\n", stack[k]);
    }
    
    printf("----스택의 최하단----\n");
}

int main(void){
    push(5);
    push(7);
    push(8);
    push(2);
    pop();
    push(6);
    pop();
    show();

    return 0;
}

이 코드에서 새로 배웠던 점은 stack[++top]과 stack[top--] 기능이다. 배열은 연결리스트에 비해 무난하게 스택 구현을 할 수 있었다. 하지만, pop 함수에서 return stack[pop--] 에서는 조금 이해가 부족한 부분이 생긴 것 같다. 현재 top이 가리키고 있는 그 원소의 값을 반환하면서 원소가 줄었음을 알려주기 위해 top에서 1을 감소시키기 위해서임은 알겠지만, return을 했을 때 해당 원소가 삭제된다는 점에서 의아했던 것 같다. 사실, 원소가 삭제된다는 점에서 확신이 안 들어 디버깅을 해보고 나서야 확신하게 됐다.  이 부분은 return을 더 자주 사용하면서 이렇게 사용될 수 있는지를 알아봐야 할 것 같다. 구글링을 통해서는 쉽게 답을 찾을 수 없었다. 

 

배열을 통한 스택 구현은 메모리 사용 측면에서 비효율적이다. 초반에 설정한 것과 같이 int STACK[SIZE]를 통해서 스택의 크기만큼 배열을 만들어 줘야 하기 때문이다. 따라서 메모리 사용 측면에서는 필요한 만큼만 메모리를 할당해 주는 연결리스트가 효율적이다.

 

다음은 연결리스트로 구현한 스택이다.

#include <stdio.h>
#include <stdlib.h>
#define INF 99999999

typedef struct Node{
    int data;
    struct Node *next;
}Node;

typedef struct{
    Node *top;
}Stack;

void push(Stack *stack,int data){
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}

int pop(Stack *stack){
    if(stack->top == NULL){
        printf("스택 언더플로우/n");
        return -INF;
    }
    Node *node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}

void show(Stack *stack){
    Node *cur = stack->top;
    printf("----스택의 최상단----\n");
    while(cur != NULL){
        printf("%i\n", cur->data);
        cur = cur->next;
    }
    printf("\n----스택의 최하단----\n");
}

int main(void){
    Stack stack;
    stack.top = NULL;
    push(&stack, 3);
    push(&stack, 5);
    pop(&stack);
    push(&stack, 8);
    push(&stack, 7);
    push(&stack, 9);
    push(&stack, 12);
    pop(&stack);
    show(&stack);

    system("pause");
    return 0;

}

아무래도 연결리스트는 수업을 듣고 실제로 구현해보면서 멈칫 하는 부분들이 많았다. 여기서 push는 추가하려고 하는 새로운 노드를 만들고, 새로운 노드에 top을 연결하고, 새로운 노드를 top으로 정하여 리스트의 가장 앞에 데이터를 추가했다. pop은 일시적인 새로운 노드를 top으로 만들고, 새로운 노드의 next로 top을 변동시킨 후, 새로운 노드를 없애 리스트의 가장 앞 원소를 없앴다. 연결리스트로 구현하게 되면 main 함수 내에서 top을 NULL로 초기화 해줘야 한다. 단일 연결리스트와 비슷한 이유와 방법이었다. 

 

이렇게 스택에 대한 가장 기초적인 이해를 마무리했다. 컴퓨터 과학에서 스택은 활용도가 높아 잘 알고 있어야 한다는데, 설명도 많이 듣고, 많이 구현해봐야 익숙해 질 것 같다.