Очередь — это еще одна одномерная структура данных. Она напоминает стек, но работает иначе. Вновь прибывшие элементы добавляются в конец, а обрабатываются они начиная с первого.
Вот схематичное изображение очереди. Добавим в нее голубой блок, элемент Blue. Затем добавим зеленый блок, элемент Green. Завершим композицию красным блоком, элементом Red.
Данные из очереди извлекаются последовательно, начиная с самых старых. Сначала будет выбран синий блок, элемент Blue. Операция извлечения данных из очереди называется dequeueing.
Механизм очереди основан на принципе «первым пришел — первым вышел» (FIFO — First In, First Out).
Стеки и очереди работают по строгим правилам. В стеке данные добавляются и удаляются только с одного конца. В очереди же операции происходят с противоположных сторон.
Очереди стали популярны благодаря своей естественности. Они работают по принципу «первым пришел — первым обслужен», что соответствует нашему восприятию времени.
Способы реализации стека
- Сollections.deque
- Queue.Queue
- Создание класса односвязного списка.
COLLECTIONS.DEQUE
Очередь можно реализовать с помощью класса deque из модуля collections. Deque имеет более быстрые операции добавления и извлечения элементов с обоих концов контейнера.
from collections import deque
stack = deque()
# добавление элементов в стек
stack.append(1)
# извлечение и удаление элементов
element = stack.pop()Queue.LifoQueue
from queue import Queue
stack = LifoQueue(maxsize=3)
# добавление элементов в стек
stack.put('a')
# извлечение и удаление элементов
element = stack.get()