Стеки и очереди

Основные структуры данных

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

Стек (LIFO — Last In, First Out)

Принцип работы стека

Стек работает по принципу LIFO (Last In, First Out) — последний пришел, первый ушел. Основные операции:

Push — добавление элемента на вершину стека
Pop — удаление элемента с вершины стека
Peek — просмотр элемента на вершине без удаления

Push(5)

Pop() → 5

Визуализация операций Push и Pop в стеке

Реализация стека в Python

# Реализация стека с использованием списка
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)

# Пример использования
stack = Stack()
stack.push(5)
stack.push(3)
stack.push(7)
print(stack.pop())  # 7
print(stack.peek()) # 3
print(stack.size()) # 2

Анализ правильности скобочного выражения

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

Алгоритм проверки скобок:

Создать пустой стек
Пройти по каждому символу в выражении
Если символ — открывающая скобка, добавить ее в стек
Если символ — закрывающая скобка:
- Если стек пуст — выражение неверное
- Если верхний элемент стека не соответствует скобке — выражение неверное
- Иначе удалить верхний элемент стека
После обработки всех символов, если стек не пуст — выражение неверное

def is_balanced(expression):
    stack = []
    matching_brackets = {')': '(', ']': '[', '}': '{'}
    
    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != matching_brackets[char]:
                return False
            stack.pop()
    
    return len(stack) == 0

# Примеры использования
print(is_balanced("((()))"))    # True
print(is_balanced("({[]})"))    # True
print(is_balanced("({[})"))     # False
print(is_balanced("((())"))     # False

Выражение: (()())

(

)

(

)

Стек:

(

Визуализация проверки скобочного выражения

Вычисление выражений в постфиксной форме

Постфиксная запись (обратная польская запись) — это форма записи математических выражений, в которой операторы следуют после своих операндов. Стек идеально подходит для вычисления таких выражений.

Алгоритм вычисления постфиксного выражения:

Создать пустой стек
Разбить выражение на токены (числа и операторы)
Для каждого токена:
- Если токен — число, добавить его в стек
- Если токен — оператор, извлечь из стека два операнда
- Выполнить операцию и результат поместить в стек
После обработки всех токенов, результат будет в стеке

def evaluate_postfix(expression):
    stack = []
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b
    }
    
    for token in expression.split():
        if token in operators:
            # Извлекаем два операнда из стека
            b = stack.pop()
            a = stack.pop()
            # Выполняем операцию и помещаем результат в стек
            result = operators[token](a, b)
            stack.append(result)
        else:
            # Преобразуем токен в число и добавляем в стек
            stack.append(float(token))
    
    return stack[0] if stack else 0

# Пример использования
result = evaluate_postfix("5 3 + 2 *")  # (5 + 3) * 2 = 16
print(result)  # 16.0

result = evaluate_postfix("10 5 - 3 /")  # (10 - 5) / 3 ≈ 1.666
print(result)  # 1.666...

Выражение: 5 3 + 2 *

Стек:

Визуализация вычисления постфиксного выражения

Очередь (FIFO — First In, First Out)

Принцип работы очереди

Очередь работает по принципу FIFO (First In, First Out) — первый пришел, первый ушел. Основные операции:

Enqueue — добавление элемента в конец очереди
Dequeue — удаление элемента из начала очереди
Peek — просмотр первого элемента без удаления

Dequeue()

Enqueue(9)

Визуализация операций Enqueue и Dequeue в очереди

Реализация очереди в Python

# Реализация очереди с использованием списка
class Queue:
    def __init__(self):
        self.items = []
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        return None
    
    def peek(self):
        if not self.is_empty():
            return self.items[0]
        return None
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# Пример использования
queue = Queue()
queue.enqueue(5)
queue.enqueue(3)
queue.enqueue(7)
print(queue.dequeue())  # 5
print(queue.peek())     # 3
print(queue.size())     # 2

Использование очереди для временного хранения данных

Очереди часто используются для временного хранения данных в различных приложениях:

Обработка задач

Очереди используются для управления задачами, которые нужно выполнить в порядке их поступления.

Буферизация данных

При передаче данных между быстрыми и медленными компонентами системы.

Поиск в ширину (BFS)

В алгоритмах на графах для обхода вершин в порядке их удаления от начальной вершины.

# Пример: система обработки задач с использованием очереди
class TaskSystem:
    def __init__(self):
        self.task_queue = Queue()
    
    def add_task(self, task):
        print(f"Добавлена задача: {task}")
        self.task_queue.enqueue(task)
    
    def process_tasks(self):
        print("Обработка задач...")
        while not self.task_queue.is_empty():
            task = self.task_queue.dequeue()
            print(f"Обрабатывается задача: {task}")
            # Имитация обработки задачи
            # time.sleep(1)
        print("Все задачи обработаны!")

# Пример использования
system = TaskSystem()
system.add_task("Отправить email")
system.add_task("Создать отчет")
system.add_task("Обновить базу данных")
system.process_tasks()

Сравнение стека и очереди

Характеристика	Стек	Очередь
Принцип работы	LIFO (Last In, First Out)	FIFO (First In, First Out)
Основные операции	Push, Pop, Peek	Enqueue, Dequeue, Peek
Сложность операций	O(1) для всех операций	O(1) для Enqueue, O(n) для Dequeue (в наивной реализации)
Применение	Проверка скобок, постфиксные выражения, отмена действий	Обработка задач, BFS, буферизация

Заключение

Стеки и очереди — фундаментальные структуры данных, которые широко используются в программировании для решения различных задач. Понимание их работы и особенностей необходимо для успешной сдачи ЕГЭ по информатике и для дальнейшего изучения алгоритмов и структур данных.

Стек идеально подходит для задач, связанных с обратной обработкой данных (LIFO), тогда как очередь используется, когда важен порядок поступления данных (FIFO).