[Python] 알고리즘 개념7 - 스택(Stack)

 

 

🚀 1. 스택(Stack)이란?

**스택(Stack)**은 데이터를 차곡차곡 쌓아 올리는 구조로, LIFO(Last In, First Out, 후입선출) 원칙을 따르는 자료구조입니다.
➡ 즉, 가장 나중에 추가된 데이터가 가장 먼저 제거되는 구조입니다.
 
💡 스택의 특징

• 후입선출(LIFO): 마지막에 들어온 데이터가 가장 먼저 나감
• 한쪽 끝에서만 데이터 추가(push)와 삭제(pop)가 이루어짐
• 재귀 호출, 괄호 검사, 실행 취소(Undo) 기능 등에 활용

 
📌 스택의 예시

• 웹 브라우저의 뒤로 가기(Back) 버튼: 최근 방문한 페이지부터 먼저 나옴
• 텍스트 편집기의 실행 취소(Undo) 기능: 가장 최근의 작업부터 차례대로 취소
• 함수 호출 스택: 현재 실행 중인 함수가 종료되면, 마지막 호출된 함수부터 반환됨

➡ 스택은 다양한 프로그래밍 문제에서 유용하게 사용됩니다.

---

 

 

🚀 2. 스택의 동작 원리

스택은 push(추가)와 pop(제거) 연산을 사용하여 데이터를 관리합니다.
 
연산 설명

push(item)	스택의 맨 위에 새로운 요소 추가
pop()	스택의 맨 위 요소 제거 후 반환
peek()	스택의 맨 위 요소를 확인(제거하지 않음)
is_empty()	스택이 비어 있는지 확인

💡 스택은 데이터를 추가하고 제거하는 방식이 제한적이지만, 이러한 제한이 특정 문제를 해결하는 데 유용하게 작용합니다.
➡ 스택은 리스트(List) 또는 collections.deque를 사용하여 구현할 수 있습니다.

---

 

 

🚀 3. 스택 구현하기

 

✅ 리스트(List)로 스택 구현 (비추천)

Python의 리스트를 이용하여 스택을 구현할 수 있지만, 크기가 커질수록 성능 저하 가능성이 있습니다.

stack = []

# 데이터 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # 출력: [1, 2, 3]

# 데이터 제거 (pop)
print(stack.pop())  # 출력: 3
print(stack.pop())  # 출력: 2
print(stack)  # 출력: [1]

 
💡 리스트는 동적 배열이므로 크기가 증가하면 새로운 메모리를 할당하는 과정이 필요하여 속도가 저하될 수 있습니다.
➡ 대안으로 collections.deque를 사용하면 성능을 더 최적화할 수 있습니다.

---

 

 

✅ collections.deque로 스택 구현 (추천)

collections.deque는 Python에서 제공하는 양방향 큐(double-ended queue) 자료구조로, 리스트보다 스택 연산에 더 최적화되어 있습니다.

from collections import deque

stack = deque()

# 데이터 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # 출력: deque([1, 2, 3])

# 데이터 제거 (pop)
print(stack.pop())  # 출력: 3
print(stack.pop())  # 출력: 2
print(stack)  # 출력: deque([1])

 
💡 deque는 리스트보다 빠르고, 메모리 효율성이 좋습니다.
➡ 스택 연산을 효율적으로 수행하려면 collections.deque를 사용하는 것이 좋습니다.

---

 

 

🚀 4. 스택의 활용 예제

 

✅ 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)
    return not stack

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

💡 스택을 사용하여 괄호가 올바르게 닫혀 있는지 효율적으로 검사할 수 있습니다.
➡ 이 방식은 LIFO 원칙을 활용하여 쉽게 구현할 수 있습니다.

---

 

 

✅ 2) 뒤집기 문제 (Reverse String)

📌 문제: 주어진 문자열을 스택을 사용하여 뒤집어 보세요.

def reverse_string(s):
    stack = list(s)
    reversed_str = ""
    while stack:
        reversed_str += stack.pop()
    return reversed_str

# 테스트
print(reverse_string("hello"))  # 출력: "olleh"

💡 스택의 LIFO 특성을 활용하여 문자열을 쉽게 뒤집을 수 있습니다.
➡ 한 글자씩 스택에 저장한 후, pop()을 사용하여 역순으로 재조합하면 쉽게 뒤집을 수 있습니다.

---

 

 

✅ 마무리 정리

• **스택(Stack)**은 LIFO(Last In, First Out, 후입선출) 방식으로 동작하는 자료구조입니다.
• 주요 연산: push(추가), pop(제거), peek(확인), is_empty(비어있는지 확인)
• 스택 구현 방법:
  • 리스트(list.append(), list.pop()) 사용 가능하지만 비효율적일 수 있음
  • collections.deque를 사용하면 더 효율적인 스택 구현 가능
• 스택 활용 예제:
  • 올바른 괄호 검사(Valid Parentheses)
  • 문자열 뒤집기(Reverse String)
  • 웹 브라우저 뒤로 가기(Back Button), 실행 취소(Undo) 기능 등