Используйте стек для обратного порядка
Представьте стопку карточек, к которой можно обращаться только сверху. Новая карточка кладётся сверху, и оттуда же снимается следующая. Если последовательно добавить А, Б и В, первым извлечётся В. Такой порядок полезен, когда нужно вернуться от последнего действия к предыдущему. Например, учебная история отмены может хранить выполненные изменения в обратном порядке. При этом полноценная отмена требует достаточных сведений о каждом действии; один список названий не восстановит прежнее состояние документа.
Используйте очередь для порядка поступления
В обычной очереди новые элементы добавляются в конец, а извлечение происходит из начала. После добавления А, Б и В первым будет А. Так можно описать обработку заявок по времени поступления. Однако правило очереди не означает, что реальная задача всегда должна выполняться именно так. Иногда нужны приоритеты или отдельные группы. Тогда структура и алгоритм должны явно отражать другое условие. Нельзя незаметно извлекать случайный элемент и продолжать называть процесс строгой очередью поступления.
Опишите операции и граничные состояния
Для обеих структур нужны добавление, извлечение и проверка пустоты. Иногда также требуется посмотреть следующий элемент, не удаляя его. Заранее решите, что происходит при попытке извлечения из пустой структуры: возвращается специальный результат или возникает понятная ошибка. Не используйте обычное допустимое значение так, чтобы его можно было спутать с отсутствием элемента. Если элементы повторяются, различайте значение и конкретную запись. Две карточки с одинаковой буквой могут представлять разные задачи и должны обрабатываться дважды.
Отделяйте правило от реализации
Стек и очередь можно реализовать разными способами. Внешнее поведение определяется порядком операций, а затраты времени и памяти зависят от выбранного устройства хранения. Например, операция, удобная для конца динамического массива, не обязательно столь же удобна для его начала. Поэтому сначала проверяют корректность логики, а затем оценивают реализацию под нужный объём. Полезно фиксировать инвариант: в очереди необработанные записи сохраняют порядок поступления. После каждого шага можно проверить, не нарушено ли это условие.
Попробуйте на практике
Выполните одну последовательность операций одновременно для стека и очереди.
- Подготовьте карточки А, Б и В. Добавьте А, затем Б в обе структуры.
- Извлеките один элемент и запишите, какой вернул стек и какой очередь.
- Добавьте В, затем извлеките все оставшиеся элементы, сохраняя порядок результатов.
- Попробуйте выполнить ещё одно извлечение на бумажной модели и опишите заранее выбранный исход пустого состояния.
Как проверить результат. Первое извлечение возвращает Б из стека и А из очереди. После добавления В стек отдаёт В, затем А; очередь Б, затем В. Пустое состояние обработано отдельно.
Частые вопросы
Очередь всегда справедливее стека?
Это разные правила для разных задач. Справедливость процесса определяется требованиями системы, а не одним названием структуры данных.
Можно ли хранить в стеке сложные объекты?
Да. Тип элемента не меняет правило порядка. Важно, чтобы операции сохраняли нужные данные и различали отдельные записи.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.