[C언어 50강] 37강. ADT 개념 + 스택 구현(배열 기반)

Last updated on 
[C언어 50강] 37강. ADT 개념 + 스택 구현(배열 기반)

C언어에서 자료구조를 배우기 시작하면 가장 먼저 마주치는 전환점이 있습니다. “배열을 쓰면 되는데, 왜 굳이 스택(Stack)이라는 이름을 붙이고 인터페이스를 나누지?” 오늘 주제인 ADT(Abstract Data Type, 추상 자료형)와 배열 기반 스택 구현은 바로 이 질문에 대한 답입니다. 핵심은 단순히 push/pop 코드를 외우는 게 아니라, **데이터를 어떻게 다룰지(정책)**와 **어떻게 저장할지(구현)**를 분리하는 사고를 익히는 것입니다.

핵심 개념

  • ADT는 “무엇을 할 수 있는가(연산 계약)”를 정의하고, 내부 저장 방식은 감춘다.
  • 스택은 LIFO(Last In, First Out) 규칙을 따르며, push, pop, peek, is_empty, is_full이 핵심 연산이다.
  • 배열 기반 스택의 성능은 대부분 O(1)이고 단순·빠르지만, 고정 용량 제한을 반드시 관리해야 한다.
  • 실무에서는 함수 이름/반환 규칙/에러 처리 정책까지 포함해 “인터페이스 품질”이 자료구조 품질을 결정한다.

개념 먼저 이해하기

ADT(추상 자료형)를 처음 배우면 종종 “객체지향 언어에서나 중요한 개념 아닌가요?”라는 오해를 합니다. 하지만 ADT는 C에서 오히려 더 중요합니다. C는 언어 차원에서 캡슐화를 강제해 주지 않기 때문에, 개발자가 의식적으로 “이 구조체를 직접 만지지 말고 함수로만 다루자”라는 경계를 세워야 코드가 유지됩니다. 즉 ADT는 문법 기능이 아니라 설계 규칙입니다.

스택을 예로 보면, 사용자는 사실 내부가 궁금하지 않습니다. 사용자가 궁금한 것은 “값을 넣을 수 있나?”, “마지막 값을 꺼낼 수 있나?”, “비어 있나?” 같은 동작입니다. 내부를 배열로 하든 연결 리스트로 하든, 사용자 입장에서는 동작이 같아야 합니다. 이게 ADT의 핵심입니다. 구현이 바뀌어도 계약이 유지되면, 스택을 쓰는 다른 코드(예: 괄호 검사기, 실행 취소 기능, DFS)는 거의 수정 없이 계속 동작합니다.

왜 이런 분리가 중요한지 실전 관점에서 보겠습니다. 초보 단계에서는 종종 아래처럼 작성합니다: int top = -1; int arr[100];를 여러 파일에서 공유하고, 어디서든 top++, arr[top] = x를 직접 수행합니다. 처음엔 빠르지만 규모가 커지면 바로 무너집니다. 누군가 top을 잘못 감소시키거나 범위를 체크하지 않으면 버그가 전체 프로그램으로 퍼집니다. 반면 stack_push(&s, value) 같은 API를 통하게 하면 범위 체크를 한 군데서 통제할 수 있고, 실패 정책도 일관되게 만들 수 있습니다.

배열 기반 스택의 내부 원리는 단순합니다. top을 “현재 마지막 원소의 인덱스”로 두고, 비어 있으면 -1로 시작합니다. push는 ++top 위치에 저장, pop은 현재 top 값을 읽고 --top 합니다. 여기서 중요한 건 문법이 아니라 상태 불변식(invariant) 입니다. 예를 들면 다음 규칙이 항상 참이어야 합니다.

  1. -1 <= top < capacity
  2. 원소 개수는 top + 1
  3. 빈 스택은 top == -1

