스택 (Stack)
들어가는 말
지금까지 리스트를 구현하는 여러 방법을 살펴보았다.
리스트는 앞, 중간, 뒤 등 원하는 위치에 데이터를 넣거나 뺄 수 있는 자료구조다.
인덱스를 이용하면 특정 위치의 값에 바로 접근할 수도 있다.
반면 스택은 한쪽 끝에서만 데이터를 넣고 꺼낸다.
영어 단어 stack은 물건을 차곡차곡 쌓아 올린 더미를 뜻한다.
차곡차곡 쌓은 접시를 떠올려 보자.
접시는 맨 위에만 쌓을 수 있고, 꺼낼 때도 맨 위 접시부터 꺼낸다.
이처럼 가장 나중에 넣은 데이터가 가장 먼저 나오는 규칙을 LIFO(Last In, First Out)라고 한다.
처음 스택을 보면 왜 이렇게 제한적인 구조를 사용하는지 의문이 들고, 리스트보다 덜 유용해 보일 수 있다.
하지만 스택은 자유로운 접근을 제한하는 대신, 가장 마지막에 넣은 데이터를 먼저 꺼낸다는 순서를 분명하게 보장한다.
스택을 구현하는 일은 어렵지 않다.
더 중요한 것은 문제 속에서 최근에 처리한 데이터를 먼저 다시 다뤄야 하는 흐름을 알아차리는 일이다.
그 흐름을 발견하면 복잡해 보이던 문제도 스택으로 간결하게 풀어낼 수 있다.
스택이 실제 문제를 푸는 데 쓰이는 과정이 궁금하다면, 수식 계산기 구현에서 수식의 표기법을 변환하고 계산하는 과정을 확인할 수 있다.
스택은 데이터를 어떻게 저장할지보다 어떤 동작을 제공할지를 먼저 정하는 추상 자료형(Abstract Data Type, ADT)이다.
따라서 리스트를 배열이나 연결 리스트로 구현할 수 있듯이, 스택도 여러 방식으로 구현할 수 있다.
먼저 배열 기반 스택과 연결 리스트 기반 스택의 코드를 차례로 살펴보겠다.
소스 코드
아래 코드는 학습용 코드로, 핵심 동작에 집중하기 위해 메모리 할당이 성공하고 각 함수가 올바른 순서로 호출된다고 가정한다.
main.c
#include <stdio.h>
#include "array_stack.h"
//#include "linked_list_stack.h"
int main(void)
{
Stack stack;
Data value;
stack_init(&stack);
stack_push(&stack, 1);
stack_push(&stack, 2);
stack_push(&stack, 3);
stack_push(&stack, 4);
stack_push(&stack, 5);
stack_peek(&stack, &value);
printf("peek: %d\n\n", value);
while (!stack_is_empty(&stack))
{
stack_pop(&stack, &value);
printf("pop: %d\n", value);
}
printf("\n");
if (!stack_peek(&stack, &value))
printf("peek: stack is empty\n");
return 0;
}배열 기반 스택
array_stack.h
#ifndef ARRAY_STACK_H
#define ARRAY_STACK_H
#include <stdbool.h>
typedef int Data;
#define STACK_CAPACITY 128
typedef struct Stack
{
int top;
Data values[STACK_CAPACITY];
} Stack;
bool stack_init(Stack* stack);
bool stack_push(Stack* stack, Data value);
bool stack_pop(Stack* stack, Data* out_value);
bool stack_peek(const Stack* stack, Data* out_value);
bool stack_is_empty(const Stack* stack);
#endif // ARRAY_STACK_Harray_stack.c
#include <stdlib.h>
#include "array_stack.h"
bool stack_init(Stack* stack)
{
if (stack == NULL)
return false;
stack->top = -1;
return true;
}
bool stack_push(Stack* stack, Data value)
{
if (stack == NULL || stack->top + 1 >= STACK_CAPACITY)
return false;
stack->values[++stack->top] = value;
return true;
}
bool stack_pop(Stack* stack, Data* out_value)
{
if (stack == NULL || out_value == NULL || stack_is_empty(stack))
return false;
*out_value = stack->values[stack->top--];
return true;
}
bool stack_peek(const Stack* stack, Data* out_value)
{
if (stack == NULL || out_value == NULL || stack_is_empty(stack))
return false;
*out_value = stack->values[stack->top];
return true;
}
bool stack_is_empty(const Stack* stack)
{
return stack->top == -1;
}연결 리스트 기반 스택
linked_list_stack.h
#ifndef LINKED_LIST_STACK_H
#define LINKED_LIST_STACK_H
#include <stdbool.h>
typedef int Data;
typedef struct Node
{
Data value;
struct Node* next;
} Node;
typedef struct Stack
{
Node* head;
} Stack;
bool stack_init(Stack* stack);
bool stack_push(Stack* stack, Data value);
bool stack_pop(Stack* stack, Data* out_value);
bool stack_peek(const Stack* stack, Data* out_value);
bool stack_is_empty(const Stack* stack);
#endif // LINKED_LIST_STACK_Hlinked_list_stack.c
#include <stdlib.h>
#include "linked_list_stack.h"
bool stack_init(Stack* stack)
{
if (stack == NULL)
return false;
stack->head = NULL;
return true;
}
bool stack_push(Stack* stack, Data value)
{
if (stack == NULL)
return false;
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->value = value;
new_node->next = stack->head;
stack->head = new_node;
return true;
}
bool stack_pop(Stack* stack, Data* out_value)
{
if (stack == NULL || out_value == NULL || stack_is_empty(stack))
return false;
Node* del_node = stack->head;
*out_value = del_node->value;
stack->head = del_node->next;
free(del_node);
return true;
}
bool stack_peek(const Stack* stack, Data* out_value)
{
if (stack == NULL || out_value == NULL || stack->head == NULL)
return false;
*out_value = stack->head->value;
return true;
}
bool stack_is_empty(const Stack* stack)
{
if (stack->head == NULL)
return true;
return false;
}시간 복잡도
접근
스택은 배열과 연결 리스트 중 어떤 방식으로 구현하더라도 가장 최신 값을 O(1)에 확인할 수 있다.
하지만 그 아래의 값을 확인하려면 위에 쌓인 값을 pop으로 하나씩 꺼내야 하므로 최악의 경우 O(n)이 걸린다.
삽입
배열 기반 스택은 top이 가리키는 위치에 값을 저장하면 삽입이 끝난다.
연결 리스트 기반 스택은 새 노드의 next가 기존 head를 가리키도록 한 뒤, head를 새 노드로 변경하면 된다.
두 구현 방식 모두 삽입에 O(1)이 걸린다.
삭제
배열 기반 스택에서의 삭제는 top 인덱스를 하나 줄여 해당 값을 더 이상 스택의 원소로 취급하지 않으면 삭제가 완료된다.
인덱스만 줄이고 기존 값은 그대로 두어도 되는지 의문이 들 수 있다.
하지만 스택은 함수를 통해서만 조작하며, 이후 push하면 해당 위치의 값은 자연스럽게 덮어써지므로 문제가 없다.
연결 리스트 기반 스택에서는 다음과 같이 삭제가 이루어진다.
먼저 head가 가리키는 노드를 지역 변수 del_node에 보관한다.
그다음 head가 del_node의 next를 가리키도록 변경한다.
마지막으로 del_node를 해제하면 삭제가 완료된다.
두 구현 방식 모두 삭제에 O(1)이 걸린다.