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