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

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

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

Стек

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

Основные операции: 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()

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

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

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

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

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

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

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