[자료구조/Python] 파이썬으로 구현하고 활용하는 스택(Stack) 자료구조

스택(stack) 자료구조란?

스택은 후입선출(LIFO, Last-In-First-Out) 원칙에 따라 데이터를 쌓고, 가장 최근에 쌓인 데이터가 가장 먼저 처리되는 자료구조입니다. 주로 함수 호출과 관련된 작업, 괄호 검사, 뒤로 가기 등의 기능을 구현할 때 유용하게 사용됩니다.

스택은 기본적으로 두 가지 주요 동작을 수행합니다:

• push: 스택에 데이터를 쌓는 동작입니다. 가장 최근에 쌓인 데이터가 스택의 가장 위에 위치합니다.
• pop: 스택에서 가장 위에 있는 데이터를 가져오고 제거하는 동작입니다.

파이썬으로 스택 구현하기

파이썬에서 스택을 구현하는 방법은 간단합니다. 리스트(List)를 사용하여 스택을 구현할 수 있습니다. 파이썬 리스트는 동적 배열로 크기가 자동으로 조정되므로 스택으로 사용하기에 적합합니다.

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def size(self):
        return len(self.items)

스택 활용

1. 괄호 검사

프로그래머스나 백준에 가면 유사 문제가 다양하니, 풀어보시는 것을 추천합니다!

def is_balanced(expression):
    stack = Stack()
    opening_brackets = '([{'
    closing_brackets = ')]}'
    
    for char in expression:
        if char in opening_brackets:
            stack.push(char)
        elif char in closing_brackets:
            if stack.is_empty() or closing_brackets.index(char) != opening_brackets.index(stack.pop()):
                return False
    
    return stack.is_empty()

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

2. 함수 호출과 백트래킹

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))  # 출력: 120