03.02.101 Стеки и очереди - justjune/AiSD2026 GitHub Wiki
Контейнер (container) - абстрактный тип данных, позволяющий хранить и извлекать данные независимо от содержимого. Контейнеры различаются по поддерживаемому ими типу извлечения данных. Другими словами, они хранят объекты организованным образом, в соответствии с определенными правилами доступа. Стеки и очереди - наиболее важные типы контейнеров. Порядок извлечения в них зависит от порядка помещения. Их можно реализовывать посредством массивов и связанных списков.
Стеки
Название stack — это аналогия с набором физических предметов, сложенных друг на друга, например стопкой тарелок. Извлечение данных осуществляется в порядке LIFO («last-in, first-out», «последним вошел - первым вышел»). Как и в случае со стопкой физических объектов, эта структура позволяет легко достать элемент из верхней части стека, но для доступа к данным, расположенным глубже в стеке, требуется сначала удалить несколько других элементов. Поэтому стеки удобно применять в случаях, когда порядок извлечения данных не имеет никакого значения, - например, при обработке пакетных заданий. Операции вставки и извлечения данных для стеков выглядят так:
push(x, s)$-$ вставить элемент x в конец стека s.рор(s)$-$ извлечь верхний элемент из стека s.
Порядок LIFO возникает во многих реальных ситуациях. Например, из набитого битком вагона метро пассажиры выходят в порядке LIFO. В алгоритмах же этот порядок обычно возникает при выполнении рекурсивных операций.
Очереди
Название queue (очередь) — это аналогия со словами, используемыми для описания людей, стоящих в очереди за товарами или услугами. Очереди поддерживают порядок извлечения FIFO («first-in, first-out», «первым вошел - первым вышел»). Обработка задач в порядке FIFO минимизирует максимальное время ожидания. Обратите внимание, что среднее время ожидания будет одинаковым, независимо от применяемого порядка, будь то FIFO или LIFO. Очереди реализовать несколько труднее, чем стеки, и поэтому их применение больше подходит для приложений, в которых порядок извлечения данных является важным, - например, при эмуляции определенных процессов. Применительно к очередям операции вставки и извлечения данных выглядят соответсвенно:
enqueue (x, q)- вставить элемент х в конец очереди q;dequeue (q)- извлечь (и удалить) элемент в начале очереди q.
Литература
[ Скиена 2022 с. 101, 102]
[Контейнер (абстрактный тип данных)]