Chapter 4. 스택(Stack)

1. 스택이란? 🍽️

스택(Stack) 은 접시 쌓기처럼 나중에 들어온 데이터가 먼저 나가는 구조예요!

• 정의: LIFO (Last In First Out)
• 예시:
  • 웹 브라우저 뒤로가기 ⬅️
  • 편집기의 되돌리기 (Undo) ↩️
  • 함수 호출 스택 ⛓️

가장 최근에 쌓인 게 먼저 나간다!

---

2. 스택 구조와 연산 ⚙️

✅ 주요 연산

연산	설명
push(e)	요소 e를 스택에 추가
pop()	스택의 맨 위 요소를 꺼냄
peek()	삭제 없이 맨 위 확인
is_empty()	스택이 비었는지 확인
is_full()	스택이 꽉 찼는지 확인 (배열 스택인 경우)

 

🧱 구조 그림

[   ] ← 바닥
[ 30 ]
[ 20 ]
[ 10 ] ← top (가장 최근)

---

3. 스택 구현 예제 (Python) 🐍

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

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

    def pop(self):
        return self.stack.pop()

    def peek(self):
        return self.stack[-1] if self.stack else None

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

---

4. 스택의 응용 예제 💡

---

(1) 괄호 검사기 (){}[] ✅❌

올바른 괄호 쌍을 확인하는 프로그램

검사 조건:

1. 왼쪽 괄호 개수 = 오른쪽 괄호 개수
2. 괄호 짝은 순서대로 나와야 함
3. 서로 교차하지 않아야 함 ([ ( ] ) ❌)

✔️ 예시 코드:

def check_brackets(expr):
    stack = []
    for ch in expr:
        if ch in '({[':
            stack.append(ch)
        elif ch in ')}]':
            if not stack:
                return False
            top = stack.pop()
            if not ((top == '(' and ch == ')') or
                    (top == '[' and ch == ']') or
                    (top == '{' and ch == '}')):
                return False
    return not stack

🧪 테스트:

 

check_brackets("({[()]})")   # True
check_brackets("({[([)])}")  # False

---

(2) 수식 계산기 🧮

우리가 흔히 쓰는 중위표기법(2 + 3) 을 → 후위표기법(2 3 +) 으로 바꿔 계산!

📌 알고리즘 (후위표기 계산):

1. 숫자는 스택에 push
2. 연산자가 나오면 2개 pop해서 계산
3. 결과를 다시 push
4. 마지막 하나가 정답

✔️ 예시 코드:

def calc_postfix(expr):
    stack = []
    for token in expr:
        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[0]

🧪 테스트:

calc_postfix("23*4+")  # (2 * 3) + 4 = 10

---

(3) 미로 탐색 🧭

🔍 문제:

미로에서 출구를 찾는 알고리즘 — 가다가 막히면 가장 최근 갈림길로 되돌아감

✅ 사용 기술: DFS (깊이우선탐색) + 스택

• 가던 길이 막히면 pop 해서 뒤로 돌아감
• 갈 수 있는 길이 있으면 push

---

정리 📝

활용	설명
괄호 검사	스택에 괄호 저장해서 짝 맞추기
수식 계산	중위 → 후위 변환, 후위 계산
미로 탐색	DFS에서 되돌아갈 길 기억

 

---

마무리 멘트

스택은 알고 보면 정말 유용한 자료구조예요!
기본 원리는 단순하지만, 괄호 검사, 수식 계산, DFS 등
실제 소프트웨어 곳곳에서 사용됩니다.

"나중에 쌓은 걸 먼저 꺼낸다"는 원칙 하나로
복잡한 문제를 아주 깔끔하게 해결할 수 있어요!