길리랩blog

스택 자료구조: LIFO 구현과 경계 조건 설계

스택의 LIFO 동작, 배열·연결 리스트 구현 차이, Push·Pop 경계 처리와 C 구현 방식을 정리한다.

2026-08-14 · 최초 발행 2024-04-29

마지막에 넣은 값이 먼저 나오는 규칙

스택은 프로그램의 실행 흐름과 메모리 관리에서 자주 만나는 자료구조다. 마지막으로 넣은 요소를 먼저 꺼내는 LIFO(Last In First Out), 즉 후입선출 규칙을 따른다. 함수 호출, 수식 파싱, 백트래킹에 쓰이는 이유도 이 순서에 있다.

핵심 연산은 다음과 같다.

  • Push: 요소 삽입
  • Pop: 최상단 요소를 삭제하고 반환
  • Top 또는 Peek: 최상단 요소 조회
  • IsEmpty와 IsFull: 상태 확인

배열 스택에서 Top은 요소 수이자 다음 삽입 위치로 둘 수 있다. 이 경우 유효 인덱스 범위는 0 ≤ Top ≤ Capacity이며, 최상단 요소는 Top-1에 놓인다. 이 불변식을 지키면 삽입과 삭제의 기준이 명확해진다.

메모리 표현이 달라지면 관리 지점도 달라진다

배열 기반 스택은 연속된 메모리에 요소를 저장하고 인덱스로 접근한다. 캐시 친화적인 구조이며, 경계도 Top과 Capacity로 비교할 수 있다. 반면 연결 리스트 기반 스택은 노드마다 메모리를 할당하므로 동적 확장이 쉽지만 포인터와 할당 상태를 함께 관리해야 한다.

두 방식 모두 Push와 Pop은 평균·최악 O(1)로 처리한다. 배열을 자동 확장할 때는 재할당 비용 O(n)이 발생할 수 있지만, 전체 연산 관점에서는 아몰타이즈드 O(1)이다.

구현에서 빠지기 쉬운 지점은 경계와 실패 처리다.

  • 스택이 가득 찬 Overflow와 비어 있는 Underflow를 처리해야 한다.
  • 입력 유효성, 메모리 할당 실패, 동시성 조건에 대한 예외 처리 설계가 필요하다.
  • Top을 증감하는 순서를 일관되게 유지하고, 실패하면 롤백하거나 에러 코드를 반환해야 한다.
  • 멀티스레드 환경에서는 락 또는 CAS 기반으로 원자성을 확보한다.

호출 프레임부터 탐색 이력까지

스택은 최근 상태를 되돌리거나 중첩된 작업을 관리하는 상황에 맞는다.

  • 함수 호출 스택과 예외 처리 스택 관리
  • RPN, 괄호 유효성 검사 같은 수식 파싱 및 평가
  • DFS(깊이 우선 탐색), 백트래킹, Undo/Redo 이력 관리
  • 인터프리터·가상머신의 프레임 스택과 지역 변수 저장

배열 스택에서 Top을 다루는 방식

배열 스택은 최대 용량인 Capacity, 다음 삽입 위치를 가리키는 Top, 요소 저장 배열인 Nodes로 구성할 수 있다.

Top == 0이면 비어 있고, Top == Capacity이면 가득 찬 상태다. Push(data)는 여유 공간을 확인한 뒤 Nodes[Top]에 데이터를 넣고 Top을 증가시킨다. Pop()은 비어 있지 않은지 확인한 뒤 Top을 감소시키고 그 위치의 요소를 반환한다. 가득 찼을 때는 realloc으로 확장하거나 에러를 반환하며, 비어 있을 때는 에러를 반환한다.

⤢✕NoYesNoYesPush(data)IsFull?Nodes[Top]=dataTop++Grow or ErrorPop()IsEmpty?Top--return Nodes[Top].DataUnderflow Error

POSIX 또는 표준 C 환경을 전제로 하며, 컴파일 명령어 예시는 gcc -std=c11 -O2 stack.c -o stack이다.

// stack.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElementType;

typedef struct {
    ElementType Data;
} Node;

typedef struct {
    int Capacity;   // 용량
    int Top;        // 요소 수(다음 삽입 위치)
    Node* Nodes;    // 노드 배열
} ArrayStack;

