§ 42. Стек, очередь, дек

Определения и обозначения

Стек — структура данных, в которой добавление и удаление элементов происходят с одного конца; последним добавлен — первым удалён (LIFO, от английского Last In, First Out). Этот конец называют вершиной стека: новый элемент кладут на вершину, а при удалении снимают именно его. Такой порядок нужен, когда сначала следует завершить самое последнее начатое действие.

Очередь — структура данных, в которой элементы добавляют в конец, а удаляют из начала; первым добавлен — первым удалён (FIFO, First In, First Out). Она похожа на обычную очередь людей: новый участник становится в хвост, а первым обслуживают того, кто стоит впереди. Это правило удобно, когда важно обрабатывать поступившие данные по порядку.

Дек — структура данных, в которой добавлять и удалять элементы можно с обоих концов. Название происходит от слов «двусторонняя очередь»: у дека есть начало и конец, и оба доступны для операций. Такая гибкость позволяет использовать его и как стек, и как очередь, выбирая нужный конец в зависимости от задачи.

Как это устроено

Представим пустой стек, в который по очереди кладут числа 4, 7 и 2. После добавления 4 она находится на вершине, затем число 7 закрывает её, а число 2 оказывается сверху всех остальных. При удалении нельзя перескочить через верхний элемент, поэтому первым снимают 2, затем 7 и наконец 4; именно так реализуется LIFO.

В очереди порядок действий другой: новый элемент присоединяется к концу, а обслуживают того, кто находится в начале. Если добавить Аню, Бориса и Веру, Аня окажется впереди, Борис — за ней, Вера — последней. Удаление Ани не переставляет остальных: теперь первым становится Борис, потому что он раньше Веры вошёл в очередь.

Основные действия — добавить элемент, удалить его и посмотреть доступный элемент, не удаляя. В стеке добавление кладёт элемент на вершину, удаление снимает вершину, а просмотр показывает верхний элемент. В очереди добавление выполняется в конец, удаление — из начала, просмотр показывает первого в очереди; в обоих случаях просмотр сам по себе не меняет порядок.

Дек объединяет возможности двух структур, потому что операции разрешены и у начала, и у конца. Например, если добавлять и удалять только с одного конца, он будет работать как стек; если добавлять с одного конца, а удалять с другого — как очередь. В других задачах можно попеременно использовать оба края, например сравнивать крайние элементы последовательности.

Любая операция зависит от текущего состояния структуры: если элементов нет, удалять нечего и просматривать нечего. После успешного удаления число элементов уменьшается, а доступным становится следующий элемент согласно правилу структуры. Поэтому перед операцией нужно проследить, что именно сейчас находится на вершине, в начале или на концах дека, иначе можно нарушить порядок или выполнить невозможное действие.

Сравнение стека, очереди и дека

Сначала сравните, с каких концов выполняются добавление и удаление, а затем определите, какой элемент доступен без извлечения. Если нужно сохранить порядок поступления, выбирайте очередь; если требуется обратный порядок — стек. Дек подходит, когда алгоритму нужны оба конца.

Разбор задач

Задача 1

В пустой стек последовательно добавили числа 4, 7 и 2. Нужно определить, в каком порядке они будут удалены. Поскольку стек работает по правилу LIFO, сначала рассматриваем последний добавленный элемент. Затем продолжаем с новой вершины.

1. Добавляем 4: она становится единственным элементом и вершиной.
2. Добавляем 7: она оказывается над числом 4.
3. Добавляем 2: она становится новой вершиной, поэтому снимаем сначала 2, затем 7, затем 4.

Ответ: числа будут удалены в порядке 2, 7, 4. Идти от 4 к 2 нельзя, потому что нижние элементы закрыты теми, которые добавили позже.

Задача 2

В очередь добавили фамилии Ани, Бориса и Веры, затем удалили двух человек. Нужно выяснить, кто останется и кто будет удалён первым. Очередь сохраняет порядок поступления, поэтому первым обслуживают того, кого добавили раньше всех. После его удаления начало очереди сдвигается к следующему человеку.

1. Добавляем Аню, Бориса и Веру: они стоят именно в таком порядке.
2. Первое удаление убирает Аню из начала очереди.
3. Второе удаление убирает Бориса, который теперь стоит первым.
4. После двух удалений в очереди остаётся Вера.

Ответ: первой будет удалена Аня, а останется Вера. При добавлении очередь не перестраивается: новые участники становятся за теми, кто уже ждёт.

Задача 3

Дана последовательность целых чисел, нужно проверить, является ли она палиндромом, то есть читается одинаково слева направо и справа налево. Дек позволяет сравнивать первый и последний элементы без перебора всей последовательности. Если края совпали, их можно убрать и повторить проверку для оставшейся середины.

1. Помещаем последовательность в дек, сохраняя исходный порядок.
2. Сравниваем элементы на обоих концах; если они различаются, последовательность не палиндром.
3. Если элементы равны, удаляем оба и снова сравниваем крайние элементы.
4. Продолжаем, пока дек не опустеет или в нём не останется один элемент.

Ответ: последовательность является палиндромом, если несовпадений не встретилось. Один оставшийся средний элемент не мешает симметрии, потому что у него нет пары для сравнения.

Типичные ошибки

Путать направления добавления и удаления в очереди — значит, например, пытаться убрать человека из конца. Ошибка возникает, когда правило очереди мысленно заменяют правилами стека. Проверяйте себя: новый элемент встаёт в конец, а обслуживают того, кто дольше всех ждёт в начале.

Считать, что из стека можно удалить любой элемент, нельзя: доступна только вершина. Такую ошибку допускают, если воспринимают стек как обычный список, где можно выбрать произвольную позицию. Представьте элементы друг над другом и убедитесь, что выбранный для удаления находится сверху.

Путать LIFO и FIFO — значит неверно предсказывать, кто или что выйдет первым. Названия похожи, поэтому полезно не ограничиваться запоминанием букв, а проследить путь элементов. Для стека задайте вопрос «что добавили последним?», для очереди — «что поступило первым?».

Удалять элемент или просматривать вершину, когда структура пуста, невозможно. Это происходит, если выполнять команды, не отслеживая изменения после предыдущих операций. Перед каждым удалением и просмотром проверьте количество элементов; если оно равно нулю, сначала нужно добавить элемент или завершить действия.

Связь с другими темами

Для работы со стеком, очередью и деком нужно уметь понимать последовательность и выполнять алгоритм пошагово: после каждой команды фиксировать, какие элементы остались и где находятся доступные концы. Стек применяется при разборе выражений, проверке скобок и организации вызовов функций, потому что последние начатые действия завершаются первыми. Очереди и деки полезны при моделировании обслуживания заявок, обходе графов и обработке данных в порядке поступления или с двух сторон.

Что запомнить

• Стек работает по правилу LIFO: последним добавлен — первым удалён.
• Очередь работает по правилу FIFO: первым добавлен — первым удалён.
• В стеке добавляют и удаляют элементы с одного конца.
• В очереди добавляют в конец, а удаляют из начала.
• В деке добавление и удаление возможны с обоих концов.
• Перед удалением или просмотром элемента нужно проверить, что структура не пуста.