Приведи пример стека

Стек (Stack) в Python: определение и примеры

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

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

• push() — добавить элемент на вершину стека
• pop() — удалить и вернуть элемент с вершины
• peek() — посмотреть верхний элемент без удаления
• isEmpty() — проверить, пуст ли стек
• size() — получить количество элементов

Пример 1: Реализация стека на базе списка

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Добавить элемент на вершину стека"""
        self.items.append(item)
    
    def pop(self):
        """Удалить и вернуть верхний элемент"""
        if not self.is_empty():
            return self.items.pop()
        return None
    
    def peek(self):
        """Посмотреть верхний элемент без удаления"""
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        """Проверить, пуст ли стек"""
        return len(self.items) == 0
    
    def size(self):
        """Получить размер стека"""
        return len(self.items)
    
    def __str__(self):
        return str(self.items)

# Использование
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print(f"Стек: {stack}")  # [1, 2, 3]
print(f"Верхний элемент: {stack.peek()}")  # 3
print(f"Размер: {stack.size()}")  # 3

print(f"Удален: {stack.pop()}")  # 3
print(f"Удален: {stack.pop()}")  # 2
print(f"Стек: {stack}")  # [1]

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

Python списки имеют методы append() и pop(), которые работают как push/pop:

stack = []

# push — добавить элемент
stack.append("a")
stack.append("b")
stack.append("c")

print(stack)  # ['a', 'b', 'c']

# pop — удалить верхний элемент
print(stack.pop())  # 'c'
print(stack.pop())  # 'b'
print(stack)  # ['a']

# peek — посмотреть верхний элемент
if stack:
    print(stack[-1])  # 'a'

Пример 3: Проверка сбалансированности скобок (классическая задача)

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop() if not self.is_empty() else None
    
    def is_empty(self):
        return len(self.items) == 0

def is_balanced(expression):
    """Проверить, сбалансированы ли скобки"""
    stack = Stack()
    opening = {"(", "[", "{"}
    closing = {")": "(", "]": "[", "}": "{"}
    
    for char in expression:
        if char in opening:
            stack.push(char)
        elif char in closing:
            if stack.is_empty() or stack.pop() != closing[char]:
                return False
    
    return stack.is_empty()

# Примеры
print(is_balanced("(())"))      # True
print(is_balanced("([{}])"))    # True
print(is_balanced("([)]"))      # False
print(is_balanced("((("))       # False
print(is_balanced("())"))       # False

Пример 4: Реверс строки с использованием стека

def reverse_string(s):
    """Развернуть строку используя стек"""
    stack = []
    
    # Пушим каждый символ
    for char in s:
        stack.append(char)
    
    # Попим в обратном порядке
    reversed_str = ""
    while stack:
        reversed_str += stack.pop()
    
    return reversed_str

print(reverse_string("hello"))   # olleh
print(reverse_string("python"))  # nohtyp

Пример 5: Обход истории браузера (назад/вперед)

class BrowserHistory:
    def __init__(self, homepage):
        self.back_stack = []  # История для кнопки "Назад"
        self.current = homepage
        self.forward_stack = []  # История для кнопки "Вперед"
    
    def visit(self, url):
        """Посетить новый сайт"""
        self.back_stack.append(self.current)
        self.current = url
        self.forward_stack = []  # Очищаем будущее при новом визите
    
    def back(self):
        """Вернуться на предыдущую страницу"""
        if self.back_stack:
            self.forward_stack.append(self.current)
            self.current = self.back_stack.pop()
        return self.current
    
    def forward(self):
        """Вперед на следующую страницу"""
        if self.forward_stack:
            self.back_stack.append(self.current)
            self.current = self.forward_stack.pop()
        return self.current
    
    def get_current(self):
        return self.current

# Использование
browser = BrowserHistory("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.visit("stackoverflow.com")

print(f"Текущая: {browser.get_current()}")  # stackoverflow.com
print(f"Назад: {browser.back()}")  # github.com
print(f"Назад: {browser.back()}")  # youtube.com
print(f"Вперед: {browser.forward()}")  # github.com
print(f"Вперед: {browser.forward()}")  # stackoverflow.com

Пример 6: Система отмены операций (Undo/Redo)

class TextEditor:
    def __init__(self):
        self.text = ""
        self.undo_stack = []  # История для отмены
        self.redo_stack = []  # История для повтора
    
    def type_text(self, new_text):
        """Добавить текст"""
        self.undo_stack.append(self.text)
        self.text += new_text
        self.redo_stack = []  # Очищаем redo при новом действии
        print(f"Текст: {self.text}")
    
    def undo(self):
        """Отменить последнее действие"""
        if self.undo_stack:
            self.redo_stack.append(self.text)
            self.text = self.undo_stack.pop()
            print(f"После отмены: {self.text}")
    
    def redo(self):
        """Повторить отмененное действие"""
        if self.redo_stack:
            self.undo_stack.append(self.text)
            self.text = self.redo_stack.pop()
            print(f"После повтора: {self.text}")

# Использование
editor = TextEditor()
editor.type_text("Hello")  # Hello
editor.type_text(" World")  # Hello World
editor.undo()  # Hello
editor.undo()  # 
editor.redo()  # Hello
editor.redo()  # Hello World

Пример 7: Вычисление выражений в обратной польской нотации

def evaluate_rpn(tokens):
    """Вычислить выражение в обратной польской нотации
    Пример: ["2", "1", "+", "3", "*"] → 9 (то есть (2+1)*3)
    """
    stack = []
    operators = {"+", "-", "*", "/"}
    
    for token in tokens:
        if token in operators:
            # Вычисляем операцию с двумя верхними элементами
            b = stack.pop()
            a = stack.pop()
            
            if token == "+":
                result = a + b
            elif token == "-":
                result = a - b
            elif token == "*":
                result = a * b
            elif token == "/":
                result = int(a / b)
            
            stack.append(result)
        else:
            # Число
            stack.append(int(token))
    
    return stack[0]

print(evaluate_rpn(["2", "1", "+", "3", "*"]))  # 9
print(evaluate_rpn(["4", "13", "5", "/", "+"]))  # 6
print(evaluate_rpn(["10", "6", "9", "3", "/", "/", "-", "2", "*", "2", "+", "*"]))  # 36

Пример 8: Использование модуля collections.deque (оптимизированный стек)

from collections import deque

stack = deque()

# push
stack.append(1)
stack.append(2)
stack.append(3)

# pop (очень эффективно)
print(stack.pop())  # 3
print(stack.pop())  # 2

# peek
if stack:
    print(stack[-1])  # 1

print(len(stack))  # 1

Сложность операций

Операция     | Сложность
------------ | ---------
push()       | O(1)
pop()        | O(1)
peek()       | O(1)
is_empty()   | O(1)
size()       | O(1)
поиск элемента | O(n)

Практическое применение стеков

• Парсинг выражений — проверка скобок, вычисление RPN
• Отмена операций — undo/redo в редакторах
• Навигация — история браузера, back button
• Вызовы функций — call stack в интерпретаторе
• Обход графов — DFS (глубинный поиск)
• Обработка JSON — парсинг вложенных структур

Вывод

Стек — фундаментальная структура данных, которая использует принцип LIFO. Python предоставляет несколько способов реализации стека: от простых списков до оптимизированного deque. Понимание стеков критически важно для решения задач по парсингу, отмене операций и навигации.