[C언어]42일차 - 스택 - 배열로 구현해보기 (이것이 C언어 자료구조 알고리즘이다.)

 

[C언어]42일차 - 스택 - 배열로 구현해보기

 

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

#define ElementType int

typedef struct _Node{
    ElementType Data;
} Node;

typedef struct _Stack{
    int capacity;       //용량
    int top;            //최상위 노드의 위치
    Node *nodes;        //노드 배열 (힙에할당된 첫번째 요소를 가리킨다.)
}Stack;


void createStack(Stack** stack, int capacity);
void destroyStack(Stack* stack);
void push(Stack* stack , ElementType Data);
ElementType pop(Stack* stack);
ElementType top(Stack* stack);
int getSize(Stack* stack);
int isEmpty(Stack* stack);
int isFull(Stack* stack);
void printStacks(Stack* stack);

//MARK: 스택생성
void createStack(Stack** stack, int capacity){
    
    //스택의 힙 공간 생성 후 할당
    (*stack) = (Stack*)malloc(sizeof(Stack));
    
    if ((*stack) == NULL) {
        printf("스택 생성에 실패했습니다.\n");
        return;
    }
    (*stack)->nodes = (Node*)malloc(sizeof(Node) * capacity);
    
    if ((*stack)->nodes == NULL) {
        printf("스택 배열 생성에 실패했습니다.\n");
        return;
    }
    
    (*stack)->top = -1;
    (*stack)->capacity = capacity;
}

//MARK: 사이즈
int getSize(Stack* stack){
    return stack->top + 1;
}

//MARK: 비었는지 체크
// -1: 비었음, 0이상: 안비었음
int isEmpty(Stack* stack){
    return stack->top;
}

//MARK: 가득찼는지 체크
//1: 가득참, 0:가득안참
int isFull(Stack* stack){
    return stack->capacity == (stack->top + 1);
}

//MARK: push
void push(Stack* stack , ElementType Data){

    if (isFull(stack)) {
        printf("스택 배열이 가득찼습니다.\n");
        return;
    }
    
    stack->top += 1;
    stack->nodes[stack->top].Data = Data;
}

//MARK: pop
ElementType pop(Stack* stack){
    if (isEmpty(stack) == -1) {
        printf("스택 배열이 비었습니다.\n");
        return -1;
    }
    
    stack->top -= 1;
    return stack->nodes[stack->top].Data;
}


//MARK: top
ElementType top(Stack* stack){
    if (isEmpty(stack) == -1) {
        printf("스택 배열이 비었습니다.\n");
        return -1;
    }
    return stack->nodes[stack->top].Data;
}


//MARK: 출력
void printStacks(Stack* stack){
    if (isEmpty(stack) == -1) {
        printf("스택 배열이 비었습니다.\n");
        return;
    }
    
    int cnt = stack->top;
    while (cnt != -1) {
        printf("%d\n", stack->nodes[cnt].Data );
        printf("---------\n");
        cnt -= 1;
    }
}



//MARK: main
int main(int argc, const char * argv[]) {
    
    Stack* Stack = NULL;
    createStack(&Stack, 3);
    
    printf("사이즈 : %d\n" , getSize(Stack));
    printStacks(Stack);

    push(Stack , 1);
    push(Stack , 2);
    push(Stack , 3);
    push(Stack , 4);
    
    printf("사이즈 : %d\n" , getSize(Stack));
    
    printStacks(Stack);
    
   
    return 0;
}

 

 

주요 버그 & 문제점 (핵심)

 

1. isEmpty 구현이 잘못됨.

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

 

1. isEmpty는 boolean(비었는지: 1 또는 0)을 반환해야 하는데 top(인덱스값, -1이면 비어있음)을 그대로 리턴하고 있어 호출부에서 잘못 사용합니다. (예: if (isEmpty(stack) == -1) 같은 비직관적 사용으로 이어짐.)
2. pop의 인덱스 처리 오류