이 불변식이 깨지면 자료구조는 즉시 신뢰를 잃습니다. 그래서 실무에서는 연산 하나하나보다 “연산 후에도 불변식이 유지되는가”를 기준으로 코드를 리뷰합니다. 자료구조 버그가 무서운 이유는, 에러가 난 지점이 아니라 몇 단계 뒤 전혀 다른 위치에서 크래시가 터지기 때문입니다.

또 하나 중요한 포인트는 반환 정책입니다. C에서 pop은 실패 가능 연산입니다(빈 스택). 그러면 함수 시그니처를 어떻게 설계할까요? 흔한 방식은 세 가지입니다. (1) 실패 시 특정 값 반환(예: -1), (2) bool 반환 + out-parameter, (3) assert로 프로그램 중단. 실무에서는 대체로 (2)를 선호합니다. 데이터 값의 범위와 에러를 분리할 수 있기 때문입니다. 예를 들어 스택에 -1도 정상 데이터로 들어갈 수 있다면 (1)은 설계 자체가 모호해집니다.

정리하면 ADT 학습의 목표는 “스택 구현법 암기”가 아니라, 경계와 계약을 명확히 하여 코드 변경 비용을 낮추는 습관을 익히는 데 있습니다. 오늘은 배열 기반으로 시작하지만, 같은 인터페이스로 연결 리스트 기반 스택으로 바꿔도 사용자 코드는 거의 안 바뀌게 만드는 것이 진짜 실력입니다.

기본 사용

예제 1) 최소 동작 스택 ADT

#include <stdio.h>
#include <stdbool.h>

#define STACK_CAPACITY 5

typedef struct {
    int data[STACK_CAPACITY];
    int top; // 마지막 원소 인덱스, 비었으면 -1
} IntStack;

void stack_init(IntStack *s) {
    if (!s) return;
    s->top = -1;
}

bool stack_is_empty(const IntStack *s) {
    return !s || s->top == -1;
}

bool stack_is_full(const IntStack *s) {
    return s && s->top == STACK_CAPACITY - 1;
}

bool stack_push(IntStack *s, int value) {
    if (!s || stack_is_full(s)) return false;
    s->data[++(s->top)] = value;
    return true;
}

bool stack_pop(IntStack *s, int *out) {
    if (!s || stack_is_empty(s) || !out) return false;
    *out = s->data[(s->top)--];
    return true;
}

int main(void) {
    IntStack s;
    stack_init(&s);

    stack_push(&s, 10);
    stack_push(&s, 20);
    stack_push(&s, 30);

    int v;
    while (stack_pop(&s, &v)) {
        printf("%d\n", v); // 30, 20, 10
    }
    return 0;
}

설명:

  • top을 -1부터 시작하면 빈 상태 표현이 직관적이다.
  • push/pop은 O(1)이고, 포인터 이동 없이 인덱스만 갱신한다.
  • 반환형을 bool로 두고 실제 값은 out으로 돌려주면 에러와 데이터를 분리할 수 있다.

예제 2) 실무형 패턴: 사이즈/에러 메시지 포함

#include <stdio.h>
#include <stdbool.h>

#define CAP 3

typedef struct {
    int buf[CAP];
    int top;
} Stack;

void stack_init(Stack *s) { s->top = -1; }
int stack_size(const Stack *s) { return s ? (s->top + 1) : 0; }
bool stack_is_full(const Stack *s) { return s && s->top >= CAP - 1; }
bool stack_is_empty(const Stack *s) { return !s || s->top < 0; }

bool stack_push(Stack *s, int x) {
    if (!s) return false;
    if (stack_is_full(s)) {
        fprintf(stderr, "[stack] push failed: full (size=%d, cap=%d)\n", stack_size(s), CAP);
        return false;
    }
    s->buf[++s->top] = x;
    return true;
}

bool stack_peek(const Stack *s, int *out) {
    if (!s || !out || stack_is_empty(s)) return false;
    *out = s->buf[s->top];
    return true;
}

int main(void) {
    Stack s;
    stack_init(&s);

    stack_push(&s, 1);
    stack_push(&s, 2);
    stack_push(&s, 3);
    stack_push(&s, 4); // 실패 로그

    int top;
    if (stack_peek(&s, &top)) {
        printf("top=%d, size=%d\n", top, stack_size(&s));
    }
    return 0;
}

