[Python-알고리즘] 스택

스택(Stack) 완벽 정리

---

1. 스택이란?

스택은 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조입니다.
쉽게 말해, 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조(LIFO, Last In First Out) 입니다.

---

2. 왜 쓰는가?

• 함수 호출 기록 저장 (호출 스택)
• 괄호 검사, 수식 계산
• 뒤로 가기 기능 등
• 재귀 알고리즘의 내부 동작 원리 이해에 도움

---

3. 스택 기본 동작

• Push: 스택에 데이터를 넣는다.
• Pop: 스택에서 가장 최근에 들어온 데이터를 꺼낸다.
• Peek (또는 Top): 스택의 가장 위에 있는 데이터를 확인한다.
• isEmpty: 스택이 비었는지 확인한다.

---

4. 예시: 파이썬 리스트로 스택 구현

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()  # 리스트 끝에서 데이터 꺼냄
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]  # 가장 위 데이터 확인
        return None

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

# 사용 예시
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.peek())  # 20
print(stack.pop())   # 20
print(stack.pop())   # 10
print(stack.pop())   # None (비어있음)

---

5. 스택의 시간복잡도

• Push, Pop, Peek 모두 O(1) (상수 시간)
• 빠르고 효율적인 자료구조

---

6. 스택의 응용 예시

• 괄호 검사: 수식이나 코드 내 괄호가 제대로 열리고 닫혔는지 확인
• 후위 표기법 계산기: 수학 수식을 후위 표기법으로 변환하고 계산
• 웹 브라우저 뒤로가기: 방문 기록 저장 및 이전 페이지 이동
• 재귀 함수 내부 동작: 함수 호출 기록 저장

---

7. 예시: 괄호 검사 파이썬 코드

def is_balanced_parentheses(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)  # 여는 괄호는 push
        elif char == ')':
            if not stack:
                return False  # 닫는 괄호인데 스택이 비어있으면 불균형
            stack.pop()  # 스택에서 여는 괄호 pop

    return len(stack) == 0  # 스택이 비어있으면 균형

# 테스트
print(is_balanced_parentheses("((()))"))  # True
print(is_balanced_parentheses("(()"))     # False
print(is_balanced_parentheses("())"))     # False

---

8. 정리

특징	설명
구조	LIFO (Last In First Out) 구조
기본 연산	Push, Pop, Peek, isEmpty
시간복잡도	모든 연산 O(1)
주요 응용	괄호 검사, 재귀 호출, 후위 표기법 계산, 브라우저 뒤로가기

스택 응용 완벽 정리

---

1. 괄호 검사 확장 (모든 종류 괄호 처리)

스택을 활용해 (), {}, [] 같은 모든 괄호가 올바르게 짝을 이루는지 검사할 수 있습니다.

def is_balanced_all_parentheses(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in '({[':
            stack.append(char)  # 여는 괄호는 push
        elif char in ')}]':
            if not stack or stack[-1] != pairs[char]:
                return False  # 짝이 맞지 않음
            stack.pop()  # 올바른 짝이면 pop

    return len(stack) == 0

# 테스트
print(is_balanced_all_parentheses("{[()]}"))  # True
print(is_balanced_all_parentheses("{[(])}"))  # False
print(is_balanced_all_parentheses("((()))"))  # True

---

2. 후위 표기법 계산기 (스택으로 수식 계산)

중위 표기법(일반적인 수식)을 후위 표기법으로 변환하거나, 후위 표기법을 스택으로 계산하는 대표 예제입니다.

def eval_postfix(expression):
    stack = []
    for token in expression.split():
        if token.isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)
    return stack.pop()

# 테스트: 후위 표기법 "3 4 + 2 * 7 /"
print(eval_postfix("3 4 + 2 * 7 /"))  # 결과: 2.0

---

3. 웹 브라우저 뒤로가기 기능 구현

방문한 페이지를 스택에 쌓았다가, 뒤로가기 시 pop 하는 간단한 예시입니다.

class BrowserHistory:
    def __init__(self):
        self.history = []

    def visit(self, url):
        self.history.append(url)  # 방문 기록 저장

    def back(self):
        if len(self.history) > 1:
            self.history.pop()  # 현재 페이지 제거하고 이전 페이지로
            return self.history[-1]
        return None

# 사용 예시
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("naver.com")
print(browser.back())  # naver.com 방문 후 back -> google.com
print(browser.back())  # google.com 방문 후 back -> None (이전 기록 없음)

---

4. 재귀 함수 호출 내부 원리 이해

재귀 함수가 호출될 때마다 스택 프레임이 쌓이고, 종료 후 하나씩 꺼내지는 과정은 스택 구조로 설명할 수 있습니다.

예를 들어, 팩토리얼 함수는 다음과 같이 동작합니다:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(4))  # 24

함수가 호출될 때마다 factorial(4) → factorial(3) → factorial(2) → ... 스택에 쌓였다가, 종료되면서 계산 결과가 차례로 반환됩니다.

---

5. 요약 및 정리

응용 분야	설명	핵심 아이디어
괄호 검사 (모든 괄호 종류)	스택에 여는 괄호 저장 후 닫는 괄호 확인	짝 맞는지 확인하며 pop
후위 표기법 계산	연산자 나오면 스택에서 두 숫자 꺼내 계산 후 다시 push	LIFO 구조로 수식 계산
웹 브라우저 뒤로가기	방문 기록 스택에 저장, 뒤로가기 시 pop	최신 기록부터 꺼냄
재귀 함수 호출	함수 호출 시 스택 프레임 쌓임	스택으로 재귀 동작 구현