Какие знаешь основные операции стека?

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

Стек (Stack) — это одна из фундаментальных структур данных в компьютерной науке. Это структура с принципом LIFO (Last In, First Out) — последний вошёл, первый вышел.

1. Push (Добавление элемента)

Добавляет элемент на вершину стека:

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Добавить элемент в стек"""
        self.items.append(item)
    
    def __repr__(self):
        return f"Stack({self.items})"

# Использование
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack)  # Stack([10, 20, 30])

Сложность: O(1) — константное время

2. Pop (Удаление элемента)

Удаляет и возвращает элемент с вершины стека:

class Stack:
    def __init__(self):
        self.items = []
    
    def pop(self):
        """Удалить и вернуть элемент со вершины"""
        if len(self.items) == 0:
            raise IndexError("pop from empty stack")
        return self.items.pop()

# Использование
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print(stack.pop())  # 30
print(stack.pop())  # 20
print(stack)        # Stack([10])

Сложность: O(1) — константное время

3. Peek (Просмотр верхнего элемента)

Возвращает элемент с вершины без его удаления:

class Stack:
    def __init__(self):
        self.items = []
    
    def peek(self):
        """Вернуть верхний элемент без удаления"""
        if len(self.items) == 0:
            raise IndexError("peek from empty stack")
        return self.items[-1]

# Использование
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print(stack.peek())  # 30 (элемент остался в стеке)
print(stack.peek())  # 30 (ещё раз возвращает 30)

Сложность: O(1) — константное время

4. IsEmpty (Проверка пустоты)

Проверяет, пуст ли стек:

class Stack:
    def __init__(self):
        self.items = []
    
    def is_empty(self):
        """Проверить, пуст ли стек"""
        return len(self.items) == 0
    
    def __len__(self):
        return len(self.items)

# Использование
stack = Stack()
print(stack.is_empty())  # True
stack.push(10)
print(stack.is_empty())  # False
print(len(stack))        # 1

Сложность: O(1) — константное время

5. Size (Размер стека)

Возвращает количество элементов в стеке:

class Stack:
    def __init__(self):
        self.items = []
    
    def size(self):
        """Вернуть размер стека"""
        return len(self.items)

# Использование
stack = Stack()
print(stack.size())  # 0
stack.push(10)
stack.push(20)
print(stack.size())  # 2

Сложность: O(1) — константное время

Полная реализация Stack

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Добавить элемент"""
        self.items.append(item)
    
    def pop(self):
        """Удалить и вернуть элемент"""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()
    
    def peek(self):
        """Просмотреть верхний элемент"""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]
    
    def is_empty(self):
        """Проверить пустоту"""
        return len(self.items) == 0
    
    def size(self):
        """Получить размер"""
        return len(self.items)
    
    def clear(self):
        """Очистить стек"""
        self.items.clear()
    
    def __str__(self):
        return f"Stack({self.items})"
    
    def __repr__(self):
        return self.__str__()

# Использование
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print(stack)          # Stack([10, 20, 30])
print(stack.size())   # 3
print(stack.peek())   # 30
print(stack.pop())    # 30
print(stack)          # Stack([10, 20])

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

1. Парные скобки (проверка правильности)

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

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

2. Обратная польская нотация (RPN)

def evaluate_rpn(tokens):
    """Вычислить выражение в обратной польской нотации"""
    stack = Stack()
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.push(a + b)
            elif token == '-':
                stack.push(a - b)
            elif token == '*':
                stack.push(a * b)
            elif token == '/':
                stack.push(a // b)
        else:
            stack.push(int(token))
    
    return stack.pop()

# Примеры
print(evaluate_rpn(["2", "1", "+", "3", "*"]))  # (2+1)*3 = 9
print(evaluate_rpn(["15", "7", "1", "1", "-", "-", "/", "3", "*", "2", "1", "1", "+", "+", "-"]))  # 5

3. Инверсия строки

def reverse_string(s):
    """Обратить строку используя стек"""
    stack = Stack()
    for char in s:
        stack.push(char)
    
    result = ""
    while not stack.is_empty():
        result += stack.pop()
    
    return result

# Использование
print(reverse_string("hello"))  # olleh
print(reverse_string("Python")) # nohtyP

4. Отмена операций (Undo)

class TextEditor:
    def __init__(self):
        self.text = ""
        self.undo_stack = Stack()
    
    def type(self, char):
        self.undo_stack.push(self.text)
        self.text += char
    
    def undo(self):
        if not self.undo_stack.is_empty():
            self.text = self.undo_stack.pop()
    
    def __str__(self):
        return self.text

# Использование
editor = TextEditor()
editor.type('H')
editor.type('e')
editor.type('l')
editor.type('l')
editor.type('o')
print(editor)  # Hello

editor.undo()
print(editor)  # Hell
editor.undo()
print(editor)  # Hel

5. История браузера (Back button)

class BrowserHistory:
    def __init__(self, homepage):
        self.current_page = homepage
        self.back_stack = Stack()
        self.forward_stack = Stack()
    
    def visit(self, url):
        self.back_stack.push(self.current_page)
        self.current_page = url
        self.forward_stack.clear()
    
    def back(self):
        if not self.back_stack.is_empty():
            self.forward_stack.push(self.current_page)
            self.current_page = self.back_stack.pop()
    
    def forward(self):
        if not self.forward_stack.is_empty():
            self.back_stack.push(self.current_page)
            self.current_page = self.forward_stack.pop()

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

print(browser.current_page)  # medium.com
browser.back()
print(browser.current_page)  # stackoverflow.com
browser.back()
print(browser.current_page)  # github.com
browser.forward()
print(browser.current_page)  # stackoverflow.com

6. Преобразование инфиксного в постфиксное

def infix_to_postfix(infix):
    """Преобразовать инфиксное выражение в постфиксное"""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = Stack()
    postfix = []
    
    for char in infix:
        if char.isdigit():
            postfix.append(char)
        elif char in precedence:
            while (not stack.is_empty() and 
                   stack.peek() in precedence and 
                   precedence[stack.peek()] >= precedence[char]):
                postfix.append(stack.pop())
            stack.push(char)
        elif char == '(':
            stack.push(char)
        elif char == ')':
            while stack.peek() != '(':
                postfix.append(stack.pop())
            stack.pop()  # Удалить '('
    
    while not stack.is_empty():
        postfix.append(stack.pop())
    
    return ' '.join(postfix)

# Использование
print(infix_to_postfix("2+3*4"))  # 2 3 4 * +
print(infix_to_postfix("(2+3)*4"))  # 2 3 + 4 *

Таблица сложности операций

Python встроенные структуры как стек

# Список как стек
stack = []
stack.append(10)    # push
stack.append(20)
stack.pop()         # pop -> 20
print(stack[-1])    # peek

# collections.deque как стек (более эффективно)
from collections import deque

stack = deque()
stack.append(10)    # O(1)
stack.pop()         # O(1)

# Встроенная очередь в asyncio
import asyncio
queue = asyncio.LifoQueue()  # LIFO = Stack

Выводы

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

1. Push — добавить элемент (O(1))
2. Pop — удалить и вернуть (O(1))
3. Peek — просмотреть верхний (O(1))
4. IsEmpty — проверить пустоту (O(1))
5. Size — получить размер (O(1))

Все операции выполняются за O(1) — очень быстро!

Применения:

• Проверка скобок
• Обратная польская нотация
• Отмена операций (Undo)
• История браузера
• Parsing выражений
• Глубина рекурсии