Лекция
Стек и очередь: реализации и задачи в программировании
Изучите основы стека и очереди, их реализацию и применение в Computer Science.
- стек
- очередь
- абстрактные типы данных
- ADTs
- LIFO
- FIFO
- алгоритмы
- реализация структур данных
Для звонков по России
Личный кабинет
Лекция
Изучите основы стека и очереди, их реализацию и применение в Computer Science.
Подскажем по теме, разберём задание и поможем довести работу до результата.
Раньше мы рассматривали структуры данных как конкретные способы организации объектов в памяти — например, массивы или связные списки. Однако в Computer Science важна концепция Абстрактного Типа Данных (ADT). Это математическая модель, которая определяет набор доступных операций и их логику, полностью скрывая детали реализации.
Стек и очередь — базовые ADT, накладывающие жесткие ограничения на доступ к данным. В отличие от массива, позволяющего извлечь любой элемент по индексу (Random Access) за , здесь интерфейс сознательно сужается для гарантии строгого порядка обработки.
Различие между этими структурами заключается в их дисциплине обслуживания:
Диаграмма загружается…
Формально ADT описывается через аксиомы. Пусть — состояние стека, а — элемент. Основной интерфейс включает операции , , и .
Поведение стека определяют зависимости:
Формулы показывают, что возвращает структуру в состояние, предшествующее последнему . Сложность всех операций в ADT Stack и Queue должна составлять . Позже мы докажем это на практике, реализуя данные модели через динамические массивы и связные списки.
Стек работает по принципу LIFO (Last In, First Out — «последним пришел, первым ушел»). Для его внутреннего устройства подходят две базовые стратегии управления данными: непрерывные блоки памяти (массивы) или связные узлы (списки).
В этом случае элементы располагаются в последовательных ячейках. Стек растет «вправо», а специальный указатель top отслеживает индекс последнего добавленного объекта.
Push: Сначала проверяется свободное место. Если массив заполнен, выделяется новый блок памяти большего размера (реаллокация). Затем значение записывается в ячейку после текущего top, и указатель обновляется.Pop: Программа считывает данные по индексу top, после чего уменьшает указатель на единицу. Физически затирать данные не нужно — они остаются в памяти, но считаются «мусором» за пределами логической границы стека.class ArrayStack:
def __init__(self):
self._data = [] # Используем встроенный динамический массив
def push(self, value):
self._data.append(value) # Амортизированная сложность O(1)
def pop(self):
if not self.is_empty():
return self._data.pop() # O(1)
raise IndexError("Stack is empty")
def is_empty(self):
return len(self._data) == 0
Каждый элемент здесь представлен отдельным узлом, содержащим данные и ссылку на соседа. Вершиной стека всегда выступает «голова» (head). Преимущество этого метода в том, что программе не требуется резервировать огромный монолитный участок памяти заранее.
Push: Создается новый объект-узел. Его поле ссылки направляется на текущую голову, после чего сама голова переключается на этот новый элемент.Pop: Значение из головы сохраняется для возврата, указатель головы перемещается на следующий узел, а старый объект удаляется из памяти.Диаграмма загружается…
| Операция | Динамический массив | Связный список |
|---|---|---|
| Push | амортизировано | строго |
| Pop | ||
| Память | Резерв под расширение | Указатели в каждом узле |
| Локальность данных | Высокая (удобно для кэша) | Низкая |
Теоретически стек может расти бесконечно, но на практике ресурсы компьютера ограничены. Ошибки возникают в двух случаях:
Обратимся теперь к очередям, чтобы увидеть, как те же самые структуры адаптируются под дисциплину FIFO и почему обычный массив при таком подходе может потребовать дорогостоящего сдвига элементов.
В отличие от стека, основанного на принципе «последним пришел — первым ушел», очередь работает по правилу FIFO (First In, First Out). Элемент, который попал в структуру первым, должен быть извлечен раньше остальных. Интерфейс классической очереди минималистичен: enqueue (добавление в хвост) и dequeue (извлечение из головы).
При попытке построить очередь на базе стандартного динамического массива возникает асимметрия производительности. Операция enqueue (аналог push_back) выполняется за амортизированное время . Проблемы начинаются на этапе dequeue, когда нужно удалить объект из самого начала (индекс 0).
Для сохранения непрерывности данных в памяти после удаления первого элемента все оставшиеся объектов приходится перемещать на одну позицию влево. Линейная сложность каждого извлечения превращает обработку потока данных в тяжелую вычислительную задачу. При необходимости обработать элементов общее время составит .
Обеспечить для обеих операций в массиве позволяет механика кольцевого буфера. Вместо трудоемкого перемещения данных мы меняем границы самой очереди, используя индексы head и tail.
Когда tail доходит до конца выделенной памяти, он переходит в начало массива — при условии, что там освободилось пространство после вызова dequeue. Такая логика опирается на арифметику остатка от деления на общую емкость буфера Cap.
Диаграмма загружается…
Обновление позиций происходит по формулам:
head = (head + 1) % Captail = (tail + 1) % CapРассмотрим пример программной реализации такой структуры:
class CircularQueue:
def __init__(self, capacity):
self.cap = capacity
self.buffer = [None] * capacity
self.head = 0
self.tail = 0
self.size = 0
def enqueue(self, item):
if self.size == self.cap:
raise OverflowError("Queue is full")
self.buffer[self.tail] = item
self.tail = (self.tail + 1) % self.cap
self.size += 1
def dequeue(self):
if self.size == 0:
raise IndexError("Queue is empty")
data = self.buffer[self.head]
self.head = (self.head + 1) % self.cap
self.size -= 1
return data
Если заранее неизвестно количество элементов и жесткий лимит массива неудобен, очередь можно построить на базе двусвязного списка. В этой модели хранятся ссылки на первый (head) и последний (tail) узлы.
tail.head на следующий по порядку узел.В этом случае оба метода гарантированно работают за , так как не требуют копирования данных или пересчета индексов. Однако за гибкость приходится платить повышенным расходом памяти, необходимой для хранения ссылок в каждом узле.
В будущем мы изучим, как эта концепция эволюционирует в «Очередь с приоритетом», где порядок извлечения зависит не от времени добавления, а от значимости конкретного элемента.
Эффективность стека и очереди определяется фундаментом, на котором они построены. При оценке производительности решающую роль играет вычислительная стоимость операций в начале и конце коллекции.
Сопоставим временные затраты для базовых действий. Учтите, что для динамического массива показатель считается амортизированным, так как периодически требуется выделение новой памяти и перенос данных.
| Операция | Стек (Массив) | Стек (Список) | Очередь (Список) | Очередь (Кольцевой буфер) |
|---|---|---|---|---|
| Push / Enqueue | ||||
| Pop / Dequeue | ||||
| Peek (Top/Front) | ||||
| Search (поиск) | ||||
| Space Complexity |
Примечание: Связный список расходует больше оперативной памяти из-за хранения системы указателей, однако массив эффективнее использует кэш процессора благодаря локальности данных.
Механика LIFO незаменима там, где необходимо фиксировать промежуточные состояния или соблюдать строгую обратную последовательность обработки.
pop.Очереди становятся основой для балансировки нагрузки и выстраивания асинхронного взаимодействия.
Диаграмма загружается…
Переход от теории к реализации вскрывает нюансы, которые легко упустить при обсуждении абстрактных типов данных. Стек и очередь кажутся простыми конструкциями, пока дело не доходит до обработки граничных условий и управления ресурсами.
Проверка правильности расстановки скобок — классический сценарий применения стека. Здесь структура выполняет роль «памяти» для ожидаемых закрывающих символов. Алгоритм обходит строку: если встречается открывающая скобка, она отправляется в стек; если закрывающая — проверяется её соответствие верхнему элементу.
def is_balanced(expression: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in expression:
if char in mapping.values():
stack.append(char)
elif char in mapping:
# ОШИБКА 1: Попытка вызова pop() из пустого стека
if not stack or stack.pop() != mapping[char]:
return False
# ОШИБКА 2: Игнорирование оставшихся в стеке элементов
return len(stack) == 0
Нарушение инварианта пустого контейнера
Частый баг — вызов операций извлечения (pop, front) без предварительной проверки is_empty(). В низкоуровневых языках это чревато Segmentation Fault, а в Python приводит к IndexError. Проверку на пустоту необходимо встраивать в логику вызывающего кода или обрабатывать внутри метода с помощью исключений.
Утечки памяти (Loitering) В реализациях на базе связных списков или динамических массивов разработчики иногда забывают обнулять ссылки.
next может оставить в памяти изолированный фрагмент цепи.Ошибки «off-by-one» в кольцевом буфере При создании очереди на базе массива критически важно различать состояния «пусто» и «заполнено».
Диаграмма загружается…
Просчет кроется в использовании условия head == tail для обоих сценариев. Чтобы избежать путаницы, обычно либо оставляют один слот массива пустым, либо вводят отдельный счетчик size.
Избыточное копирование Если стек базируется на динамическом массиве, стоит учитывать стоимость реалокации. Когда максимальное количество элементов известно заранее, лучше сразу инициализировать структуру с фиксированным размером. Это позволит избежать амортизированных затрат на расширение памяти в критических участках программы.
В дальнейшем мы изучим, как стек помогает в обходе деревьев (DFS), а очереди становятся основой для поиска в ширину (BFS) и систем управления приоритетами.