Stack - 자료구조의 기본 중 기본

스택은 Last In, First Out (LIFO) 구조

마지막에 넣은 데이터가 가장 먼저 나온다

쉽게 생각해서 책 더미라고 보면 됨.
계속 책을 쌓다가 가장 위에 있는 책부터 꺼내는 구조

Stack의 기본 연산

• push(x) : 스택 위에 데이터를 넣는다
• pop() : 스택 위에서 데이터를 꺼낸다
• peek() 또는 top() : 맨 위에 있는 데이터 확인 (제거 X)
• is_empty(): 스택이 비어 있는지 확인

스택은 언제 쓸까?

• 재귀 호출 추적 (함수 호출 스택)
  → 프로세스가 함수를 호출할 때마다 호출 정보를 스택에 저장
• 웹 브라우저 뒤로 가기
  → 방문한 페이지를 스택에 쌓고, pop()하면 이전 페이지로 이동
• 문자열 괄호 짝 검사
  → 여는 괄호는 push(), 닫는 괄호는 pop()하며 짝이 맞는지 확인
• DFS(깊이 우선 탐색)
  → 재귀적으로 내려갈 때마다 스택처럼 호출 정보 쌓음

예제 코드

괄호 유효성 검사 (Python)

def is_valid_parentheses(s):
    stack = []
    for ch in s:
        if ch == '(':
            stack.append(ch)
        elif ch == ')':
            if not stack:
                return False
            stack.pop()
    return not stack  # 스택이 비어 있어야 유효한 괄호 문자열

print(is_valid_parentheses("(())()"))  # True
print(is_valid_parentheses("(()"))     # False

다음에 알아 볼 큐(Queue)와 미리 비교를 해보자