Реализация итерируемого стека на Python: руководство и мин-проект
Показывает стек с просмотром и обходом, который нужно отделять от извлечения и состояния итератора.
Читать материалСтек Python удобнее осваивать в три шага: сначала проверить порядок LIFO и просмотр без удаления, затем согласовать минимум и максимум с добавлением и извлечением, после этого применить извлечение к перевороту строки. Главный результат упражнения — предсказуемое состояние после каждого действия, а не только красивый вывод значений.
Выберите инструкцию под свою задачу. Ниже — подробный разбор выбора и проверки результата.
Показывает стек с просмотром и обходом, который нужно отделять от извлечения и состояния итератора.
Читать материалДаёт отслеживание текущих min/max при согласованном push и pop.
Читать материалИспользует извлечение символов для учебного переворота строки и сравнивает его со срезом.
Читать материалДобавьте по очереди три различных элемента: А, Б и В. Если вершиной выбран конец списка, извлечение должно вернуть В, затем Б, затем А. До удаления посмотрите вершину и обойдите содержимое. Запишите направление обхода: от основания к вершине или обратно. Оба варианта просмотра возможны, но его порядок нельзя путать с порядком извлечения.
Сравнивайте состояние до и после действия. Просмотр вершины и обычное чтение содержимого не должны удалять элементы, если это обещает ваш интерфейс. pop, напротив, меняет стек. Заранее определите поведение пустого состояния: исключение или явно выбранное значение. Смешивать варианты в одном интерфейсе без объяснения неудобно для вызывающего кода.
| Этап | Что меняется | Главная проверка |
|---|---|---|
| Просмотр и обход | Положение читающего итератора | Состав стека остаётся прежним |
| Добавление и извлечение | Вершина и количество элементов | Возвращается последний добавленный из оставшихся |
| Чтение min/max | Ничего в основном составе | Граница соответствует текущему содержимому |
| Переворот через pop | Рабочий стек постепенно пустеет | Выход совпадает с обратной последовательностью входа |
Разделяйте стек и средство его обхода. В учебной реализации, где индекс обхода хранится в самом объекте, вложенный цикл может сбросить положение внешнего. Поэтому успешный одиночный обход не подтверждает независимость двух обходов. Если это требуется, проектируйте отдельное состояние итераторов и проверяйте именно этот случай.
Теперь используйте числа и сохраняйте вместе с каждым уровнем текущие минимум и максимум. При добавлении обновляются и основной стек, и сведения о границах. При извлечении должны согласованно исчезнуть оба последних уровня. Чтение границ не должно менять число элементов.
Предложенная контрольная последовательность: добавить 5, 2, 10, 10. Минимум равен 2, максимум — 10. После удаления одного значения 10 максимум остаётся 10; после следующего возвращается к 5. Затем извлеките 2 и проверьте минимум 5. Такой пример обнаруживает ошибку, когда повторный максимум удаляют из служебного состояния слишком рано.
Дополните проверку одним элементом и пустым стеком. Для пустого случая явно согласуйте ответы min/max и pop. Не переносите на весь объект обещание потокобезопасности только из-за блокировки добавления и удаления: просмотр и последовательности нескольких операций могут иметь другие условия. Эти упражнения рассматривают последовательную работу.
Положите символы строки в рабочий стек в исходном порядке, затем извлекайте их до опустошения, собирая результат. Для учебной строки «кот» ожидается «ток». Это наглядное применение LIFO: первый выданный символ был последним добавленным. Обход без удаления и такая сборка результата имеют разный эффект на контейнер.
Проверьте пустую строку, один символ и строку с пробелом. Если задача именно перевернуть вход, нельзя незаметно отфильтровать небуквенные символы: это уже другое преобразование. Сравните итог со срезом для тех же учебных данных, но не объявляйте стек более быстрым способом. Повторное склеивание строк также не даёт универсальной гарантии линейного времени.
После трёх упражнений у вас останется таблица операций, ожидаемые значения и ожидаемый состав. При расширении класса сначала повторяйте этот короткий маршрут: новый способ чтения или дополнительные сведения не должны незаметно менять базовое правило LIFO.