Структуры данных: стек и очередь

Динамические структуры данных

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

Стек

Стек работает по принципу «последним пришёл — первым вышел». Новый элемент кладут на вершину, и извлекают тоже с вершины. Образ — стопка тарелок: берут верхнюю, ту, что положили последней.

Основные операции: push — положить элемент на вершину, pop — снять верхний элемент. В Python стек удобно моделировать списком:

stek = []
stek.append(5) # push
x = stek.pop() # pop

Очередь

Очередь работает по принципу «первым пришёл — первым вышел». Элементы добавляют в конец, а извлекают из начала — как живая очередь в магазине. Кто встал раньше, того и обслужат первым.

Структура	Принцип	Добавление	Удаление
Стек	последним пришёл — первым вышел	на вершину	с вершины
Очередь	первым пришёл — первым вышел	в конец	из начала

Где применяются

Стек используется для отмены действий (кнопка «назад»), вычисления выражений, организации вызовов подпрограмм — именно стек хранит цепочку рекурсивных вызовов. Очередь нужна там, где заявки обрабатывают в порядке поступления: печать документов, обработка сообщений, моделирование потоков.

Разбор примера

Проверка правильности скобок использует стек: открывающую скобку кладут в стек, при закрывающей — снимают парную. Если в конце стек пуст — скобки расставлены верно:

for c in s:
if c == '(': stek.append(c)
elif c == ')': stek.pop()

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

Реализация на массиве

И стек, и очередь можно построить на обычном массиве с указателями. Для стека достаточно хранить индекс вершины: при добавлении он растёт, при удалении уменьшается. Для очереди хранят два указателя — на начало и на конец. Чтобы массив не «уезжал» в одну сторону по мере работы очереди, применяют кольцевую (циклическую) реализацию, где индексы возвращаются к началу массива.

Применение	Подходящая структура
Кнопка «отменить»	стек
Очередь печати	очередь
Проверка скобок	стек
Обход графа в ширину	очередь

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

Рабочая очередь на Python

Для очереди FIFO удобно использовать deque: append добавляет справа, popleft извлекает слева. В отличие от list.pop(0), такое извлечение не требует сдвигать все оставшиеся элементы.

from collections import deque

queue = deque(['task-A', 'task-B'])
queue.append('task-C')
first = queue.popleft()
print(first)        # task-A
print(list(queue))  # ['task-B', 'task-C']

while queue:
    current = queue.popleft()
    print(current)  # task-B, затем task-C

Условие while queue проверяет, что структура не пуста. Вызов popleft для пустой deque вызывает IndexError. Если ожидаются параллельные производители и потребители с ожиданием данных, одной этой проверки недостаточно: нужна подходящая синхронизация, например интерфейс queue.Queue. Здесь показана последовательная учебная программа.

Как сделать очередь обычным списком

Можно хранить индекс head первого активного элемента: добавлять в конец, а при извлечении увеличивать head. Активная длина равна len(items) − head. Важно проверять непустоту до обращения items[head]. Уже использованные элементы продолжают занимать память до очистки.

Если время от времени удалять использованный префикс, один такой шаг может занимать линейное время. Поэтому оценка «O(1) в худшем случае для каждого извлечения» неверна; речь может идти об амортизированной оценке по всей последовательности операций.

Когда ограничение размера меняет поведение

deque(maxlen=3) при добавлении четвёртого элемента справа автоматически удалит самый левый. Это полезно для хранения последних трёх событий, но опасно для очереди заявок, где ничего нельзя терять. Задайте правила переполнения до выбора реализации.

Самопроверка: после добавления 10,20, извлечения первого и добавления 30 очередь содержит 20,30. Если извлечено 30, использован стековый pop справа, а не FIFO popleft слева.

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

Первоисточники: Python: deque и операции очереди.

Кратко о главном

• Стек: последним пришёл — первым вышел; работа с вершиной.
• Очередь: первым пришёл — первым вышел; добавление в конец, извлечение из начала.
• Стек применяют для отмены действий и рекурсии, очередь — для заявок.
• Перед извлечением проверяют, что структура не пуста.

Источники и материалы

• Python: deque и операции очереди