Overview

스택은 선입후출(혹은 후입선출, FILO, LIFO 다양하게 부른다.)식 자료구조이다.

쉽게 말해 먼저 들어간 놈이 제일 마지막에 나온다.

 

무언가를 차곡 차곡 쌓았을때,

제일 첫번째로 꺼내들 수 있는 것은 제일 마지막에 쌓아둔 것이다.

이름 그대로 무언가를 쌓아놓는 자료구조가 되겠다.


스택이 기본적으로 가져야 하는 세가지 동작은 push, pop, peek이다.

push는 집어넣는거, pop은 빼는거, peek은 단어 뜻 그대로 top에 뭐가 있는지 슬쩍 훔쳐보는거다.

 

top은 가장 마지막으로 들어온 요소의 위치를 의미하며, 보통 빈 스택에서는 -1이라는 값을 가진다.

Implementation

C로 간단하게 구현해보았다. C++이나 JAVA, 파이썬 등으로 구현하면 더 편리하게 구현할 수 있을 것이다.

원래 malloc-free 할때는 NULL 체크를 열심히 해주는게 맞긴 한데 여기서는 너무 빡빡하게 한게 아닌가 싶다.

#include <stdbool.h>
#include <malloc.h>

typedef struct {
    int   top;      // 현재 위치
    int   capacity; // 스택 최대 크기
    int*  arr;      // 스택의 내용을 저장할 배열
} stack;

stack* stack_new(int capacity) {
    stack* new_stack = (stack*) malloc( sizeof(stack) );
    
    // 정말 재수 없으면 여기부터 할당이 실패할 수 있다.
    if (new_stack == NULL) {
        return NULL;       // 그때는 NULL을 리턴해주자.
    }
    
    new_stack->top = -1; // 빈 스택의 top 값은 -1이다.
    new_stack->capacity = capacity;
    new_stack->arr = (int*) malloc( capacity * sizeof(int) );
    
    // 내부 배열 할당이 실패했다면 - malloc은 할당 실패시 NULL 리턴
    if (new_stack->arr == NULL) {
        free(new_stack);       // 기껏 만들어놓은 스택 내던지고
        return NULL;           // NULL 리턴
    }
    
    return new_stack;
}

void   stack_delete(stack* self) {
    if (self != NULL) {
        free(self->arr);  // 따로 malloc 된거니까 따로 free 해준다.
                          // stack_new에서 NULL 체크 하니까 이상한 짓만 안하면 따로 체크할 필요 없다.
        free(self);
    }
}

bool   stack_full(stack* self) {
    return self->top == self->capacity - 1;
}

bool   stack_empty(stack* self) {
    return self->top == -1;
}

// push
void   stack_push(stack* self, int element) {
    if (stack_full(self)) { // 스택이 꽉 찼을까?
        return;             // 그렇다면 무시
    }
    
    self->top++;                     // top 1 증가
    self->arr[self->top] = element;  // top 위치에 새 요소 삽입
}

// peek: top에 있는 값을 한번 살펴보자.
int   stack_peek(stack* self) {
    if (stack_empty(self)) { // 스택이 비었을까?
        return -1;           // 뭔가 에러가 될 만한 값을 리턴하자.
    }

    return self->arr[self->top];
}

// pop
int   stack_pop(stack* self) {
    if (stack_empty(self)) { // 스택이 비었을까?
        return -1;           // 뭔가 에러가 될 만한 값을 리턴하자.
    }
    
    int data = stack_peek(self);     // top 위치에 있는 값 가져오기
    self->top--;                     // top 1 감소
    
    return data;
}

Application

이렇게나 간단한 자료구조이지만, 쓸모는 굉장히 많은게 또 이 스택이다.

 

대표적으로 컴퓨터 시스템에서 함수 콜스택(이름부터 스택이 들어갔다)의 구현이 이 스택으로 이루어지며,

컴파일러나 인터프리터에서 토큰이나 괄호 검사 등을 할 때도 스택이 들어간다. 

게임쪽으로 넘어가보자면 미로찾기할 때도 스택이 쓰인다. (갔다가 막히면 되돌아 와야 하니까)

 

결론적으로 뭔가 되돌아 갈 필요가 있는 작업에는 대개 스택을 사용한다고 보면 되겠다.