[자료구조] 스택 자료구조의 구현

스택은 가장 많이 들어보았을 자료구조 중 하나이다. 간단한 자료구조임에도 불구하고 이를 응용하는 곳은 많다. 스택의 응용에 대해서는 다른 포스트에서 정리하도록 하겠다.

1. 스택이란?

스택의 형태를 이해하기 위해서는 프링글스 통을 생각하면 편하다. 우리는 프링글스 통에서 과자를 빼어먹을 때 가장 맨 위에 있는 과자를 빼어먹으며, 과자를 넣을 때도 맨 위에 과자를 넣게 된다. 가장 늦게 들어온 것이 가장 첫번째로 나가는 형태이므로 이런 입출력 형태를 LIFO(Last-In First-Out)이라고 한다.

스택의 형태를 그림으로 나타낸 것이다. 스택에 있는 1, 2, 3을 스택의 요소라고 부르며, 가장 위에 있는 요소는 스택의 상단(top)이라 부른다.
또한, 스택에 요소가 하나도 들어있지 않을 때는 공백(empty) 상태라 하고 꽉 차서 더 이상 요소를 집어넣지 못하 경우 포화(full) 상태라고 한다.

다음과 같이 스택의 top 요소를 빼오는 연산을 pop, 스택에 top에 새로운 요소를 추가하는 연산을 push라고 한다. pop의 경우 스택이 공백(empty) 상태인지 확인해야 하며, push의 경우 스택이 포화(full) 상태인지 확인해야 한다.

2. 소스 코드 구현

구현하는데 사용한 언어는 C이다.

#include <stdbool.h>

#ifndef _STACK_
#define _STACK_

typedef struct stack {
        int* element;
        int size;
        int top;
} stack;
typedef stack* Stack;

Stack createStack(int n);
bool isFull(Stack stack);
void push(Stack stack, int elem);
bool isEmpty(Stack stack);
int pop(Stack stack);
int peek(Stack stack);
void printStack(Stack stack);

#endif

stack.h

Stack createStack(int n) {
    Stack stack = (Stack)malloc(sizeof(Stack));
    stack->element = (int*)malloc(sizeof(int) * n);
    stack->size = n;
    stack->top = -1;

    return stack;
}

bool isFull(Stack stack) {
    if (stack->top == stack->size - 1)
        return true;
    else
        return false;
}

void push(Stack stack, int elem) {
    if (!isFull(stack)) {
        stack->top++;
        stack->element[stack->top] = elem;
    }
}

bool isEmpty(Stack stack) {
    if (stack->top == -1)
        return true;
    else
        return false;
}

int pop(Stack stack) {
    if (!isEmpty(stack)) {
        return stack->element[stack->top--];
    }
}

int peek(Stack stack) {
    if (!isEmpty(stack)) {
        return stack->element[stack->top];
    }
}

void printStack(Stack stack) {
    for (int i = 0; i < stack->top + 1; i++) {
        printf("%d ", stack->element[i]);
    }
    printf("\n");
}

stack.c

위는 스택을 배열을 이용해 구현한 형태로 stack의 pop, push 연산 전에 각각 공백(empty) 상태, 포화(full) 상태를 체크하는 것을 볼 수 있다.
pop 연산 시 top 요소를 리턴하며 top을 1 줄이고, push 연산 시 stack의 위에 요소를 하나 추가하며 top을 1 증가시킨다.

#include <stdio.h>
#include "stack.h"

int main() {
    Stack stack = createStack(10);
    
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    printStack(stack);

    pop(stack);
    printStack(stack);

    return 0;
}

main.c

간단한 테스트를 할 수 있는 main 함수이다.

3. 참조

천인국, 최영규, 「C++로 쉽게 풀어쓴 자료구조」, 생능출판사, 2019년