스택(Stack)의 개념과 구현: LIFO 원리와 활용

**스택(Stack)**은 한쪽 끝에서만 데이터의 삽입과 삭제가 일어나는 선형 자료구조입니다. 가장 나중에 들어간 데이터가 가장 먼저 나오는 후입선출(LIFO, Last-In First-Out) 메커니즘을 따릅니다.

1. 스택의 핵심 개념과 LIFO 메커니즘

스택은 접시를 차곡차곡 쌓아 올린 형태와 같습니다. 새로운 접시는 맨 위에 쌓이고, 사용할 때도 맨 위의 접시부터 꺼내게 됩니다.

• 상단(Top): 데이터의 삽입과 삭제가 이루어지는 스택의 끝 위치.
• 하단(Bottom): 가장 먼저 들어간 데이터가 위치하는 스택의 바닥.
• LIFO (Last-In First-Out): 마지막에 들어온(Last-In) 데이터가 가장 먼저 나가는(First-Out) 구조.

2. 스택의 주요 연산

스택이 제공하는 기본 연산은 다음과 같습니다.

3. 파이썬 기반 스택 구현

파이썬에서는 리스트(List)의 append()와 pop() 메서드를 사용하거나, collections.deque를 활용하여 스택을 효율적으로 구현할 수 있습니다.

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

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

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items[-1]

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

    def size(self):
        return len(self._items)

# 사용 예시
s = Stack()
s.push(10)
s.push(20)
print(s.peek())  # 20
print(s.pop())   # 20
print(s.pop())   # 10

4. 대표적인 스택 활용 사례

1. 함수 호출 스택 (Call Stack): 프로그램 실행 중 함수가 호출될 때 복귀 주소와 지역 변수를 스택에 저장합니다.
2. 웹 브라우저 뒤로 가기 / 앞으로 가기: 방문한 페이지 이력을 두 개의 스택으로 관리합니다.
3. 수식의 괄호 쌍 검사: 열린 괄호 (, {, [를 만날 때 스택에 push하고, 닫힌 괄호를 만날 때 pop하여 짝이 맞는지 검사합니다.
4. 텍스트 에디터 Undo(실행 취소): 작업 이력을 스택에 기록하여 최신 작업부터 취소합니다.

5. 자주 묻는 질문 (Q&A)

Q. 스택 오버플로(Stack Overflow)란 무엇인가요? A. 고정된 크기의 스택 메모리 공간이 가득 찬 상태에서 추가로 데이터를 push하려고 할 때 발생하는 오류입니다. 재귀 함수가 무한 호출될 때 흔히 발생합니다.

Q. 배열 기반 스택과 연결 리스트 기반 스택의 차이는 무엇인가요? A. 배열 기반은 메모리가 연속적이고 접근이 빠르지만 크기가 고정될 수 있습니다. 연결 리스트 기반은 동적으로 크기를 늘릴 수 있으나 포인터 저장 메모리가 추가로 소요됩니다.