[자료구조] C로 Stack 만들기

Stack?

스택은 문자 그대로 데이터를 쌓는 형식으로 저장하고 가져오는 자료구조 입니다. LIFO(Last In First Out) 방식으로, 가장 마지막으로 들어온 데이터가 가장 먼저 나가는 형태입니다.

동작 원리

스택은 내부적으로 배열이나 연결리스트를 이용해서 데이터를 저장합니다. 여기서는 배열을 이용해서 구현하는 방법을 설명하겠습니다. 0번 idx부터 순차적으로 데이터를 추가하고, 데이터가 추가된 가장 마지막 idx를 기록하는 방식으로 동작합니다. 자세한 동작 원리는 코드와 함꼐 설명드리겠습니다.

구조체 선언

typedef struct {
    int items[MAX_SIZE]; // 데이터를 저장 할 배열
    int top; // 가장 뒤에 있는 데이터 = 가장 마지막에 추가된 데이터
} Stack;

Stack initStack() {
    Stack stack;
    // top을 -1로 초기화
    stack.top = -1;
    return stack;
}

스택을 구성하는 구조체입니다. 데이터를 저장 할 배열 array, 가장 마지막에 추가된 데이터 위치를 표현하는 top으로 구성되어 있습니다. 스택에 데이터가 없을때는 top을 -1로 초기화합니다.

데이터 push

void push(Stack *stack, int value) {
    // 이미 최대 사이즈 만큼 데이터를 저장하고 있으면 함수 종료
    if (stack->top + 1 == MAX_SIZE) return;
    // top + 1 위치에 데이터 추가
    stack->items[++stack->top] = value;
}

스택에서 push 함수는 데이터를 새로 추가하는 함수입니다. 내부적으로 배열에 데이터가 저장된 마지막 idx의 + 1 위치에 새 데이터를 넣습니다.

데이터 pop

int pop(Stack *stack) {
    // 꺼넬 데이터가 없다면 -1 리턴
    if (isEmpty(stack)) return -1;
    // 현재 top 위치의 데이터를 리턴하고 top - 1
    return stack->items[stack->top--];
}

스택에서 pop 함수는 데이터를 꺼내오는 함수입니다. 배열의 top 데이터를 가져오고, top을 -1 하여 추후 push시 값을 덮어씁니다.

데이터 peak

int peak(Stack *stack) {
    // 스택에 데이터가 없다면 -1 리턴
    if (isEmpty(stack)) return -1;
    // top 데이터 리턴
    return stack->items[stack->top];
}

스택에서 peak 함수는 가장 최근에 추가된 데이터를 확인하는 함수입니다. 배열의 top 데이터를 가져와서 리턴합니다.

전체 코드

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

Stack initStack() {
    Stack stack;
    stack.top = -1;
    return stack;
}

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int peak(Stack *stack) {
    if (isEmpty(stack)) return -1;
    return stack->items[stack->top];
}

void push(Stack *stack, int value) {
    if (stack->top + 1 == MAX_SIZE) return;
    stack->items[++stack->top] = value;
}

int pop(Stack *stack) {
    if (isEmpty(stack)) return -1;
    return stack->items[stack->top--];
}

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

int main() {
    Stack stack = initStack();

    char command[10];
    int number;

    printf("Commands: push <num>, pop, peak, exit\n");
    while (1) {
        printf("> ");
        scanf("%s", command);

        if (strcmp(command, "push") == 0) {
            scanf("%d", &number);
            push(&stack, number);
            printStack(&stack);
        } else if (strcmp(command, "pop") == 0) {
            printf("%d\n", pop(&stack));
            printStack(&stack);
        } else if (strcmp(command, "peak") == 0) {
            printf("%d\n", peak(&stack));
        } else if (strcmp(command, "exit") == 0) {
            break;
        } else {
            printf("Invalid command.\n");
        }
    }

    return 0;
}