설명:

  • 실무에서는 “실패했다”만으로는 부족하고, 디버깅 가능한 문맥(size/capacity)을 함께 남겨야 한다.
  • peek를 두면 pop 없이 현재 상태를 확인할 수 있어 상태 머신 디버깅에 유용하다.
  • 사이즈 API를 별도로 두면 호출자가 top 내부 규칙을 몰라도 된다.

예제 3) 디버깅 포인트 포함: 괄호 검사기

#include <stdio.h>
#include <stdbool.h>

#define MAX 128

typedef struct {
    char a[MAX];
    int top;
} CharStack;

void init(CharStack *s) { s->top = -1; }
bool empty(const CharStack *s) { return s->top == -1; }
bool full(const CharStack *s) { return s->top == MAX - 1; }

bool push(CharStack *s, char c) {
    if (full(s)) return false;
    s->a[++s->top] = c;
    return true;
}

bool pop(CharStack *s, char *out) {
    if (empty(s)) return false;
    *out = s->a[s->top--];
    return true;
}

bool is_balanced(const char *expr) {
    CharStack s;
    init(&s);

    for (int i = 0; expr[i] != '\0'; ++i) {
        if (expr[i] == '(') {
            if (!push(&s, '(')) return false; // 오버플로
        } else if (expr[i] == ')') {
            char tmp;
            if (!pop(&s, &tmp)) return false; // 언더플로: 닫는 괄호가 더 많음
        }
    }
    return empty(&s); // 여는 괄호가 남았는지 검사
}

int main(void) {
    const char *ok = "(a+(b*c))";
    const char *bad = "(a+b))(";

    printf("%s -> %s\n", ok, is_balanced(ok) ? "OK" : "BAD");
    printf("%s -> %s\n", bad, is_balanced(bad) ? "OK" : "BAD");
    return 0;
}

설명:

  • 스택 ADT의 장점은 도메인 문제(괄호 검사)에 바로 적용된다는 점이다.
  • push/pop 실패를 각각 오버플로/언더플로 신호로 해석하면 문제 원인을 빠르게 찾을 수 있다.
  • 입력 검증 루프에서 실패를 즉시 반환하면 이후 상태 오염을 막을 수 있다.

자주 하는 실수

실수 1) top 의미를 일관되게 정의하지 않음

  • 원인: 어떤 함수는 top을 “원소 개수”, 다른 함수는 “마지막 인덱스”로 취급.
  • 해결: 한 프로젝트에서 하나의 규칙만 사용하고, 주석/함수명으로 명확히 고정한다.

실수 2) push/pop 경계 검사 누락

  • 원인: “테스트 데이터가 작아서 괜찮다”는 가정.
  • 해결: 모든 연산에서 is_full, is_empty를 먼저 확인하고 실패 경로를 테스트한다.

실수 3) 실패를 데이터 값으로 표현

  • 원인: pop() 실패 시 -1 반환 같은 단순화.
  • 해결: bool + out-parameter 또는 오류코드(enum) 방식으로 인터페이스를 분리한다.

실수 4) ADT라면서 내부 필드를 외부에서 직접 수정

  • 원인: 급하게 구현하면서 s.top-- 같은 직접 접근을 허용.
  • 해결: 모듈 경계(.h/.c 분리)를 만들고, 구조체를 외부에서 불투명하게 다루는 방향으로 리팩터링한다.

실무 패턴

  • 스택 API 계약을 먼저 문서화한다: 입력 조건, 실패 조건, 시간복잡도.
  • stack_init을 누락하면 치명적이므로, 생성 직후 초기화를 강제하는 래퍼를 둔다.
  • 디버그 빌드에서는 assert를 적극 사용하고, 릴리즈 빌드에서는 안전한 실패 반환으로 전환한다.
  • 테스트는 정상 케이스보다 경계 케이스(가득 참, 비어 있음, NULL 인자)를 더 많이 만든다.
  • 향후 확장을 위해 인터페이스를 유지한 채 내부 구현(배열→연결리스트)을 교체할 수 있게 설계한다.

