스택(Stack) 구현 (C언어) : Part.3 - get_size, reverse, copy 구현

이전 포스팅에서 스택의 기본적인 기능들을 구현했다. 이번 Part3에서는 일종의 심화 기능들을 구현해 보겠다. 사실 이전 포스팅에서 생각보다 많은 기능들을 구현했다. 하지만 간단한 기능들이 다수였다. 반면 이번 기능들은 심화 기능이니 비교적 복잡하다 느낄 수 있다.

---

1. 구현 목표

• get_size : 스택의 크기를 구한다.
• reverse_stack : 스택을 뒤집는다.
• copy_stack : 스택의 값을 복사한다.

---

2. 기능 구현

🔨 get_size

get_size 함수는 스택의 사이즈를 구하는 함수이다. 스택의 사이즈를 구하는 방법은 간단하다 스택의 노드들을 반복문으로 순회하며 순회할 때마다 카운트 변수의 값을 증가시키고 반복이 끝났을 때 반환하면 끝이다.

int get_size(Stack *stack) {
    if (stack == NULL || stack->top == NULL) return 0;

    StackNode *cur = stack->top;
    int count = 0;
    while (cur != NULL) {
        cur = cur->next;
        count++;
    }
    return count;
}

---

🔨 reverse_stack

reverse_stack의 경우 스택의 순서를 뒤집는 것이다. 사실 이 기능은 링크드 리스트 때 구현을 해 봤던 기능이다.

구현 아이디어

1. prev, cur, next 변수를 만들고 각각 NULL, stack->top, NULL 로 초기화한다.
2. cur 값을 이용해 while 반복을 진행하며
3. next가 가리키는 노드를 대신해 cur->next 노드를 지정한다.
4. cur의 next 노드를 prev로 설정한다.
5. prev 노드를 cur 노드로 대체한다.
6. cur 노드를 next 노드로 대체한다.
7. 모든 반복이 끝난 후 stack의 top 값을 prev로 설정한다. 이렇게 하면 prev 값 즉 가장 마지막 노드가 top이 되고 사실상 뒤집힌 결과를 얻을 수 있다.

void reverse_stack(Stack *stack) {
    if (stack == NULL || stack->top == NULL) return;
    StackNode *prev = NULL;
    StackNode *cur = stack->top;
    StackNode *next = NULL;
    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    stack->top = prev;
}

---

🔨 copy_stack

copy_stack은 copy라는 별도의 스택에 기존 스택의 값들을 복사하는 것이다. 이때 우리는 기존에 구현했던 pop과 push를 사용해 두 스택의 값은 값지만 둘이 완전히 같은 것은 아닌 즉 깊은 복사를 구현할 것이다.

구현 아이디어는 다음과 같다.

1. temp라는 임시 스택을 만들고 초기화한다. -> top = NULL 이 된다.
2. cur 노드를 stack의 top 노드로 저장한다.
3. cur 노드를 이용해 while 반복을 진행한다.
4. 반복문 내부에서 push를 이용해 temp라는 임시 스택에 데이터를 저장한다. cur 값을 cur->next로 지정해 반복을 한다.
5. temp라는 임시 스택에 값을 저장하는 것이 끝이 나면 temp 스택이 비어버릴 때까지 반복한다.
6. 반복하면서 copy 스택에 temp의 값들을 pop으로 뽑아낸 뒤 다시 push를 한다. 이렇게 하면 순서까지 같이 만들 수 있다.
7. 반복이 끝나면 temp 스택은 빈 값이 되고 이 스택을 free로 해제한다.
8. copy를 반환한다.

Stack copy_stack(Stack* stack, Stack* copy) {
    if (stack == NULL || stack->top == NULL) return *copy;
    Stack temp;
    init_stack(&temp);

    StackNode *cur = stack->top;
    while (cur) {
        push(&temp, cur->data);
        cur = cur->next;
    }
    while (!is_empty(&temp)) {
        push(copy, pop(&temp));
    }
    free_stack(&temp);
    return *copy;
}

---

3. 기능 검증

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;
}

이 테스트 코드를 실행했을 때 아래와 같은 출력이 나오면 구현에 성공했다고 볼 수 있다.

▶ Running test_push_and_peek...
✅ Passed test_push_and_peek (0.02 ms)

▶ Running test_pop...
✅ Passed test_pop (0.00 ms)

▶ Running test_pop_on_empty_stack...
stack empty
✅ Passed test_pop_on_empty_stack (0.00 ms)

▶ Running test_get_size...
✅ Passed test_get_size (0.00 ms)

▶ Running test_reverse_stack...
✅ Passed test_reverse_stack (0.00 ms)

▶ Running test_copy_stack...
✅ Passed test_copy_stack (0.00 ms)

========================================
Tests run: 6
Tests passed: 6
Tests failed: 0
✅ ALL TESTS PASSED