Порядок является частью результата
У обычной очереди первым извлекается тот элемент, который раньше остальных ещё ожидающих элементов был добавлен. У стека первым извлекается последний добавленный из оставшихся. Эти правила часто сокращают до FIFO и LIFO соответственно. Представьте три учебные заявки с метками А, Б и В. Если сначала добавить все три, очередь выдаст А, Б, В, а стек В, Б, А. Оба варианта сохраняют количество заявок. Поэтому проверка, которая сравнивает только набор полученных значений, пропустит ошибку. В условии теста нужно зафиксировать и последовательность.
Смешивайте добавление и извлечение
Проверка после единственной серии добавлений слишком проста для многих ошибок. Полезнее чередовать действия. Добавим А, затем Б, извлечём один элемент, добавим В и извлечём оставшиеся два. Для очереди ответ снова будет А, Б, В; после первого извлечения внутри остаётся Б, затем к ней присоединяется В. Для стека та же последовательность действий даст Б, В, А. Именно промежуточные состояния объясняют различие. Записывая их после каждого шага, вы проверяете правило работы, а не пытаетесь угадать причину по окончательному списку.
Выбирайте операции под правило
В Python двусторонняя очередь collections.deque поддерживает добавление и извлечение с обоих концов. Для простой очереди можно добавлять справа методом append и извлекать слева методом popleft. Метод pop извлекает справа; при добавлении с той же стороны получается поведение стека. Удаление первого элемента обычного списка методом pop с индексом ноль требует перемещения остальных элементов. У deque операции на концах рассчитаны на примерно постоянную стоимость. Это не означает, что deque быстрее для любой задачи: обращение к середине и другие операции имеют иные свойства. Сначала определяют нужное поведение, затем оценивают подходящую реализацию.
Проверьте границы учебной модели
Что должно происходить при попытке извлечения из пустой структуры? Это отдельное условие. У deque пустое извлечение вызывает IndexError. Программа может проверять пустоту или обрабатывать исключение, но выбранное поведение нужно согласовать с задачей. Также полезно проверить повторяющиеся значения. Две заявки могут иметь одинаковое описание и при этом оставаться двумя отдельными элементами. Для учебной трассировки используйте разные метки, а затем добавьте пример с повторами. Рассмотренная модель описывает последовательные действия одного исполнителя; требования к одновременному доступу нескольких исполнителей потребуют отдельного рассмотрения.
Попробуйте на практике
Проведите одну последовательность операций через очередь и стек на бумаге. Используйте метки 11, 22 и 33; их числовой порядок не должен влиять на извлечение.
- Создайте две пустые схемы. Для очереди обозначьте добавление справа и извлечение слева, для стека оба действия справа.
- Добавьте 11, затем 22. Извлеките один элемент из каждой структуры и запишите ответы отдельно.
- Добавьте 33. Нарисуйте оставшиеся элементы в обеих структурах, сохранив направление, выбранное в первом шаге.
- Извлеките ещё по два элемента. Соберите полную последовательность ответов для очереди и стека.
- Попробуйте описать следующее извлечение из каждой уже пустой структуры. Запишите, какое поведение вы ожидаете от учебной программы.
Как проверить результат. Очередь выдаёт 11, 22, 33. Стек выдаёт 22, 33, 11. В конце обе структуры пусты, а дополнительное извлечение рассмотрено отдельно от обычного случая.
Частые вопросы
Если значения одинаковые, можно ли проверить порядок?
По одним одинаковым значениям происхождение элемента может быть неразличимо. Для проверки добавьте учебные идентификаторы, сохранив повторяющееся содержимое, и проследите порядок именно элементов.
Почему нельзя сразу выбрать самую быструю структуру?
Быстрота имеет смысл относительно нужных операций и размера данных. Реализация, которая быстро выдаёт элементы в неверном порядке, не решает исходную задачу. Сначала проверяют правило, затем стоимость выполнения.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.