Colin's Blog
[파이썬] 스택 (Stacks)의 개념과 구현

스택은 컴퓨터 과학에서 널리 사용되는 데이터 구조 중 하나입니다. 스택은 후입선출 (Last-In, First-Out) 원칙에 따라 동작하는 추상 자료형입니다. 이는 마지막으로 삽입한 요소가 먼저 삭제되고, 마지막에 삭제한 요소는 다시 접근할 수 없다는 것을 의미합니다. 스택은 함수 호출, 재귀 알고리즘, 브라우저의 뒤로 가기 등에 유용하게 사용됩니다.

스택의 개념

스택은 일렬로 정렬된 요소들을 저장하는 컨테이너로 생각할 수 있습니다. 요소를 추가할 때는 스택의 맨 위에 삽입되며(push), 요소를 삭제할 때는 맨 위의 요소가 제거됩니다(pop).

스택의 주요 동작은 다음과 같습니다:

파이썬으로 스택 구현하기

파이썬에서는 스택을 구현하기 위해 리스트나 데크(deque) 자료구조를 사용할 수 있습니다. 여기에서는 리스트를 사용하여 스택을 구현하는 예제를 살펴보겠습니다.

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, item):
        self.stack.append(item)
    
    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
    
    def peek(self):
        if not self.isEmpty():
            return self.stack[-1]
    
    def isEmpty(self):
        return len(self.stack) == 0

위의 코드에서 Stack 클래스는 내부적으로 리스트를 저장하는 stack 변수를 가지고 있습니다. push 메서드는 리스트의 append 메서드를 사용하여 요소를 스택의 맨 끝에 추가합니다. pop 메서드는 리스트의 pop 메서드를 사용하여 스택의 맨 끝 요소를 제거하고 반환합니다. peek 메서드는 리스트의 인덱스 -1을 사용하여 맨 끝 요소를 반환하며, isEmpty 메서드는 리스트 길이가 0인지 확인하여 스택이 비어있는지 여부를 반환합니다.

스택의 활용 예제

스택은 다양한 상황에서 유용하게 사용될 수 있습니다. 예를 들어, 괄호의 짝을 검사하는 문제는 스택을 사용하여 해결할 수 있습니다. 다음은 스택을 활용하여 괄호의 짝을 검사하는 예제 코드입니다.

def check_brackets(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.isEmpty() or opening_brackets.index(stack.pop()) != closing_brackets.index(char):
                return False
    
    return stack.isEmpty()

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

위의 코드에서 check_brackets 함수는 주어진 표현식에 있는 괄호가 올바르게 열고 닫혀있는지 검사합니다. opening_brackets와 closing_brackets 변수는 각각 열린 괄호와 닫힌 괄호를 저장하는 리스트입니다. 표현식을 한 글자씩 읽어오면서 열린 괄호는 스택에 push하고, 닫힌 괄호는 스택에서 pop하여 짝을 검사합니다. 만약 스택이 비어있거나 짝이 맞지 않는 괄호가 나온다면 False를 반환합니다. 마지막으로 스택이 비어있는지 여부를 확인하여 모든 괄호의 짝이 맞는지를 검사합니다.

스택은 이 외에도 여러 가지 상황에서 유용하게 사용되며, 다양한 알고리즘 및 자료구조의 구현에서도 핵심적인 역할을 합니다. 스택을 잘 이해하고 활용하는 것은 프로그래밍 실력 향상에 도움이 될 것입니다.

스택에 대한 개념과 파이썬에서의 구현 방법에 대해 알아보았습니다. 스택을 활용하여 다양한 문제를 해결할 수 있으니, 다음에는 여러분들이 스택을 사용하여 어떤 문제를 해결하는지 기대해봅니다!

© 2018 Colin. All rights reserved.