- Дайте определение использованию стеков и объясните его своими словами
- Правильно используйте ключевые термины, например «стек»
- Применяйте изученное к новым примерам и вопросам
- Избегайте типичных ошибок, которые ученики допускают в этой теме
Список — не всегда правильный инструмент: кнопки отмены, очереди печати, файловые системы и навигаторы нуждаются каждый в своём способе организации данных. Структуры данных — это такие специализированные контейнеры, и удачный выбор — то, что отделяет работающий код от элегантного. В этой главе строятся четыре структуры, которые должен освоить каждый ученик A-level.
Этот урок посвящён использованию стеков: храните данные по принципу «последним пришёл — первым ушёл», как стопку тарелок.
Храните данные по принципу «последним пришёл — первым ушёл», как стопку тарелок.
Ключевые идеи
LIFO против FIFO меняет всё
Стеки меняют порядок на обратный — идеальны для отмены, кнопок «Назад» и проверки сбалансированности скобок. Очереди сохраняют порядок — идеальны для очереди печати и честной обработки запросов. Операции тоже различаются: стеки кладут и снимают сверху, а очереди добавляют сзади и удаляют спереди. Неверный выбор молча даёт неверные ответы.
Деревья превращают поиск в деление пополам
Двоичное дерево поиска держит меньшие значения слева, а большие справа, поэтому каждое сравнение отбрасывает половину дерева — та же идея, что и бинарный поиск, встроенная в структуру. Обходы посещают узлы в разном порядке: симметричный обход двоичного дерева поиска даёт значения отсортированными. Порядок вставки формирует дерево, и неудачный порядок вставки вырождает его в медленный связный список.
Термин — стек: Структура «последним пришёл — первым ушёл»: элементы добавляются и удаляются с одного конца, называемого верхом, — как подпружиненный раздатчик тарелок.
Начните с пустого стека. Положите 4, положите 7, снимите, положите 2, снимите. Что возвращает каждое снятие и что остаётся?
Кладём 4: стек — [4], 4 сверху. Кладём 7: стек — [4, 7], 7 сверху. Снятие убирает сверху, поэтому первое снятие возвращает 7. Стек — [4]. Кладём 2: стек — [4, 2], 2 сверху. Снятие снова убирает верх, поэтому второе снятие возвращает 2. Стек — [4].
Ответ: Снятия возвращают 7, затем 2, а в стеке остаётся лишь [4] — «последним пришёл — первым ушёл».
- Использование стека там, где нужна очередь Исправление: спросите себя «должен ли первый пришедший быть обслужен первым?» — если да, нужна очередь; стек обслужил бы последнего пришедшего первым.
- Извлечение из пустой структуры или удаление из пустой очереди Исправление: всегда сначала проверяйте, что структура не пуста — удаление из ничего вызывает ошибку опустошения.
Практика
Стек — каждая новая страница кладётся, а «Назад» снимает самую свежую страницу, то есть работает по принципу «последним пришёл — первым ушёл».
Верно — кладите каждую открывающую скобку и снимайте на каждой закрывающей; последняя открытая должна закрыться первой, а это как раз LIFO.
[B, C, D] — A уходит спереди, а D присоединяется сзади.
3 — она идёт влево от корня 5, а затем 1 идёт влево от 3.
Быстрая проверка
Что из этого лучше всего определяет "стек"?
В дорожной сети, смоделированной как граф, что представляют узлы, рёбра и веса?
Что даёт симметричный обход двоичного дерева поиска?
- Использование стеков: храните данные по принципу «последним пришёл — первым ушёл», как стопку тарелок.
- LIFO против FIFO меняет всё: Стеки меняют порядок на обратный — идеальны для отмены, кнопок «Назад» и проверки сбалансированности скобок.
- Узел: Отдельный элемент в дереве или графе, хранящий данные и ссылки на другие узлы.
- Остерегайтесь: использования стека там, где нужна очередь