Native Python Programing

파이썬 스택(Stack) 자료구조 개요

스택(Stack)은 후입선출(LIFO, Last-In-First-Out) 방식으로 작동하는 자료구조입니다. 즉, 가장 최근에 추가된 요소가 가장 먼저 제거됩니다. 파이썬에서는 리스트(list)를 이용하여 스택을 쉽게 구현할 수 있으며, append() 메서드를 이용해 요소를 추가하고 pop() 메서드를 이용해 요소를 제거합니다.

예를 들어:

stack = []
stack.append(1)  # 스택에 1 추가
stack.append(2)  # 스택에 2 추가
stack.pop()      # 마지막으로 추가한 2 제거

이 코드에서 stack.pop()을 실행하면 2가 제거되고, 스택에는 [1]만 남습니다.

스택의 실무 활용 예시

스택 자료구조는 다양한 실무 분야에서 활용됩니다. 몇 가지 대표적인 예시는 다음과 같습니다.

1. 웹 브라우저 뒤로가기 기능

• 브라우저에서 사용자가 여러 페이지를 이동할 때 방문한 페이지들을 스택에 저장해둡니다.
• "뒤로가기" 버튼을 누를 때마다 마지막에 방문한 페이지가 스택에서 제거되며, 이전 페이지로 돌아가게 됩니다.

2. 재귀 함수 호출 관리

• 재귀 함수 호출 과정에서도 스택이 사용됩니다.
• 파이썬은 내부적으로 호출된 함수들을 스택에 저장하여 순차적으로 실행하고 복귀합니다.

3. 문자열 역순 출력

• 문자열을 거꾸로 출력하는 작업에서도 스택을 이용할 수 있습니다.
• 문자열의 각 문자를 스택에 하나씩 넣고, 스택에서 꺼내면 문자의 순서가 뒤집히게 됩니다.

4. 괄호의 유효성 검사

• 코드에서 괄호가 올바르게 닫혔는지 확인하는 데 스택이 사용됩니다.
• 여는 괄호를 스택에 추가하고, 닫는 괄호가 나오면 스택에서 여는 괄호를 제거하여 올바른 쌍을 이루는지 확인하는 방식입니다.

예를 들어 괄호 유효성을 체크하는 간단한 코드:

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("(]"))      # False

위 코드에서 괄호가 올바르게 닫히면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

5. 역폴란드 표기법 계산기

• 수식 계산 시에도 스택을 활용할 수 있습니다.
• 특히 역폴란드 표기법에서는 연산자 뒤에 피연산자가 오는 형태이므로, 스택을 이용해 피연산자를 쌓아가며 계산합니다.

이와 같이 스택은 데이터의 순서와 관계된 문제를 해결하는 데 매우 유용하게 사용됩니다.

스택(Stack)은 LIFO(Last In, First Out) 방식으로 작동하는 자료구조입니다. 즉, 가장 마지막에 추가된 요소가 가장 먼저 제거됩니다. 파이썬에서 기본적으로 제공하는 리스트(list)는 스택의 기능을 구현하는 데 적합한 자료구조입니다. 리스트를 상속하여 스택을 구현하면 리스트의 모든 기능을 활용하면서, 스택의 push, pop 기능을 쉽게 구현할 수 있습니다.

스택의 주요 동작:

1. push(item): 스택의 가장 위에 요소를 추가합니다.
2. pop(): 스택의 가장 위에 있는 요소를 제거하고 반환합니다.
3. peek(): 스택의 가장 위에 있는 요소를 제거하지 않고 반환합니다.
4. is_empty(): 스택이 비어 있는지 확인합니다.

파이썬 리스트를 상속한 스택 구현

class Stack(list):
    def __init__(self):
        super().__init__()  # 리스트 초기화

    def push(self, item):
        """스택에 요소를 추가"""
        self.append(item)  # 리스트의 append()를 사용해 스택의 push 기능 구현

    def pop(self):
        """스택의 가장 위에 있는 요소를 제거하고 반환"""
        if not self.is_empty():
            return super().pop()  # 리스트의 pop()을 사용해 스택의 pop 기능 구현
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        """스택의 가장 위에 있는 요소를 반환 (제거하지 않음)"""
        if not self.is_empty():
            return self[-1]  # 리스트의 마지막 요소를 반환
        else:
            raise IndexError("peek from empty stack")

    def is_empty(self):
        """스택이 비어 있는지 확인"""
        return len(self) == 0

    def size(self):
        """스택의 크기 반환"""
        return len(self)

# 스택 사용 예제
stack = Stack()

# 스택에 요소 추가 (push)
stack.push(10)
stack.push(20)
stack.push(30)

print("Current Stack:", stack)  # 출력: [10, 20, 30]

# 스택의 가장 위 요소 확인 (peek)
top = stack.peek()
print("Top element:", top)  # 출력: 30

# 스택에서 요소 제거 (pop)
popped = stack.pop()
print("Popped element:", popped)  # 출력: 30

# 스택 상태 확인
print("Stack after pop:", stack)  # 출력: [10, 20]

# 스택이 비어 있는지 확인
print("Is stack empty?", stack.is_empty())  # 출력: False

# 스택 크기 확인
print("Stack size:", stack.size())  # 출력: 2

예제 설명:

1. push(item): 리스트의 append() 메서드를 사용하여 스택의 맨 위에 요소를 추가합니다.
2. pop(): 리스트의 pop() 메서드를 사용하여 스택의 맨 위 요소를 제거하고 반환합니다. 스택이 비어 있으면 IndexError를 발생시킵니다.
3. peek(): 리스트의 마지막 요소(스택의 맨 위)를 반환하지만 제거하지 않습니다. 스택이 비어 있으면 IndexError를 발생시킵니다.
4. is_empty(): 스택이 비어 있는지 확인합니다.
5. size(): 스택에 있는 요소의 개수를 반환합니다.

출력 결과:

Current Stack: [10, 20, 30]
Top element: 30
Popped element: 30
Stack after pop: [10, 20]
Is stack empty? False
Stack size: 2

장점:

• 리스트 상속: 파이썬 리스트는 동적 배열로 동작하기 때문에, 추가적인 메모리 관리 없이 스택의 요소를 쉽게 추가하거나 제거할 수 있습니다.
• 단순 구현: 리스트의 기본 기능을 그대로 사용하면서, 스택의 동작을 간단하게 구현할 수 있습니다.

스택 사용 사례:

1. 수식의 괄호 검증: 수학 또는 프로그래밍 수식에서 괄호의 짝을 맞출 때 스택을 사용하여 유효성을 검증할 수 있습니다.
2. 재귀 호출의 관리: 재귀 호출 과정에서 함수 호출 스택을 관리하는데 스택 자료구조가 유용합니다.
3. Undo/Redo 기능: 텍스트 편집기와 같은 프로그램에서 이전 상태로 돌아가거나 다시 앞으로 이동할 때 스택을 사용합니다.

이와 같이 파이썬 리스트를 상속하여 스택 자료구조를 구현하면, 간단한 코드로 스택의 주요 기능을 쉽게 사용할 수 있습니다.