[자료구조] stack 구조에 대해 알아보자

오늘은 자료 구조 중 stack 구조에 대해 알아봐요.

오늘 포스팅의 목표는 여러분이 이 포스팅의 썸네일을 이해하는 거에요!

---

사실 크게 어려울 건 없어요. 왜냐하면, stack 구조는 우리가 일상에서 너무 많이 접하는 구조이기 때문이죠.

옷을 넣는 수납함이 있다고 생각해보세요. 그 수납함에 옷을 차곡차곡 쌓아서 넣어놨는데 맨 아래에 있는 옷을 꺼내야한다고 가정해볼게요.

꺼내야 하는 옷 위에 다른 옷들을 건드리지 않고 꺼내야 하는 옷을 꺼낼 수 있을까요?

맞아요. 불가능하죠? 맨 아래 옷은 위 옷들을 전부 꺼낸 후에야 꺼낼 수 있어요.

이게 바로 stack 구조에요. 참 쉽죠?

이러한 구조를 우리는 LIFO(Last In First Out)구조라고 해요. 마지막에 들어간 게 처음으로 나온다. 여기까지만 이해하시면 이론은 끝입니다.

stack 구조라는 건 입구가 하나뿐인 바구니에 우리가 원하는 물건을 넣고 위에서부터 차례대로 빼는 거라고 생각하시면 편해요.

대부분의 언어들에서는 이미 stack, queue 등이 모두 최적화된 상태로 바로 사용할 수 있게 제공되기 때문에 C언어로 구현해볼게요.

사실 자료 구조 자체를 제대로 이해하고 구현할 수 있으면 언어는 크게 문제가 없어요. (문제 없다는 건 성능을 말하는 게 아니고 언어에 구애받지 않는 실력을 말하는 거에요.)

위에서 stack 구조를 이해해봤으니 이제 구현해봐요.

2-1. 필요한 변수

이해는 했는데 그럼 구현은 어떻게 해야될까요?

먼저 필요한 변수들을 정의해야해요.

구조체 형태로 Stack을 만들어봤는데요.

top

현재 스텍이 얼마나 차있는지를 의미하는 변수에요.

초기값을 -1로 두고 array에 값이 채워질 때마다 +1 해줘서 배열의 가장 마지막에 들어온 아이템을 가리키는 인덱스 역할을 해줄 거에요.

array

스텍을 쌓을 공간이에요. 위의 설명을 빌리자면 옷을 넣을 수납함인 거죠.

1#define ARRAY_SIZE 6
2
3typedef struct STACK {
4    int top;
5    char array[ARRAY_SIZE];
6} Stack;

2-2. 필요한 함수

항상 반복적으로 사용하는 코드들은 어떻게 해야한다? 함수화 시켜야한다~!

함수화 시켜두면 변경사항이 생길 때 한 부분만 고치면 해당 함수를 사용하는 모든 코드 부분에 적용되기 때문에 유지보수가 쉬워지고 실수가 적어지니까 꼭! 함수화 시키는 연습을 해주세요.

int isEmpty(Stack stack)

stack이 비어있는지 여부를 확인해주는 함수에요.

top 변수의 초기값을 -1로 둔다고 했으니 -1인지만 확인하면 되겠죠?

(c언어에는 boolean 값이 없어서 참이면 1 거짓이면 0으로 반환되요.)

int size(Stack stack)

stack에 몇 개의 아이템이 들어있는지 확인해주는 함수에요.

top 변수가 마지막에 들어온 아이템을 가리키는 인덱스 역할을 한다고 했으니 +1을 해주면 아이템 개수를 쉽게 알 수 있어요.

char getTop(Stack stack)

stack에 마지막으로 들어온 아이템을 반환하는 함수에요.

void push(Stack *stack, char item)

stack에 아이템을 넣어주는 함수에요.

top index를 하나씩 늘려가면서 array 배열에 차례대로 채워넣어요.

