[TIL] 241205 스택(Stack) 자료구조

📚 TIL(Today I Learned): 스택(Stack) 자료구조와 활용

오늘은 스택(Stack) 자료구조를 공부했습니다. 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다. 즉, 가장 마지막에 추가된 데이터가 먼저 제거됩니다. 파이썬에서는 스택을 list나 collections.deque로 구현할 수 있습니다.

---

🛠️ 스택 기본 구현

1. 리스트를 사용한 스택

stack = []

# 삽입 (push)
stack.append(1)  # 스택에 1 추가
stack.append(2)  # 스택에 2 추가
stack.append(3)  # 스택에 3 추가

# 제거 (pop)
print(stack.pop())  # 스택에서 가장 위의 값(3) 제거 후 출력
print(stack.pop())  # 스택에서 가장 위의 값(2) 제거 후 출력
print(stack.pop())  # 스택에서 가장 위의 값(1) 제거 후 출력

 

2. deque를 사용한 스택

from collections import deque

# deque를 사용하여 스택 생성
stack = deque()

# 삽입 (push)
stack.append(1)  # 스택에 1 추가
stack.append(2)  # 스택에 2 추가
stack.append(3)  # 스택에 3 추가

# 제거 (pop)
print(stack.pop())  # 스택에서 가장 위의 값(3) 제거 후 출력
print(stack.pop())  # 스택에서 가장 위의 값(2) 제거 후 출력
print(stack.pop())  # 스택에서 가장 위의 값(1) 제거 후 출력

---

📌 스택 활용 예제

1. 괄호 유효성 검사

괄호가 올바르게 닫혔는지 확인하는 코드입니다.

def is_valid_parentheses(s):
    stack = []  # 괄호를 저장할 스택
    mapping = {')': '(', '}': '{', ']': '['}  # 닫는 괄호에 대응하는 여는 괄호를 매핑
    
    for char in s:
        if char in mapping:  # 닫는 괄호인 경우
            # 스택에서 top 요소를 꺼냄. 스택이 비어 있다면 '#'을 반환
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:  # 매핑이 일치하지 않으면 False 반환
                return False
        else:  # 여는 괄호인 경우
            stack.append(char)  # 스택에 추가
    
    # 스택이 비어 있으면 True, 남아 있으면 False
    return not stack

# 테스트
print(is_valid_parentheses("()[]{}"))  # True (모든 괄호가 올바르게 닫힘)
print(is_valid_parentheses("(]"))      # False (열린 괄호와 닫힌 괄호가 일치하지 않음)

 

2. DFS(깊이 우선 탐색)

스택을 사용해 DFS를 구현하는 예제입니다.

def dfs_stack(graph, start):
    visited = set()  # 방문한 노드를 기록할 집합
    stack = [start]  # 탐색을 시작할 스택, 초기 노드를 추가
    
    while stack:
        node = stack.pop()  # 스택에서 노드를 꺼냄
        if node not in visited:  # 방문하지 않은 노드인 경우
            visited.add(node)  # 노드를 방문 처리
            # 인접한 노드 중 방문하지 않은 노드를 스택에 추가
            stack.extend(graph[node] - visited)
    
    return visited  # 방문한 노드 집합 반환

# 그래프 정의 (인접 리스트)
graph = {
    1: {2, 3, 4},
    2: {1, 5},
    3: {1},
    4: {1},
    5: {2}
}

# 테스트
print(dfs_stack(graph, 1))  # {1, 2, 3, 4, 5} (1번 노드에서 시작해 모든 노드를 탐색)

---

오늘 배운 점

• 스택은 데이터를 쌓고 빼는 방식으로 동작하며, 최근 데이터 우선 처리가 필요한 문제에 적합하다.
• 괄호 검사, DFS 등 다양한 문제에서 스택을 활용할 수 있다.
• 파이썬의 list와 collections.deque를 사용하여 스택을 구현할 수 있다.