stack->top -= 1;
return stack->nodes[stack->top].Data;

 

1. 이렇게 하면 top을 먼저 감소시키므로 실제로는 하나 위의 요소를 건너뛰거나 잘못된 원소를 반환합니다. 올바른 동작은 (A) 현재 top의 값을 저장하고 top-- 하거나 (B) return stack->nodes[stack->top--].Data; 와 같이 한 줄로 처리해야 합니다.
2. 에러 처리 방식(특히 ElementType이 int일 때 -1 충돌 가능)
3. pop/top이 실패하면 -1을 리턴하는데, ElementType이 int라 -1은 유효값일 수 있습니다. 오류를 구분할 수 있는 별도 플래그(예: 호출자가 제공한 bool*), 또는 함수가 성공 여부를 반환하고 값은 출력 파라미터로 받게 하는 방식이 더 안전합니다.
4. NULL 포인터 체크 부족
5. 각 함수들이 stack == NULL을 체크하지 않아 크래시 위험이 있습니다.
6. 메모리 누수/정리 미구현
7. destroyStack 선언은 있지만 구현이 없습니다. createStack에서 nodes 할당이 실패하면 이미 할당한 Stack을 free해주지 않습니다.
8. 이름 충돌/관례
9. Stack* Stack = NULL; 처럼 타입과 동일한 이름을 변수에 쓴 것은 혼동 유발. 소문자 시작(예: stack) 권장.
10. isFull 반환 관례 혼동
11. 현재 isFull은 stack->capacity == (stack->top + 1) 으로 참이면 1, 거짓이면 0을 반환하는데 괜찮지만 읽기 쉽도록 return stack->top == stack->capacity - 1; 가 더 명확합니다.

 

---

 

수정된 코드 — 안전성/버그 수정 + 권장 개선 적용

 

아래 코드는 위 문제들을 모두 고친 버전입니다.

주요 변경:

• isEmpty/isFull 올바르게 구현
• pop/top의 인덱스 처리 수정
• 모든 공용 함수에서 stack == NULL 체크
• destroyStack 구현 (메모리 해제)
• 오류 반환은 int 상태코드(0: 성공, -1: 실패) + 출력 파라미터 방식으로 안전하게 처리 (pop과 top의 경우)
• 변수명과 타입 정리 (size_t 사용 권장 — 여기서는 간단히 int 유지하지만 capacity 체크 추가)
• createStack에서 nodes 할당 실패 시 정리

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

#define ElementType int

typedef struct _Node{
    ElementType Data;
} Node;

typedef struct _Stack{
    int capacity;       // 용량
    int top;            // 최상위 노드 인덱스 (-1: 비어있음)
    Node *nodes;        // 힙에 할당된 노드 배열
} Stack;

// 함수 프로토타입
int createStack(Stack** stack, int capacity); // 성공:0, 실패:-1
void destroyStack(Stack* stack);
int push(Stack* stack , ElementType Data);   // 성공:0, 실패:-1
int pop(Stack* stack, ElementType *out);     // 성공:0, 실패:-1
int peek(Stack* stack, ElementType *out);    // top 조회, 성공:0, 실패:-1
int getSize(Stack* stack);
int isEmpty(Stack* stack);
int isFull(Stack* stack);
void printStack(Stack* stack);

// 구현
int createStack(Stack** stack, int capacity){
    if (capacity <= 0) return -1;
    *stack = (Stack*)malloc(sizeof(Stack));
    if (*stack == NULL) {
        printf("스택 구조체 할당 실패\n");
        return -1;
    }
    (*stack)->nodes = (Node*)malloc(sizeof(Node) * capacity);
    if ((*stack)->nodes == NULL) {
        printf("스택 배열 할당 실패\n");
        free(*stack);
        *stack = NULL;
        return -1;
    }
    (*stack)->top = -1;
    (*stack)->capacity = capacity;
    return 0;
}

