Начало
Учебные материалы
Линейные АТД
Очередь
Очередью называют такой список, в котором добавление элемента возможно лишь в конец очереди, удаление — только из начала очереди. Принципом работы является "первым вошел, первым вышел" ("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(); |
Варианты реализации очереди:
- очередь фиксированного размера – на основе массива
- на основе односвязного или двусвязного списка
- на основе двух стеков
- на основе дека (по умолчанию в STL)
- потокобезопасная очередь без блокировок
При реализации очереди на списке нужно хранить указатель не только на первый, но и на последний элемент, чтобы выполнять добавление в очередь за O(1).
При реализации очереди на двух стеках добавление идет во "входной" стек, а извлечение из "выходного". Если при получении значения выходной стек пуст, то все элементы входного стека перемещаются в выходной в обратном порядке. Таким образом последний добавленный элемент окажется внизу стека. Амортизированная оценка эффективности операции извлечения равна O(n), но худшая оценка – O(n) – для случая пустого выходного стека. Для других реализаций очередей оценка всегда равна O(1).
