스택 자료구조의 LIFO 동작과 동시성 설계

가장 최근 상태를 먼저 되돌리는 구조

스택은 가장 마지막에 삽입한 요소부터 꺼내는 후입선출(LIFO, Last-In First-Out) 자료구조다. 함수 호출 관리, 파싱, 백트래킹처럼 현재 상태에서 바로 이전 상태로 거슬러 올라가야 하는 흐름에 자연스럽게 맞는다. 운영체제의 호출 스택, 가상머신 런타임, 컴파일러와 인터프리터의 평가기에도 이 규율이 쓰인다.

기본 연산은 삽입하는 push, 제거하는 pop, 제거하지 않고 최상단을 확인하는 peek이다. 평균적으로 push/pop/peek는 O(1)이며, 배열 기반 스택은 캐시 적중률이 높아 상수 시간이 작고 예측 가능하다.

빈 스택에서 pop 또는 peek를 호출하면 언더플로가 발생한다. 고정 용량 스택에 더 넣으려 하면 오버플로가 발생한다. 이 두 경계는 구현 단계에서 명시적으로 처리해야 한다.

top이 지켜야 하는 불변식

스택의 접근 지점은 top 포인터 또는 인덱스다. push는 요소를 기록한 뒤 top을 증가시키고, pop은 top을 감소시킨 뒤 해당 요소를 반환한다. 이 순서가 깨지면 스택의 일관성도 무너진다.

검증 기준은 0 ≤ top ≤ capacity 범위와 top 갱신의 원자성이다. 단일 생산자·소비자 환경에서는 락 없이도 안전할 수 있지만, 다중 스레드 환경에서는 뮤텍스나 원자적 CAS를 사용하는 lock-free 방식이 필요하다. lock-free 스택에서는 push/pop 단위의 원자성뿐 아니라 Tags, hazard pointers 등을 통한 ABA 문제 방지도 고려한다.

배열과 연결 리스트의 선택

배열 기반 스택은 연속된 메모리를 사용하므로 캐시 효율과 분기 예측 측면에서 유리하다. 인덱스로 접근하므로 오버헤드가 낮고 구현도 단순하다. 다만 고정 용량이라면 오버플로 위험을 관리해야 하며, 가변 배열은 리사이즈 비용이 생길 수 있다.

연결 리스트 기반 스택은 노드를 추가하며 확장할 수 있어 초기 용량 계획이 필요 없다. 대신 노드 할당 비용과 포인터 추적에 따른 상수 비용이 있고, 캐시 지역성이 낮다. 메모리 파편화와 가비지 컬렉션 환경의 GC 압력도 운영 시 고려 대상이다.

구현	성능(평균)	확장성	일관성	안정성	운영 편의
배열 기반 스택	O(1) 매우 빠름, 캐시 효율 높음	고정 용량은 재할당 필요, 가변은 리사이즈 비용 발생	단순 top 인덱스 불변식으로 검증 용이	메모리 연속성으로 예측 가능, 오버플로 주의	구현 단순, 메모리 추정 필요
연결 리스트 기반 스택	O(1)이나 포인터 추적으로 상수 비용 큼	노드 단위로 사실상 무제한 확장	노드 할당/해제의 실패·지연 가능성	메모리 파편화·GC 압력 가능	초기 용량 계획 불필요, 디버깅 난이도 증가

push와 pop에서 발생하는 경계 조건

push는 용량 확인, 요소 기록, top 증가 순서로 처리한다. 고정 용량을 초과하면 예외를 반환하고, 가변 용량이라면 재할당으로 확장할 수 있다.

pop은 공백 여부를 먼저 확인한 뒤 top을 감소시키고 값을 반환한다. peek은 top - 1 위치를 비파괴적으로 조회한다. 언더플로는 예외 또는 특수 값으로 처리할 수 있으며, 실무에선 예외를 권장한다.

⤢✕

