linked_stack.c - Examples

  1// linked_stack.c
  2// 연결 리스트 기반 스택 구현
  3// 동적 메모리 할당으로 크기 제한 없음
  4
  5#include <stdio.h>
  6#include <stdlib.h>
  7#include <stdbool.h>
  8
  9// 노드 구조체
 10typedef struct Node {
 11    int data;
 12    struct Node *next;
 13} Node;
 14
 15// 스택 구조체
 16typedef struct {
 17    Node *top;
 18    int size;
 19} LinkedStack;
 20
 21// 스택 생성
 22LinkedStack* lstack_create(void) {
 23    LinkedStack *s = malloc(sizeof(LinkedStack));
 24    if (s) {
 25        s->top = NULL;
 26        s->size = 0;
 27    }
 28    return s;
 29}
 30
 31// 스택 해제 (모든 메모리 해제)
 32void lstack_destroy(LinkedStack *s) {
 33    Node *current = s->top;
 34    while (current) {
 35        Node *next = current->next;
 36        free(current);
 37        current = next;
 38    }
 39    free(s);
 40}
 41
 42// 비어있는지 확인
 43bool lstack_isEmpty(LinkedStack *s) {
 44    return s->top == NULL;
 45}
 46
 47// Push - 맨 위에 요소 추가 (O(1))
 48bool lstack_push(LinkedStack *s, int value) {
 49    Node *node = malloc(sizeof(Node));
 50    if (!node) {
 51        printf("메모리 할당 실패!\n");
 52        return false;
 53    }
 54
 55    node->data = value;
 56    node->next = s->top;  // 새 노드가 현재 top을 가리킴
 57    s->top = node;        // top을 새 노드로 갱신
 58    s->size++;
 59    return true;
 60}
 61
 62// Pop - 맨 위 요소 제거 후 반환 (O(1))
 63bool lstack_pop(LinkedStack *s, int *value) {
 64    if (lstack_isEmpty(s)) {
 65        printf("Stack Underflow!\n");
 66        return false;
 67    }
 68
 69    Node *node = s->top;
 70    *value = node->data;
 71    s->top = node->next;  // top을 다음 노드로 이동
 72    free(node);           // 제거된 노드 메모리 해제
 73    s->size--;
 74    return true;
 75}
 76
 77// Peek - 맨 위 요소 확인 (제거 안함) (O(1))
 78bool lstack_peek(LinkedStack *s, int *value) {
 79    if (lstack_isEmpty(s)) {
 80        return false;
 81    }
 82    *value = s->top->data;
 83    return true;
 84}
 85
 86// 스택 출력 (top부터 bottom까지)
 87void lstack_print(LinkedStack *s) {
 88    printf("Stack (size=%d): ", s->size);
 89    Node *current = s->top;
 90    while (current) {
 91        printf("%d ", current->data);
 92        current = current->next;
 93    }
 94    printf("(top → bottom)\n");
 95}
 96
 97// 스택 크기 반환
 98int lstack_size(LinkedStack *s) {
 99    return s->size;
100}
101
102// 테스트 코드
103int main(void) {
104    LinkedStack *s = lstack_create();
105    if (!s) {
106        printf("스택 생성 실패!\n");
107        return 1;
108    }
109
110    printf("=== 연결 리스트 기반 스택 테스트 ===\n\n");
111
112    // Push 테스트
113    printf("[ Push 연산 ]\n");
114    for (int i = 1; i <= 5; i++) {
115        printf("Push %d -> ", i * 10);
116        lstack_push(s, i * 10);
117        lstack_print(s);
118    }
119
120    // Peek 테스트
121    printf("\n[ Peek 연산 ]\n");
122    int top;
123    if (lstack_peek(s, &top)) {
124        printf("Top 값: %d (스택은 변경 안됨)\n", top);
125        lstack_print(s);
126    }
127
128    // Pop 테스트
129    printf("\n[ Pop 연산 ]\n");
130    int value;
131    while (lstack_pop(s, &value)) {
132        printf("Popped: %d, ", value);
133        lstack_print(s);
134    }
135
136    // Underflow 테스트
137    printf("\n[ Underflow 테스트 ]\n");
138    printf("빈 스택에서 Pop 시도: ");
139    lstack_pop(s, &value);
140
141    // 대량 삽입 테스트 (동적 할당의 장점)
142    printf("\n[ 대량 삽입 테스트 ]\n");
143    printf("10000개 요소 삽입 중...\n");
144    for (int i = 0; i < 10000; i++) {
145        lstack_push(s, i);
146    }
147    printf("삽입 완료! 현재 크기: %d\n", lstack_size(s));
148
149    // 메모리 정리
150    printf("\n메모리 해제 중...\n");
151    lstack_destroy(s);
152    printf("스택 해제 완료!\n");
153
154    return 0;
155}