CS학습2026년 8월 15일

스택 Stack: 후입선출(LIFO) 방식으로 동작하는 자료구조

스택은 데이터를 쌓아 올린 형태의 자료구조로, 가장 최근에 추가된 데이터부터 접근한다. 웹 브라우저 방문 기록, 함수 호출 스택 등 다양한 분야에서 활용된다. Push와 Pop 연산을 통해 데이터를 관리하며, 제한된 크기를 가질 수 있다.

송민성4분 읽기

1. 개념

스택(Stack)은 Last-In, First-Out (LIFO, 후입선출) 원칙을 따르는 추상 데이터 타입(Abstract Data Type, ADT)이다. 마치 접시를 쌓아 올린 것과 유사하게, 가장 마지막에 추가된 항목이 가장 먼저 제거된다. 스택은 데이터를 저장하고 검색하는 데 사용되며, 일반적으로 Push (데이터 삽입)와 Pop (데이터 삭제) 연산을 제공한다.

2. 왜 사용하는가

스택은 다음과 같은 경우에 유용하다:

함수 호출 관리: 함수 호출 시 활성화 레코드(activation record)를 저장하여 반환 주소를 추적하고, 함수 실행이 끝나면 해당 레코드를 제거한다.
재귀 호출 처리: 재귀 함수의 각 호출 스택을 관리하는 데 사용된다.
실행 취소/다시 실행 (Undo/Redo): 사용자의 작업을 스택에 저장하여 이전 상태로 되돌리거나, 다시 실행할 수 있도록 한다.
수식 평가: 중위 표기법(infix notation)을 후위 표기법(postfix notation)으로 변환하고, 이를 이용하여 수식을 평가하는 데 사용된다.

3. 동작 원리

스택은 다음과 같은 기본 연산을 통해 동작한다:

Push (삽입): 스택의 맨 위에 새로운 데이터를 추가한다.
Pop (삭제): 스택의 맨 위에서 데이터를 제거하고 반환한다.
Peek (확인): 스택의 맨 위 데이터에 접근하여 값을 확인하지만, 제거하지는 않는다.
isEmpty: 스택이 비어 있는지 여부를 확인한다.

스택은 배열 또는 연결 리스트(linked list)를 사용하여 구현할 수 있다. 배열을 사용하면 메모리 접근 속도가 빠르지만, 크기를 미리 정해야 한다는 단점이 있다. 연결 리스트는 동적으로 크기가 변하지만, 메모리 간접 접근으로 인해 성능 저하가 발생할 수 있다.

4. 코드 예제

python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None  # or raise an exception

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

# 사용 예시
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2
print(stack.is_empty()) # Output: False

5. 시간 복잡도 또는 성능 특성

Push: O(1) - 배열의 끝에 추가하는 연산이므로 상수 시간이 소요된다. 연결 리스트를 사용하는 경우에도 마찬가지이다.
Pop: O(1) - 배열의 마지막 요소를 제거하는 연산이므로 상수 시간이 소요된다. 연결 리스트에서는 head 포인터를 업데이트하므로 상수 시간이다.
Peek: O(1) - 맨 위 요소에 접근하는 연산은 상수 시간을 소요한다.
isEmpty: O(1) - 스택의 크기를 확인하는 연산이므로 상수 시간이 소요된다.

6. 실무 사용 사례

웹 개발에서 스택은 다음과 같이 활용될 수 있다:

브라우저 방문 기록 관리: 웹 브라우저는 사용자의 방문 페이지를 스택에 저장하여 "뒤로 가기" 기능을 구현한다.
콜백 함수 처리: 이벤트 루프 기반의 JavaScript 환경에서 콜백 함수를 스택에 쌓아 순차적으로 실행한다. (TypeScript 코드 예시)

typescript

const callbackStack: (() => void)[] = [];

function enqueueCallback(callback: () => void): void {
  callbackStack.push(callback);
}

function processCallbacks(): void {
  while (callbackStack.length > 0) {
    const callback = callbackStack.pop();
    if (callback) {
      callback();
    }
  }
}

// 예시
enqueueCallback(() => console.log("First Callback"));
enqueueCallback(() => console.log("Second Callback"));

processCallbacks(); // Output: First Callback, Second Callback

7. 주의할 점

스택 오버플로우(Stack Overflow): 정해진 크기의 스택에 너무 많은 데이터를 Push하면 발생한다. 특히 재귀 호출의 경우 깊이가 깊어지면 스택 오버플로우가 발생할 수 있으므로 주의해야 한다.
비어있는 스택에서의 Pop/Peek: 스택이 비어 있는 상태에서 Pop 또는 Peek 연산을 수행하려고 하면 오류가 발생한다. 항상 isEmpty() 메서드로 확인 후 연산을 진행해야 한다.

8. 핵심 정리

스택은 LIFO 원칙을 따르는 자료구조로, Push와 Pop 연산을 통해 데이터를 관리한다. 함수 호출 스택, 재귀 호출 처리, 실행 취소/다시 실행 등 다양한 분야에서 활용된다. 각 연산의 시간 복잡도는 O(1)로 효율적이며, 스택 오버플로우 및 비어있는 스택에서의 연산에 대한 주의가 필요하다.