단일 락은 구현을 간결하게 만든다. 경합이 높은 환경에서는 CAS 기반 lock-free 스택을 고려할 수 있지만, ABA 문제를 막는 장치가 필요하다.

호출 흐름부터 탐색 상태까지

함수 호출에서는 프레임을 push하고 반환할 때 pop하여 지역 변수와 리턴 주소를 관리한다. 예외가 전파될 때는 스택을 언와인딩하며 복구 흐름을 구성한다.

파서와 컴파일러는 토큰을 스캔하면서 여는 기호를 push하고, 닫는 기호를 만날 때 매칭하여 pop한다. 남은 스택이 비어 있으면 괄호 검증이 성공한다. 중위식은 후위식으로 변환한 뒤 계산할 수 있다.

Undo/Redo는 작업 상태 스냅샷을 Undo 스택에 넣고, Undo 시에는 해당 상태를 Redo 스택으로 옮긴다. 트랜잭션 경계와 함께 다룰 수도 있다.

백트래킹과 DFS에서는 방문 노드를 push하고 인접 노드를 탐색하다가 막다른 길에서 pop한다. 재귀 대신 명시적 스택을 쓰면 스택 오버플로 위험을 제어할 수 있다. 웹 브라우저의 이동 기록도 forward와 backward를 별도 스택으로 관리하며, 이동할 때 서로 push/pop한다.

Python 구현

환경/버전: Python 3.10+, 단일 프로세스, 선택적 스레드 안전

# python 3.10+
from threading import Lock
from typing import Generic, TypeVar, Optional

T = TypeVar("T")

class StackEmpty(Exception): ...
class StackFull(Exception): ...

class Stack(Generic[T]):
    def __init__(self, capacity: Optional[int] = None, thread_safe: bool = False):
        self._data: list[T] = [] if capacity is None else [None] * capacity  # type: ignore
        self._top: int = 0
        self._capacity = capacity
        self._lock = Lock() if thread_safe else None

    def is_empty(self) -> bool:
        return self._top == 0

    def is_full(self) -> bool:
        return self._capacity is not None and self._top >= self._capacity

    def push(self, value: T) -> None:
        if self._lock:
            with self._lock:
                self._push_inner(value)
        else:
            self._push_inner(value)

    def _push_inner(self, value: T) -> None:
        if self._capacity is None:
            self._data.append(value)
            self._top += 1
        else:
            if self._top >= self._capacity:
                raise StackFull("stack overflow")
            self._data[self._top] = value
            self._top += 1

    def pop(self) -> T:
        if self._lock:
            with self._lock:
                return self._pop_inner()
        else:
            return self._pop_inner()

    def _pop_inner(self) -> T:
        if self._top == 0:
            raise StackEmpty("stack underflow")
        self._top -= 1
        val = self._data[self._top]
        if self._capacity is None:
            self._data.pop()
        return val  # type: ignore

    def peek(self) -> T:
        if self._top == 0:
            raise StackEmpty("stack is empty")
        return self._data[self._top - 1]  # type: ignore

# 사용 예
if __name__ == "__main__":
    s = Stack[int](capacity=3, thread_safe=True)
    s.push(10); s.push(20); print(s.peek())  # 20
    print(s.pop())  # 20
    print(s.pop())  # 10
    try:
        s.pop()
    except StackEmpty:
        print("빈 스택 예외 처리 완료")

고정 용량을 쓸 때는 예상 피크에 20~30% 여유를 둔다. 고경합 환경에서는 lock-free(CAS)를 검토할 수 있으나, ABA 문제 방지 장치가 전제되어야 한다.

배열 기반 구현은 캐시 적중률 향상으로 5~20% 처리량 개선이 가능하다(워크로드 의존). 오버플로와 언더플로를 분명한 오류 경계로 두면 결함을 격리하기 쉬우며, 호출 스택 기반의 예외 복구도 간결해진다. top 변화는 단순한 로깅 포인트가 되어 모니터링과 디버깅을 단순화하고, 메모리 사용량을 예측하는 데에도 도움이 된다.