[자료구조] 스택(Stack)의 개념과 구현(C) & 용도

Donghwa Kim·2022년 11월 30일

자료구조

자료구조 (data structure)

목록 보기

4/5

스택이란?

스택 (stack)

자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 중 하나
가장 먼저 자료구조에 삽입(push)된 데이터가 제일 마지막에 삭제(pop)됨
이를 4자로 줄여서 선입후출(First In Last Out) 혹은 후입선출(Last In First Out) 이라 함
또한 스택은 언제나 제일 위에 있는 자료만 접근 가능하다. 중간 자료에 임의 접근 안됨

스택의 구현

배열로 쉽게 구현 가능
그냥 배열의 앞에서부터 차례대로 데이터를 추가
마지막 요소의 위치를 스택의 제일 위 (top)라 생각하면 됨

스택의 삽입 (push)

보통 push라고 표현
- 제일 위에 밀어 넣어 쌓는다고 해서
시간복잡도는 O(1)이다

enum { MAX_NUMS = 5 };

int s_nums[MAX_NUMS];
size_t s_num_count = 0;

void push(int n)
{
    assert(s_num_count < MAX_NUMS);
    s_nums[s_num_count++] = n;
}

int main(void)
{
    push(11);
    push(22);
    push(33);
    push(44); 
    push(55); // s_nums = [11, 22, 33, 44, 55], s_num_count = 5
    push(66); /* Assertion failed */
}

스택의 제거 (pop)

스택에서 뽑아 낸다고 해서 POP이라고 함
시간 복잡도: O(1)

enum { TRUE = 1, FALSE = 0 };
enum { MAX_NUMS = 5 };

int s_nums[MAX_NUMS]; /* 11 22 33 44 55 */
size_t s_num_count = 0; /* s_num_count = 5 */

int is_empty(void)
{
    return (s_num_count == 0);
}

int pop(void)
{
    assert(is_empty() == FALSE);
    return s_nums[--s_num_count];
}

int num;

num = pop(); /* s_nums: { 11, 22, 33, 44 }, s_num_count: 4*/
num = pop(); /* s_nums: { 11, 22, 33 }, s_num_count: 3 */

위 코드에서 처음 num = pop() 했을 때 s_nums[4]에 55란 값이 남아있지만 이는 쓰레기 값
두 번째 num = pop()을 했을 때도 마찬가지

스택의 검색

시간복잡도는 O(N)
제일 위에서 찾을 때가지 뒤져야 함
보통 push()와 pop()만 허용하므로 임의의 요소에 접근할 방법이 없음
그래서 찾을 때 까지 모든 요소를 다 제거했다가 다시 원상복구해야 함
제거에 O(N) + 복구에 O(N) = O(2N) 이지만, 빅오 표기법에서 상수는 무시되므로 그냥O(N)이라고 함

스택의 용도

스택의 용도1: 자료순서 뒤집기

일련의 자료들의 순서를 뒤집는데 유용하다.
스택의 요소들을 하나씩 뽑아서 배열에 저장
- 이렇게 하면 배열의 요소가 뒤집어진다.

#include <string.h>
#include <stdio.h>
#include <assert.h>

enum { FALSE = 0, TRUE = 1 };
enum { MAX_SIZE = 5 };

int s_nums[MAX_SIZE] = { 1, 2, 3, 4, 5 };
int s_tmp_nums[MAX_SIZE];
size_t s_num_count = 0;

int is_empty(void)
{
    return s_num_count == 0;
} 

void push(int n)
{
    assert(s_num_count < MAX_SIZE);
    s_tmp_nums[s_num_count++] = n; 
}

int pop(void)
{
    assert(is_empty() == FALSE);
    return s_tmp_nums[--s_num_count]; 
}


int main(void)
{
    size_t i;

    for (i = 0; i < MAX_SIZE; ++i) {
        push(s_nums[i]); // s_tmp_nums = { 1, 2, 3, 4, 5 }
    }

    for (i = 0; i < MAX_SIZE; ++i) {
        s_nums[i] = pop();
    }

    for (i = 0; i < MAX_SIZE; ++i) {
        printf("s_nums[%d]: %d\n", i, s_nums[i]);
    }

    return 0;
}

스택의 용도2: 컴퓨터 연산 순서에 맞게 자료 재정리

다음과 같은 식(문자열로 들어 옴)을 평가하는 계산기를 만든다면?
- 2 * (4 + 5) - 15 / 3
위와 같은 표기법을 연산자가 중간에 있다고 해서 중위(infix) 표기법이라고 함
사람들에게는 매우 익숙하나, 컴퓨터가 순서대로 한 글자씩 읽으며 평가 불가능
이걸 후위 (postfix) 표기법으로 바꾸면 컴퓨터로 연산이 쉬움
- 2 4 5 + *15 3 / -
- 이렇게 중위 -> 후위로 바꾸는 것도 스택으로 구현 가능
후위 표기법으로 적힌 식은 간단하게 스택을 이용해서 계산 가능