실무에서 스택은 단독 기능보다 더 큰 기능의 하부 부품으로 자주 쓰입니다. 파서, 실행 취소(undo), 괄호/태그 검증, DFS, 수식 계산 등에서 스택이 등장합니다. 따라서 “내가 만든 스택이 다른 팀 코드에서도 안전하게 재사용될 수 있는가?”를 목표로 구현하면 훨씬 좋은 품질에 도달할 수 있습니다.

오늘의 결론

한 줄 요약: 스택 구현의 본질은 배열 문법이 아니라 ADT 계약을 지켜 경계·에러·불변식을 통제하는 설계 습관이다.

오늘 배운 내용을 제대로 체화하면 다음 강의의 연결 리스트, 이후의 큐/트리 같은 자료구조에서도 같은 기준으로 사고할 수 있습니다. 구현 디테일은 달라져도, 좋은 인터페이스와 안전한 경계 처리는 끝까지 동일합니다.

연습문제

  1. int 스택에 stack_clear 함수를 추가해 보세요. 내부 버퍼를 지울 필요가 있는지/없는지도 함께 설명해 보세요.
  2. pop 대신 try_pop이라는 이름으로 인터페이스를 바꾸고, 실패 원인을 enum(STACK_OK, STACK_EMPTY, STACK_BAD_ARG)으로 반환하도록 개선해 보세요.
  3. 괄호 검사 예제를 확장해 (), {}, [] 세 종류 괄호를 모두 검사하도록 수정해 보세요.
  4. 배열 기반 스택의 용량 제한 문제를 완화하기 위해 realloc 기반 동적 확장 전략을 설계해 보세요(코드 없이 설계만).

이전 강의 정답

지난 36강 연습문제의 핵심은 타입 설계 도구를 “의미 전달”에 활용하는 것이었습니다. 대표 정답 예시는 아래와 같습니다.

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

typedef uint32_t ProductId;

typedef enum {
    ORDER_CREATED = 0,
    ORDER_PAID,
    ORDER_SHIPPED,
    ORDER_CANCELED
} OrderState;

const char* order_state_to_string(OrderState s) {
    switch (s) {
        case ORDER_CREATED:  return "CREATED";
        case ORDER_PAID:     return "PAID";
        case ORDER_SHIPPED:  return "SHIPPED";
        case ORDER_CANCELED: return "CANCELED";
        default:             return "UNKNOWN";
    }
}

int find_product(ProductId id) {
    // 데모용: 존재하면 1, 없으면 0
    return id == 1001u;
}

int main(void) {
    ProductId id = 1001u;
    printf("find_product(%u)=%d\n", id, find_product(id));

    OrderState st = ORDER_PAID;
    printf("state=%s\n", order_state_to_string(st));
    return 0;
}

해설 포인트:

  • ProductId 별칭으로 값의 도메인 의미를 드러내면 함수 시그니처가 읽기 쉬워진다.
  • enum + 문자열 변환 함수는 로그/디버깅에서 유지보수 비용을 크게 줄인다.
  • default 분기를 남겨 예기치 못한 값에도 관찰 가능성을 확보한다.

실습 환경/재현 정보

  • 컴파일러: clang 17+ 또는 gcc 13+
  • 컴파일 옵션: -std=c11 -Wall -Wextra -O2
  • 실행 환경: macOS(Apple Silicon), Linux x86_64 터미널
  • 재현 체크:
    • 예제 코드 3개가 경고 없이 컴파일되는지 확인
    • 가득 찬 스택에서 push 실패, 빈 스택에서 pop 실패가 정상 처리되는지 확인
    • top 불변식(-1 <= top < capacity)이 모든 연산 후 유지되는지 확인
    • 괄호 검사 예제에서 정상/비정상 입력을 각각 검증했는지 확인