크래프톤 정글

스택(Stack) 구현 (C언어) : Part.1 - 초기 환경 설정 & 구현할 함수 소개

고웅 2025. 4. 16. 17:33

 이번에는 C언어를 이용해 스택을 직접 구현해보려고 한다. 링크드 리스트를 직접 구현했던 내용도 있으니 링크드 리스트에 대해서 부족하지만 정리했던 내용을 확인하려면 이 전 포스팅 했던 글을 확인하는 것도 좋을 것 같다.

1. 스택 구현 전 준비

이전 링크드 리스트와 같이 미리 테스트 코드를 준비해 두었다. 그리고 구현해야 하는 함수와 구조체를 정의해 두었다.

더보기 
#include <stdio.h>
#include <stdlib.h>
#include "minunit.h"

// ---[구현할 기능 정의]--- //
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

typedef struct Stack {
    StackNode* top;
} Stack;


// 스택 초기화
void init_stack(Stack* stack);
// 값 추가
void push(Stack* stack, int data);
// 가장 위 값 제거 및 반환
int pop(Stack* stack);
// 가장 위 값 확인
int peek(Stack* stack);
// 스택이 비어 있는지 확인
int is_empty(Stack* stack);
// 스택 전체 메모리 해제
void free_stack(Stack* stack);
int get_size(Stack* stack);
void reverse_stack(Stack* stack);
Stack copy_stack(Stack* stack, Stack* copy);
// --- [링크드 리스트 구현] --- //

// --- [메인 & 테스트 코드] --- //

/*
static char * test_push_and_peek() {
    Stack s;
    init_stack(&s);
    push(&s, 10);
    mu_assert("peek after 1 push", peek(&s) == 10);
    push(&s, 20);
    mu_assert("peek after 2 pushes", peek(&s) == 20);
    free_stack(&s);
    return 0;
}
static char * test_pop() {
    Stack s;
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    mu_assert("pop 1", pop(&s) == 3);
    mu_assert("pop 2", pop(&s) == 2);
    mu_assert("pop 3", pop(&s) == 1);
    mu_assert("stack should be empty", is_empty(&s) == 1);
    free_stack(&s);
    return 0;
}

static char * test_pop_on_empty_stack() {
    Stack s;
    init_stack(&s);
    int result = pop(&s);  // 구현 시 비정상 값 반환 (예: -1) 또는 assert
    mu_assert("pop on empty stack should return -1", result == -1);
    free_stack(&s);
    return 0;
}


static char * test_get_size() {
    Stack s;
    init_stack(&s);
    mu_assert("initial size != 0", get_size(&s) == 0);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    mu_assert("size after 3 pushes", get_size(&s) == 3);
    pop(&s);
    mu_assert("size after pop", get_size(&s) == 2);
    free_stack(&s);
    return 0;
}


static char * test_reverse_stack() {
    Stack s;
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);  // top = 3
    reverse_stack(&s);   // top = 1
    mu_assert("top after reverse", peek(&s) == 1);
    pop(&s);
    mu_assert("2nd after reverse", peek(&s) == 2);
    pop(&s);
    mu_assert("3rd after reverse", peek(&s) == 3);
    pop(&s);
    mu_assert("stack should now be empty", is_empty(&s) == 1);
    free_stack(&s);
    return 0;
}


static char * test_copy_stack() {
    Stack src, dest;
    init_stack(&src);
    init_stack(&dest);
    push(&src, 10);
    push(&src, 20);
    push(&src, 30);  // top = 30
    copy_stack(&src, &dest);
    mu_assert("src top", peek(&src) == 30);
    mu_assert("dest top", peek(&dest) == 30);
    pop(&dest);
    mu_assert("dest second", peek(&dest) == 20);
    pop(&dest);
    mu_assert("dest third", peek(&dest) == 10);
    free_stack(&src);
    free_stack(&dest);
    return 0;
}
*/

static char * all_tests() {
    // mu_run_test(test_push_and_peek);
    // mu_run_test(test_pop);
    // mu_run_test(test_pop_on_empty_stack);
    // mu_run_test(test_get_size);
    // mu_run_test(test_reverse_stack);
    // mu_run_test(test_copy_stack);
    
    if (tests_failed > 0) {
        return "Some tests failed.";
    }

    return 0;
}
int tests_run = 0;
int tests_failed = 0;

int main(void) {
    char *result = all_tests();

    printf("========================================\n");
    printf("Tests run: %d\n", tests_run);
    printf("Tests passed: %d\n", tests_run - tests_failed);
    printf("Tests failed: %d\n", tests_failed);

    if (result != 0) {
        printf("❌ TESTS FAILED\n");
        return 1;
    }
    printf("✅ ALL TESTS PASSED\n");
    return 0;
}

자세한 코드는 위의 더 보기를 클릭하여 확인하면 된다.

2. 구현할 함수 설명

// ---[구현할 기능 정의]--- //
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

typedef struct Stack {
    StackNode* top;
} Stack;


// 스택 초기화
void init_stack(Stack* stack);
// 값 추가
void push(Stack* stack, int data);
// 가장 위 값 제거 및 반환
int pop(Stack* stack);
// 가장 위 값 확인
int peek(Stack* stack);
// 스택이 비어 있는지 확인
int is_empty(Stack* stack);
// 스택 전체 메모리 해제
void free_stack(Stack* stack);
int get_size(Stack* stack);
void reverse_stack(Stack* stack);
Stack copy_stack(Stack* stack, Stack* copy);

미리 준비해 둔 구조체를 보자 Stack이라는 스택 구조체가 top이라는 포인터를 가지고 있다. 스택은 LIFO (Last In First Out) 구조를 가지고 있는데 나중에 들어온 데이터가 먼저 나가는 구조다 그래서 어떤 데이터가 가장 Top 인지 알 수 있게 top을 가지고 있다.

구현 함수 목록

init_stack  스택 초기화
push 스택에 데이터를 넣는다.
pop 스택에서 top 값을 뽑는다(제거)
peek 스택에서 top의 값을 확인
Is_empty 스택이 비어 있는지 확인
free_stack 스택 전체 메모리 해제
get_size 스택 전체 사이즈 확인
reverse_stack 스택 뒤집기
copy_stack 스택 복사

위와 같은 함수를 이제 스택 시리즈에서 구현해 보도록 하겠다. 다음 포스팅에서는 스택을 생성, 초기화, pop, free_stack 코드를 구현해 보도록 하겠다.

저작자표시 동일조건