void destroyStack(Stack* stack){
    if (stack == NULL) return;
    if (stack->nodes) free(stack->nodes);
    free(stack);
}

int getSize(Stack* stack){
    if (stack == NULL) return 0;
    return stack->top + 1;
}

int isEmpty(Stack* stack){
    if (stack == NULL) return 1; // NULL은 비어있는 것으로 간주
    return (stack->top == -1) ? 1 : 0;
}

int isFull(Stack* stack){
    if (stack == NULL) return 0;
    return (stack->top == stack->capacity - 1) ? 1 : 0;
}

int push(Stack* stack , ElementType Data){
    if (stack == NULL) return -1;
    if (isFull(stack)) {
        printf("스택이 가득 찼습니다.\n");
        return -1;
    }
    stack->nodes[++(stack->top)].Data = Data;
    return 0;
}

int pop(Stack* stack, ElementType *out){
    if (stack == NULL || out == NULL) return -1;
    if (isEmpty(stack)) {
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    *out = stack->nodes[(stack->top)--].Data;
    return 0;
}

int peek(Stack* stack, ElementType *out){
    if (stack == NULL || out == NULL) return -1;
    if (isEmpty(stack)){
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    *out = stack->nodes[stack->top].Data;
    return 0;
}

void printStack(Stack* stack){
    if (stack == NULL) {
        printf("스택 포인터 NULL\n");
        return;
    }
    if (isEmpty(stack)) {
        printf("스택이 비어 있습니다.\n");
        return;
    }
    for (int i = stack->top; i >= 0; --i){
        printf("%d\n", stack->nodes[i].Data);
        printf("---------\n");
    }
}

// 예제 main
int main(int argc, const char * argv[]) {
    Stack* stack = NULL;
    if (createStack(&stack, 3) != 0) {
        return 1;
    }

    printf("사이즈 : %d\n", getSize(stack));
    printStack(stack);

    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    if (push(stack, 4) != 0) {
        printf("push 실패(가득참)\n");
    }

    printf("사이즈 : %d\n", getSize(stack));
    printStack(stack);

    ElementType v;
    if (pop(stack, &v) == 0) {
        printf("pop: %d\n", v);
    }
    if (peek(stack, &v) == 0) {
        printf("top: %d\n", v);
    }

    destroyStack(stack);
    return 0;
}

 

---

 

추가 권장사항 (한 단계 업)

• 동적 확장 (realloc): 고정 용량 대신 push 시 가득 차면 realloc으로 용량을 2배로 늘리는 방식이 실무에서 일반적입니다. (성능/사용성 향상)
• 일관된 타입 사용: capacity와 top에 size_t 사용을 고려하세요 (음수 인덱스 사용하지 않도록 로직 변경 필요). 현재 top을 -1로 두는 관례는 직관적이지만 unsigned와 충돌할 수 있습니다.
• 에러 코드 정형화: 성공/실패 상수(예: #define STACK_OK 0, #define STACK_ERR -1)를 정의하면 읽기 편합니다.
• 범용성: ElementType을 void*로 바꾸면 포인터 기반으로 어떤 타입도 올릴 수 있습니다. (또는 C11 _Generic/매크로 사용)
• 스레드 안정성: 다중 스레드 환경이면 뮤텍스로 보호 필요.
• 테스트 케이스: 경계값(빈 상태, 한 개 남은 상태, 가득 참) 테스트 자동화 하세요.

 

요약

• 핵심 버그: isEmpty 반환값 오용, pop에서 인덱스 감소 위치 오류 — 이 둘만 고쳐도 프로그램이 정상 동작합니다.
• 위에 올린 수정 코드는 안전 검사, 오류 리포팅, 메모리 해제까지 반영한 실행 가능한 예제입니다.
• 원하면 이 코드를 realloc을 이용한 자동 확장 버전이나 void* 기반 범용 스택으로 확장해 드릴게요 — 어떤 방향으로 확장할까요?