*Очередью* называют такой список, в котором
добавление элемента возможно лишь в конец очереди, удаление — только из начала очереди.
Принципом работы является "первым
вошел, первым вышел" ("first-in-first-out", или FIFO). Здесь есть
полная аналогия с очередью в магазине.
Базовые операции для очереди:
Операция|Эффективность|Вызов
--|--|--
конструктор (пустой набор) |`O(1)`| ``std::queue<int> s;``
количество и/или проверка на пустоту |`O(1)`| ``int len=s.size();``\
``if(s.empty())``
добавить значение |`O(1)`| ``s.push(x);``
первый элемент |`O(1)`| ``auto t=s.front();``
убрать первый |`O(1)`| ``s.pop();``
--
Варианты реализации очереди:
* очередь фиксированного размера -- на основе [массива](/viz/queue.html)
* на основе [односвязного или двусвязного списка](/viz/queue1.html)
* на основе [двух стеков](/viz/queue1.html)
* на основе дека (по умолчанию в STL)
* [потокобезопасная очередь без блокировок](https://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C_%D0%9C%D0%B0%D0%B9%D0%BA%D0%BB%D0%B0_%D0%B8_%D0%A1%D0%BA%D0%BE%D1%82%D1%82%D0%B0)
При реализации очереди на списке нужно хранить указатель не только на первый, но и на последний элемент, чтобы выполнять добавление в очередь за `O(1)`.
При реализации очереди на двух стеках добавление идет во "входной" стек, а извлечение из "выходного". Если при получении значения выходной стек пуст, то все элементы входного стека перемещаются в выходной в обратном порядке. Таким образом последний добавленный элемент окажется внизу стека. Амортизированная оценка эффективности операции извлечения равна `O(n)`, но худшая оценка -- `O(n)` -- для случая пустого выходного стека. Для других реализаций очередей оценка всегда равна `O(1)`.
Линейные АТД
Начало
Учебные материалы