Очереди, дек, Deque
Очереди
Иногда возникает необходимость последовательно обработать какие-то объемы данных, для этого их помещают в очередь.
Что это такое?
По сути это двусвязный список, где в конец мы добавляем новые элементы, из начала берем данные на обработку, а действия в середине списка запрещены.
Т.е. можем «положить в конец», можем «взять из начала».
В кольцевой очереди ресурсы от элемента из начала очереди “переносятся” в конец очереди, за счет чего мы можем добавить в нее новые данные. Кольцевая очередь может быть реализована на стеке.
Очередь с приоритетом:
1-Очередь с приоритетным включением- элементы могут быть упорядочены по приоритетам в момент поступления нового элемента.
Т.е. поступает новый элемент и, если у него большее высокий приоритет – ставится в начало очереди.
2-Очередь с приоритетным исключением – элементы попадают в очередь без сортировки, но в момент взятия/извлечения нового объекта из очереди выбирается элемент с самым высоким приоритетом.
Примечание: обычно наименьший номер приоритета означает более высокий приоритет.
Дек | Deque (double ended queue) – двусторонняя очередь
В C++ также есть понятие двусторонней очереди, т.е. очереди данные в которую можно добавлять и забирать с обоих концов (правого и левого).
Т.е. главные операции происходят на концах очереди, поэтому по реализации Deque похож на двусвязный список, но для ускорения операций он обычно оптимизирован, и каждый узел такого двусвязного списка представляет собой массив из нескольких элементов.
При такой реализации скорость прохода по элементам «массива» достаточно высока, а за счет вида как у двусвязного списка отсутствует необходимость в большом непрерывном объеме памяти.
Также могут быть двусторонние очереди «Deque с ограниченным входом» и «Deque с ограниченным выходом», когда на 1 из концов мы не можем вносить или забирать данные.