스택 (Stack) 자료구조

개요

스택(Stack)은 후입선출 (LIFO, Last-In First-Out) 구조를 따르는 자료구조입니다.
즉, 마지막에 추가된 요소가 가장 먼저 제거되는 방식으로 동작합니다.

스택은 메모리 관리, 재귀 함수 실행, 괄호 검사, 문자열 역순 출력, 백트래킹(Backtracking) 등 다양한 알고리즘에서 활용됩니다.
파이썬에서는 list 또는 collections.deque를 사용하여 스택을 구현할 수 있습니다.

---

스택의 특징

1. LIFO(Last-In, First-Out)

   • 가장 나중에 삽입된 데이터가 가장 먼저 제거됨.

2. 기본 연산

   • Push: 스택에 데이터를 삽입 ($O(1)$)

   • Pop: 스택에서 최상위(top) 데이터를 제거 및 반환 ($O(1)$)

   • Peek(Top): 스택의 최상위 데이터를 조회 (삭제 X) ($O(1)$)

   • isEmpty: 스택이 비어있는지 확인 ($O(1)$)

3. 메모리 구조

   • 스택은 연속된 메모리 공간을 사용하는 배열 기반 스택과, 동적 메모리 할당을 사용하는 연결 리스트 기반 스택으로 구현할 수 있음.

4. 활용 사례

   • 재귀 함수 호출 (Call Stack)

   • 괄호 검사 (Valid Parentheses)

   • 후위 표기법(Postfix Notation) 계산

   • 웹 브라우저의 뒤로 가기(Back) 기능

   • DFS(깊이 우선 탐색, Depth-First Search) 알고리즘

---

스택 연산 (Push, Pop, Peek)

파이썬에서는 list 또는 collections.deque를 사용하여 스택을 구현할 수 있습니다.

1. 리스트 (List) 사용

stack = []

# Push (삽입)
stack.append(10)
stack.append(20)
stack.append(30)

print(stack)  # [10, 20, 30]

# Pop (삭제)
print(stack.pop())  # 30
print(stack.pop())  # 20

# Peek (최상위 원소 조회)
print(stack[-1])  # 10

# 스택이 비었는지 확인
print(len(stack) == 0)  # False

• append() 연산: $O(1)$

• pop() 연산: $O(1)$

하지만, list.pop(0)처럼 리스트의 첫 번째 요소를 삭제하면 $O(n)$의 성능이 나오므로 비효율적입니다.

---

2. Deque 사용 (권장)

collections.deque는 양쪽에서 빠르게 삽입/삭제가 가능한 자료구조로, 리스트보다 스택 연산이 더 빠릅니다.

from collections import deque

stack = deque()

# Push (삽입)
stack.append(10)
stack.append(20)
stack.append(30)

# Pop (삭제)
print(stack.pop())  # 30
print(stack.pop())  # 20

# Peek (최상위 원소 조회)
print(stack[-1])  # 10

• deque.append() 연산: $O(1)$

• deque.pop() 연산: $O(1)$

➡️ **deque**를 사용하면 더 빠른 스택 연산을 수행할 수 있습니다.

---

스택의 활용 예제

1. 올바른 괄호 검사 (Valid Parentheses)

주어진 문자열이 올바른 괄호 ()[]{} 구조인지 확인하는 문제입니다.

def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:  # 닫는 괄호라면
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)  # 여는 괄호는 push

    return not stack  # 스택이 비어 있으면 True

print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("(]"))      # False

시간 복잡도: $O(n)$
공간 복잡도: $O(n)$ (스택 사용)

---

2. 문자열 뒤집기

스택을 사용하여 문자열을 뒤집을 수 있습니다.

def reverse_string(s):
    stack = list(s)
    reversed_s = ""

    while stack:
        reversed_s += stack.pop()

    return reversed_s

print(reverse_string("hello"))  # "olleh"

시간 복잡도: $O(n)$
공간 복잡도: $O(n)$ (스택 사용)

---

3. 후위 표기법 (Postfix Notation) 계산

수식을 후위 표기법으로 변환하여 계산하는 알고리즘입니다.

def evaluate_postfix(expression):
    stack = []

    for token in expression.split():
        if token.isdigit():  # 숫자면 push
            stack.append(int(token))
        else:  # 연산자면 pop 후 연산
            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()

expr = "3 4 + 2 * 7 /"
print(evaluate_postfix(expr))  # 2.0

시간 복잡도: $O(n)$
공간 복잡도: $O(n)$ (스택 사용)

---

4. DFS (깊이 우선 탐색)

DFS 알고리즘에서 스택을 활용할 수 있습니다.

def dfs(graph, start):
    stack = [start]
    visited = set()

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            stack.extend(graph[node])  # 연결된 노드 추가

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs(graph, 'A')  # A C F B E D

시간 복잡도: $O(V + E)$
공간 복잡도: $O(V)$ (스택 사용)

---

스택 vs 큐

특징	스택 (Stack)	큐 (Queue)
동작 방식	LIFO (후입선출)	FIFO (선입선출)
삽입 연산	push()	enqueue()
삭제 연산	pop()	dequeue()
예제	웹 브라우저 뒤로 가기, DFS	프로세스 스케줄링, BFS

---

결론

• 스택은 후입선출(LIFO) 구조를 가지며, $O(1)$ 시간 복잡도로 삽입/삭제가 가능합니다.

• list보다 collections.deque를 사용하면 성능이 더 좋습니다.

• 괄호 검사, 문자열 뒤집기, DFS 탐색, 후위 표기법 계산 등 다양한 문제에서 활용됩니다. 🚀