(c언어의 함수는 기본적으로 call by value 방식으로 작동하기 때문에 stack 내부의 변수들을 수정하려면 포인터를 사용해줘야해요.)

char pop(Stack *stack)

stack의 마지막 아이템을 빼주는 함수에요.

top index를 줄여가면서 array 배열에서 차례때로 빼주세요.

1#define STACK_FULL_MSG "stack is already full\n"
2#define STACK_PUSH_MSG "push %c into stack\n"
3#define STACK_EMPTY_MSG "stack is empty now\n"
4
5int isEmpty(Stack stack)
6{
7    return stack.top == -1;
8}
9
10int size(Stack stack)
11{
12    return stack.top + 1;
13}
14
15char getTop(Stack stack)
16{
17    if (isEmpty(stack))
18    {
19        printf(STACK_EMPTY_MSG);
20        return '#';
21    }
22    return stack.array[stack.top];
23}
24
25void push(Stack *stack, char item)
26{
27    if (size(*stack) == ARRAY_SIZE - 1)
28    {
29        printf(STACK_FULL_MSG);
30        return;
31    }
32    stack->array[++stack->top] = item;
33    printf(STACK_PUSH_MSG, item);
34}
35
36char pop(Stack *stack)
37{
38    if (isEmpty(*stack))
39    {
40        printf(STACK_EMPTY_MSG);
41        return '#';
42    }
43    char item = stack->array[stack->top];
44    stack->array[stack->top--] = '\0';
45    return item;
46}

2-3. 메인 함수

stack 변수의 top과 array 변수를 각각 -1, 로 초기화해서 k, c, a, t, s를 순서대로 push하고 마지막에 모두 pop하면 어떤 단어가 나올까요?

바로 stack이에요.

이제 썸네일의 의미를 아시겠나요? 누워있는 스텍 배열에 k, c, a, t, s 아이템이 순서대로 push한 형태인거죠.

순서대로 pop하면 오늘 코딩결과와 똑같이 stack이에요.

1int main()
2{
3    Stack stack =
4        {
5            -1,
6            {"\0"}};
7
8    push(&stack, 'k');
9    push(&stack, 'c');
10    push(&stack, 'a');
11    push(&stack, 't');
12    push(&stack, 's');
13
14    while (!isEmpty(stack))
15    {
16        printf("%c", pop(&stack));
17    }
18
19    return 0;
20}

그래 다 좋다! 좋은데! 그래서 언제 쓰는데? 별로 쓸모 없을 것 같은데... 라고 생각하신다면 천만의 말씀!

생각보다 우리 주변에서 많이 쓰이는 데이터 구조에요.

3-1. 웹 브라우저 뒤로가기

크롬, 네이버 웨일, 엣지, 사파리 등 많은 브라우저에서 공통적으로 지원하는 기능인 뒤로가기 버튼도 stack을 이용한 거에요.

여러분이 보고 있는 페이지도 스텍으로 쌓여있는 거죠.

3-2. ctrl+z, cmd+z

윈도우의 경우에는 ctrl+z, 맥의 경우에는 cmd+z 문서 작업이나 코딩 막 하다가 뒤로 돌릴 때 쓰는 단축키!

이것도 여러분의 동작들을 stack 형식으로 push해두었다가 pop하는 형식이에요.

정말 신기하죠?

---

https://github.com/classic-95/data-structures/tree/main/stack

---

오늘은 stack 구조에 대해 이해하고 구현하기, 실제 사용 사례들에 대해 알아봤어요.

생각보다 어렵지 않죠? 뭐든지 이해하고 나면 구현해보는 습관을 들이시는 걸 추천드려요.

구현하면서 머리를 쓸 수록 그 구조가 더 머리에 깊게 남고 다른 곳에 이용할 수 있는 계기가 될 거에요.

포스팅 읽으면서 따라오시느라 고생하셨어요!