[자료구조 기초] 스택의 개념과 구조, 구현

SMALL

데이터를 저장하기 위한 자료구조의 형태로는 여러가지가 존재하는데 그 중 대표적인 스택과 큐중 스택에 대해서

알아보자.

스택이란?

먼저 스택의 대표적인 특징은 데이터의 입력과 출력 순서가 후입선출(LIFO, Last In First Out)이라는 특징을 지닌다,

말 그래도 나중에 넣은 데이터가 가장 먼저 나온다는 뜻인데, 그림처럼 데이터를 밑에서부터 쌓고 꺼내는 순서는

역으로 위에서 부터 꺼낸다고 생각하면 된다.

스택의 구조와 구현

이제 스택의 형태와 그 개념에 대해 이해를 해봤으니 다음으로는 스택의 구조와 구현과정에 대해서 알아보도록 하자.

먼저 스택을 구조체를 통해서 구현을 할때 ~~필수적~~으로 넣어야 하는 요소에 대해 설명해보겠다.

- 사실 구현을 할때 data[max], top 두가지 요소만 있어도 충분히 스택이라 할수 있다, 다만 다른 요소들도 설명해보고자

몇가지 요소를 더 추가했다.

#include <stdio.h>
#define max 100

typedef struct Stack{
    int max; 스택의 최대 용량
    int top; 스택의 현재 데이터 개수
    int data[max]; 스택의 데이터가 있는 배열요소
}Stack;

스택의 요소 설명

먼저 Stack의 최대 용량을 뜻하는 max이다.

- 이 요소는 Stack에서 최대 몇개의 데이터를 입력받을수 있는지 설정하는 값으로 필자의 경우 define을 통해 max값을 100으로 규정했다.

다음으로 Stack의 현재 데이터 개수 값인 top이다.

-Stack에서도 가장 필수적인 요소인데 Stack에서의 데이터 개수를 알려줄 뿐만 아니라(+1을 하면 데이터의 개수를 알수 있다), push, pop을 하는 경우 이 top값을 이용해서 데이터를 추가,제거한다.

마지막으로 Stack의 데이터를 보관하는 장소인 data[max]이다, 사실 배열을 직접 동적배열로 할당을 할수도 있지만 필자의 경우 직관적으로 이해할수 있도록 max용량을 가진 배열로 만들었다.

이렇게 스택을 만들때 사용하는 요소들을 알아보았는데 다음으로는 구체적인 스택의 함수들을 알아보도록 하겠다.

void _init_(Stack *s)
{
    s->top = -1;
}

이 코드의 경우 필수적으로 Stack을 생성시 불러와야 하는 코드이다.

:__init__ 생성코드:

스택의 요소 중 top값을 -1로 변경하였는데, 위에서 필자는 top+1 값을 Stack 내부의 데이터 개수라고 했다,

즉, -1로 변경한 이유는 배열의 인덱스 때문인데 배열의 인덱스가 0인경우 data[0]을 가르킬수 있다,

하지만 top값을 -1로 저장한다면 data[top]을 통해서 Stack 내부 데이터를 효율적으로 판별해낼수 있다.

top값이 -1인 이유

✅ 배열의 인덱스와 일관성을 유지하고
✅ 스택이 비었는지 쉽게 확인할 수 있으며
✅ 크기 계산을 직관적으로 할 수 있기 때문입니다.

int push(Stack *s, int a)
{
    if (s->top == max - 1)
    {
        return -1; // 스택이 가득 참
    }
    else
    {
        s->top += 1;
        s->data[s->top] = a;
        return 0;
    }
}

다음으로는 Stack에 입력값인 a를 넣어주는 함수인 push 함수이다.

이 함수는 굉장히 직관적으로 이해할 수 있는 코드인데, 먼저 top값을 통해서 스택의 내부 데이터값이 가득차 있는지를 확인한다.

s->top == max-1

이후에는 top값을 +1 해주어 데이터 개수를 증가시켜주고 s->data[s->top]을 이용해서 Stack에 a값을 추가시켜준다.

int pop(Stack *s)
{
    if (s->top == -1)
    {
        return -1; // 스택이 비어 있음
    }
    else
    {
        int temp = s->data[s->top];
        s->top -= 1;
        return temp;
    }
}

다음으로는 push와 짝을 이루며 Stack 함수의 기본중의 기본인 pop함수이다.

이 함수도 push와 마찬가지로 top값을 이용해서 스택이 비어있는지를 확인한 후 작동한다.

else 이후 부분을 보면

temp라는 변수를 만들어 return 시키는 것을 볼 수 있다. 이 과정에서 중요한 부분이 data[] 배열을 건드는 것이 아니라

단순히 top값을 -1 시킴으로써 값을 무력화시키는 과정이다.

Stack 함수의 모든 ADT는 top값을 이용한다, 따라서 Stack 내부데이터를 건드리지 않고도 top값을 -1 함으로써 pop함수를 구현해낼 수 있다.

s->top-=1;

#include <stdio.h>
#define max 100

typedef struct Stack {
    int top;         // 스택의 현재 데이터 개수
    int data[max];   // 스택의 데이터 배열
} Stack;

void _init_(Stack *s)
{
    s->top = -1;
}

int push(Stack *s, int a)
{
    if (s->top == max - 1)
    {
        return -1; // 스택이 가득 참
    }
    else
    {
        s->top += 1;
        s->data[s->top] = a;
        return 0;
    }
}

int pop(Stack *s)
{
    if (s->top == -1)
    {
        return -1; // 스택이 비어 있음
    }
    else
    {
        int temp = s->data[s->top];
        s->top -= 1;
        return temp;
    }
}

void clear(Stack *s)
{
    s->top = -1;
}

int peek(Stack *s, int *x)
{
    if (s->top == -1)
    {
        return -1; // 스택이 비어 있음
    }
    else
    {
        *x = s->data[s->top];
        return 0;
    }
}

int cnt(Stack *s)
{
    return s->top + 1; // 현재 데이터 개수 반환
}

int main()
{
    Stack s;
    _init_(&s);
    
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    
    int x;
    if (peek(&s, &x) == 0)
        printf("Top element: %d\n", x);
    
    printf("Stack size: %d\n", cnt(&s));
    
    printf("Popped: %d\n", pop(&s));
    printf("Stack size after pop: %d\n", cnt(&s));
    
    return 0;
}