На этом шаге мы рассмотрим особенности использования этого класса для организации очереди.
Класс deque реализует очередь с двусторонним доступом, которая поддерживает добавление и удаление элементов с любого конца за O(1) (неамортизируемое) время. Поскольку двусторонние очереди одинаково хорошо поддерживают добавление и удаление элементов с любого конца, они могут служить в качестве очередей и в качестве стеков.
См. документацию Python "collections.deque": https://docs.python.org/3.6/library/collections.html#collections.deque.
Объекты Python deque реализованы как двунаправленные связные списки (doubly-linked lists).
См. CPython "_collectionsmodule.c": https://github.com/python/cpython/blob/master/Modules/_collectionsmodule.c.
Это придает им превосходную и стабильную производительность для операций вставки и удаления элементов, но при этом плохую O(n) производительность для произвольного доступа к элементам в середине очереди.
Как результат, двусторонняя очередь collections.deque будет хорошим выбором, если вы ищете структуру данных очередь в стандартной библиотеке Python.
>>> from collections import deque >>> q = deque() >>> s.put('есть') >>> s.put('спать') >>> s.put('программировать') >>> q deque(['есть', 'спать', 'программировать']) >>> q.popleft() 'есть' >>> q.popleft() 'спать' >>> q.popleft() 'программировать' >>> q.popleft() Traceback (most recent call last): . . . . IndexError: pop from an empty deque
На следующем шаге мы рассмотрим класс queue.Queue.