// 생성자
ArrayStack* AS_Create(int capacity) {
    if (capacity <= 0) return NULL;
    ArrayStack* s = (ArrayStack*)malloc(sizeof(ArrayStack));
    if (!s) return NULL;
    s->Nodes = (Node*)malloc(sizeof(Node) * capacity);
    if (!s->Nodes) { free(s); return NULL; }
    s->Capacity = capacity;
    s->Top = 0;
    return s;
}

// 파괴자
void AS_Destroy(ArrayStack* s) {
    if (!s) return;
    free(s->Nodes);
    free(s);
}

bool AS_IsEmpty(const ArrayStack* s) { return s->Top == 0; }
bool AS_IsFull(const ArrayStack* s)  { return s->Top == s->Capacity; }

// 옵션: 자동 확장
bool AS_EnsureCapacity(ArrayStack* s) {
    if (!AS_IsFull(s)) return true;
    int newCap = (s->Capacity < 1) ? 1 : (s->Capacity * 2);
    Node* p = (Node*)realloc(s->Nodes, sizeof(Node) * newCap);
    if (!p) return false;
    s->Nodes = p;
    s->Capacity = newCap;
    return true;
}

// Push
bool AS_Push(ArrayStack* s, ElementType data) {
    if (!AS_EnsureCapacity(s)) return false;
    s->Nodes[s->Top++].Data = data;
    return true;
}

// Pop
bool AS_Pop(ArrayStack* s, ElementType* out) {
    if (AS_IsEmpty(s)) return false;
    ElementType val = s->Nodes[--s->Top].Data;
    if (out) *out = val;
    return true;
}

// Top/Peek
bool AS_Top(const ArrayStack* s, ElementType* out) {
    if (AS_IsEmpty(s)) return false;
    if (out) *out = s->Nodes[s->Top - 1].Data;
    return true;
}

// 간단 테스트
int main(void) {
    ArrayStack* s = AS_Create(2);
    if (!s) { fprintf(stderr, "create failed\n"); return 1; }

    AS_Push(s, 10);
    AS_Push(s, 20);
    AS_Push(s, 30); // 자동 확장

    ElementType x;
    while (AS_Pop(s, &x)) {
        printf("pop: %d\n", x);
    }
    AS_Destroy(s);
    return 0;
}

typeof, ArraysStack, ElementyType, retrun처럼 표준 C와 맞지 않거나 식별자 표기가 흔들리는 코드는 피하는 편이 낫다. typedef와 일관된 식별자를 사용하면 컴파일과 유지보수 과정에서 혼선을 줄일 수 있다.

배열과 연결 리스트 중 무엇을 선택할지

항목 배열 스택 연결 리스트 스택
성능 Push/Pop O(1), 캐시 적중률 우수 Push/Pop O(1), 포인터 오버헤드
확장성 재할당 필요(아몰타이즈드 O(1)) 요소당 동적 할당, 사실상 메모리 한도까지 확장
일관성 인덱스 불변식 간단, 경계 명확 포인터 무결성 관리 필요
안정성 단편화 낮음, 재할당 실패 시 취약 단편화 가능성, 할당 실패 시 롤백 필요
운영 편의 구현·디버깅 용이, 직렬화 쉬움 파편화/누수 점검 필요, 커스텀 allocator 유용

배열 방식은 단순한 인덱스 불변식과 지역성이 필요할 때 적합하다. 연결 리스트 방식은 용량을 미리 정하기 어렵고 노드 단위 확장이 필요한 경우에 선택할 수 있다.

FIFO가 필요한 문제는 큐로 분리한다

스택은 마지막에 넣은 데이터를 먼저 꺼내며 DFS와 Undo/Redo에 사용된다. 큐는 먼저 넣은 데이터를 먼저 꺼내며 BFS와 작업 대기열에 사용된다.

Rear insert, Front out, front==rear 공백 상태 같은 설명은 원형 큐(Queue)의 성질이다. 스택의 Pop은 Top-- 후 요소를 반환하고, 큐의 Dequeue는 Front++ 또는 Front = (Front+1) % M 후 요소를 반환한다. 사용하는 맥락과 불변식이 다르므로 두 구조를 분리해 구현하는 편이 안전하다.

배열 스택은 지역성이 높아 캐시 효율을 높이면서 연산 O(1)을 보장할 수 있다. 일관된 경계·에러 처리는 언더플로와 오버플로를 막고, 명확한 불변식과 API 분리는 테스트와 검증을 쉽게 만든다. 자동 확장 전략을 도입하면 다양한 워크로드에도 대응할 수 있다.

스택자료구조LIFOC 언어알고리즘