Информатика · объяснение и практика

Когда нужен стек, а когда очередь

Выбираем дисциплину извлечения для отмены действий и очереди заданий, проверяем порядок на короткой последовательности и различаем интерфейс структуры с её реализацией.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Структуры данных · Учебная карта

Главная мысль

Стек извлекает последний добавленный элемент первым: LIFO. Очередь извлекает первый добавленный первым: FIFO. Выбор определяется требуемым порядком обработки, а не тем, в каком контейнере удобно хранить значения.

Как одна последовательность даёт разные ответы

В структуру последовательно добавили А, Б, В. Стек вернёт сначала В, затем Б, затем А. Очередь вернёт А, затем Б, затем В. Содержимое до извлечения может выглядеть одинаково, но правило доступа разное. Поэтому название структуры описывает поведение операций, а не просто форму записи списка.

Отмена действий естественно использует стек: последнюю правку отменяют раньше предыдущей. Очередь печати естественно обрабатывает раньше поступившее задание, если нет дополнительных приоритетов. Если появляются срочные задания с отдельным правилом выбора, это уже не простая FIFO-очередь. Слово «очередь» в интерфейсе не гарантирует одну дисциплину без описания приоритетов.

Какие операции подходят в Python

Список удобно использовать как стек: append добавляет в конец, pop без индекса снимает с конца. Для очереди с извлечением слева подходит collections.deque: append добавляет справа, popleft извлекает слева. Эти операции позволяют явно показать противоположные края, не меняя порядок остальных элементов вручную.

Список с pop(0) может корректно моделировать FIFO, но при каждом удалении начала приходится сдвигать оставшиеся ссылки. Для длинной очереди это неудачный выбор по стоимости операций. Корректность порядка и эффективность реализации — разные вопросы. Замена контейнера должна сохранять контракт, а не неожиданно переворачивать направление обработки ради удобного метода pop.

Пример

Добавили 1,2,3, извлекли один элемент, затем добавили 4. Что извлечётся дальше из очереди?

Сначала был извлечён 1. После добавления 4 очередь содержит 2,3,4, поэтому следующим будет 2. Добавление в конец не вытесняет давно ожидающее начало.

Что проверять на границах

Извлечение из пустой структуры требует явного поведения: исключение, специальный результат или ожидание нового элемента в отдельной синхронизированной модели. Нельзя считать пустоту значением 0, если ноль является допустимым элементом. Ограниченная очередь также должна определить, что происходит при переполнении: отказ, ожидание или удаление старого элемента.

Многопоточное ожидание и безопасность нескольких операций не появляются автоматически от выбора слова FIFO. Проверка пустоты и последующее извлечение могут потребовать согласованной синхронизации. Для учебного однопоточного примера достаточно описать порядок, но перенос в рабочую систему требует учитывать среду. Хороший тест использует различимые значения и чередует добавление с извлечением: проверка только окончательного набора не обнаружит перепутанный порядок.

От чтения к действию

А теперь — вы

В стек добавили 5,8,2. Что извлечёт первый pop с вершины?

Частые вопросы

pop(0) превращает список в логически неверную очередь?

Нет. Порядок FIFO может быть верным, но удаление начала списка дорого для длинных данных.

Пустая структура должна возвращать 0?

Не обязательно. Поведение задаётся контрактом, и ноль может быть обычным допустимым элементом.

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

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться