python - 스택(Stack) 자료구조

1. 스택의 개념

• 스택(Stack): 선형 자료구조, LIFO(Last In, First Out) 방식으로 작동.
  • 가장 나중에 삽입된 데이터가 가장 먼저 제거됨. (예: 접시 쌓기)

---

2. 스택의 특징

1. LIFO 구조 : 마지막 들어간 데이터가 가장 먼저 나옴.
2. 주요 연산 :
   • push: 데이터를 스택의 맨 위에 추가.
   • pop: 스택의 맨 위 데이터를 제거하고 반환.
   • peek (또는 top): 스택의 맨 위 데이터를 제거하지 않고 확인.
   • is_empty: 스택이 비어 있는지 확인.
3. 실제 구현 :
   • 리스트를 사용하여 스택을 구현하거나, collections.deque를 사용하여 더 효율적인 스택을 구현할 수 있다.

---

3. 스택의 구현 방법

(1) 리스트를 이용한 스택

• Python의 리스트는 기본적으로 스택처럼 사용할 수 있음.

# 스택 구현
stack = []

# push: 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)
print("스택 상태:", stack)  # [1, 2, 3]

# pop: 데이터 제거
top = stack.pop()
print("제거된 데이터:", top)  # 3
print("스택 상태:", stack)  # [1, 2]

# peek: 맨 위 데이터 확인
top = stack[-1]
print("맨 위 데이터:", top)  # 2

# is_empty: 스택이 비어 있는지 확인
is_empty = len(stack) == 0
print("스택이 비어 있나요?", is_empty)  # False

(2) collecttions.deque를 이용한 스택

• 리스트는 동적 배열 기반이므로, 크기가 커질수록 append와 pop의 성능이 느려질 수 있다.
• deque는 양방향 큐로 구현되어 있어 더 빠르게 동작한다.

from collections import deque

# 스택 구현
stack = deque()

# push: 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)
print("스택 상태:", stack)  # deque([1, 2, 3])

# pop: 데이터 제거
top = stack.pop()
print("제거된 데이터:", top)  # 3
print("스택 상태:", stack)  # deque([1, 2])

# peek: 맨 위 데이터 확인
top = stack[-1]
print("맨 위 데이터:", top)  # 2

# is_empty: 스택이 비어 있는지 확인
is_empty = len(stack) == 0
print("스택이 비어 있나요?", is_empty)  # False

---

4. 스택의 활용

(1) 괄호 짝 검사

• 문자열의 괄호가 올바른지 확인.
• 스택을 사용하여 여는 괄호를 저장하고, 닫는 괄호가 나왔을 때 매칭되는 여는 괄호를 제거

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

    for char in s:
        if char in mapping.values():  # 여는 괄호
            stack.append(char)
        elif char in mapping.keys():  # 닫는 괄호
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()  # 매칭되는 여는 괄호 제거
    return not stack

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

 

(2) 문자열 뒤집기

def reverse_string(s):
    stack = []
    for char in s:
        stack.append(char)

    reversed_str = ""
    while stack:
        reversed_str += stack.pop()
    return reversed_str

# 테스트
print(reverse_string("hello"))  # "olleh"

 

(3) DFS(깊이 우선 탐색)

• 스택은 그래프 탐색에서 DFS 구현할 때 사용된다.

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

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")  # 방문 순서 출력
            stack.extend(graph[node])  # 이웃 노드 추가

# 그래프 인접 리스트
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

dfs(graph, 1)  # 출력: 1 3 2 5 4

 

---

5. 스택의 장단점

장점

• 간단한 구현: Python 리스트나 deque로 간단히 구현 가능.
• 다양한 활용: 괄호 검사, 문자열 처리, DFS 등 다양한 문제 해결 가능.
• 빠른 데이터 접근: 맨 위 데이터(peek) 접근이 O(1).

단점

• 순차적 접근: 특정 데이터에 접근하려면 스택을 모두 순회해야 함.
• 제한된 구조: LIFO 방식으로 인해 일부 문제에는 적합하지 않음.

---

6. 실습 문제

문제 1: 히스토그램에서 가장 큰 직사각형

• 문제 : 히스토그램의 막대 높이가 주어질 때, 가장 큰 직사각형의 면적을 구하시오.
• 풀이 : 스택을 사용하여 효율적으로 최대 면적 계산.

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    heights.append(0)  # 끝부분에 0을 추가해 모든 높이를 처리

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

# 테스트
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))  # 출력: 10