Стек, очередь и дек — простые структуры данных, на которых держатся вызовы функций, обработка задач по порядку и разбор выражений. Различаются они тем, с какого конца добавляют и забирают элементы.
Что нужно знать
- Стек — LIFO («последним пришёл — первым ушёл»): push, pop, top.
- Очередь — FIFO («первым пришёл — первым ушёл»): добавление в хвост, извлечение из головы.
- Дек — добавление и извлечение с обоих концов.
- Реализации: массив с указателем вершины, кольцевой буфер (индексы по модулю размера), связный список.
- Скобки: открывающую кладём в стек, закрывающая должна совпасть с вершиной; в конце стек пуст.
- Обратная польская запись: число — в стек, знак — снять два числа, вычислить, положить результат.
- Все основные операции этих структур выполняются за $O(1)$.
Где чаще всего ошибаются
- Путать порядок операндов при вычитании и делении в ОПЗ.
- Забывать проверить, что стек пуст в конце проверки скобок.
- Извлекать из пустого стека или очереди без проверки.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Программирование (ИТ-класс) · 10–11 классы · Стек, очередь, дек