Python: Как использовать стек в программировании

Стек в Python — это структура данных, которая работает по принципу "последний вошел — первый вышел" (Last-In-First-Out или LIFO). Она представляет собой упорядоченный набор элементов, где новые элементы добавляются только на один конец (вершину стека), а удаление происходит также с этого же конца.

Вот пример использования стека в Python:

stack = []

# Добавляем элементы в стек
stack.append(1)
stack.append(2)
stack.append(3)

# Удаляем элемент из стека (в данном случае 3)
removed_element = stack.pop()

print(removed_element)  # Выводит: 3

Что такое стек в Python?

Стек в Python — это структура данных, которая работает по принципу LIFO (Last In, First Out). Это означает, что последний элемент, добавленный в стек, будет первым, который будет удален.

Основные операции со стеком

Стек поддерживает следующие основные операции:

• push(item): добавляет элемент на верхушку стека.
• pop(): удаляет и возвращает элемент с верхушки стека.
• top(): возвращает элемент с верхушки стека без удаления.
• is_empty(): проверяет, пуст ли стек.
• size(): возвращает количество элементов в стеке.

Пример использования стека в Python

Давайте рассмотрим примеры использования стека в Python.

Пример 1: Обратная польская запись

Одним из распространенных применений стека является вычисление математических выражений в обратной польской записи. Вот пример:

def evaluate_postfix(expression):
    stack = []
    operators = {'+': lambda x, y: x + y, '-': lambda x, y: x - y, '*': lambda x, y: x * y, '/': lambda x, y: x / y}
    
    for token in expression:
        if token.isdigit():
            stack.append(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            result = operators[token](operand1, operand2)
            stack.append(result)
    
    return stack.pop()

expression = ['2', '3', '+', '4', '*']
result = evaluate_postfix(expression)
print(result)  # Output: 20
    

Пример 2: Проверка сбалансированности скобок

С помощью стека можно проверить, является ли строка сбалансированной в отношении скобок. Например:

def is_balanced(expression):
    stack = []
    opening_brackets = ['(', '[', '{']
    closing_brackets = [')', ']', '}']
    
    for char in expression:
        if char in opening_brackets:
            stack.append(char)
        elif char in closing_brackets:
            if len(stack) == 0:
                return False
            last_opening_bracket = stack.pop()
            if opening_brackets.index(last_opening_bracket) != closing_brackets.index(char):
                return False
    
    return len(stack) == 0

expression = '[{()}]'
print(is_balanced(expression))  # Output: True

expression = '({[)}]'
print(is_balanced(expression))  # Output: False
    

Заключение

Стек представляет собой важную структуру данных в Python. Он позволяет эффективно управлять элементами, добавляемыми и удаляемыми в определенном порядке. В этой статье мы рассмотрели основные операции со стеком и привели примеры его использования для вычисления обратной польской записи и проверки сбалансированности скобок.