Б41 Чистый Python. Тонкости программирования для профи. Спб.: Питер

очередью вы удаляете элемент, который был добавлен в нее 
раньше всех (метод «первым пришел — первым ушел», или FIFO); однако 
в случае со 
стеком вы удаляете элемент, который был добавлен в него 
позже всех (метод «последним пришел — первым ушел», или LIFO).
С точки зрения производительности предполагается, что надлежащая 
реализация стека будет занимать O(1) времени на операции вставки 
и удаления.
Стеки находят широкое применение в алгоритмах, например в синтакси-
ческом анализе языка и управлении рабочей памятью времени исполне-
ния («стек вызовов»). Короткий и красивый алгоритм с использованием 
стека представлен поиском в глубину (DFS) на древовидной или графо-
вой структуре данных.
Python поставляется с несколькими реализациями стека, каждая из 
которых имеет слегка отличающиеся характеристики. Сейчас мы их рас-
смотрим и сравним их характеристики.

---

186 Глава 5 • Общие структуры данных Python
list — простые встроенные стеки
Встроенный в Python тип 
list
создает нормальную стековую структуру 
данных, поскольку он поддерживает операции вталкивания и выталкива-
ния за амортизируемое O(1) время
1
.
На внутреннем уровне списки Python реализованы как динамические 
массивы, а значит, при добавлении или удалении элементов им время от 
времени нужно изменять пространство оперативной памяти для храня-
щихся в них элементов. Список выделяет избыточную резервную память, 
с тем чтобы не каждая операция вталкивания и выталкивания требовала 
изменения размера памяти, и, как результат, для этих операций вы полу-
чаете амортизируемую временную сложность O(1).
Недостаток же состоит в том, что это делает показатели их производитель-
ности менее надежными, чем стабильные вставки и удаления с временной 
сложностью O(1), которые обеспечиваются реализацией на основе связ-
ного списка (такого, как 
collections.deque
, см. ниже). С другой стороны, 
списки реально обеспечивают быстрый (со временем O(1)) произвольный 
доступ к элементам в стеке, и это может быть дополнительным преиму-
ществом.
Используя списки в качестве стеков, необходимо учитывать одно важное 
предостережение относительно производительности.
Чтобы получить производительность с амортизируемым временем O(1) 
для вставок и удалений, новые элементы должны добавляться в конец 
списка методом 
append()
и снова удалятся из конца методом 
pop()
. Для 
оптимальной производительности стеки на основе списков Python долж-
ны расти по направлению к более высоким индексам и сжиматься к более 
низким.
Добавление и удаление элементов в начале списка намного медленнее 
и занимает O(n) времени, поскольку существующие элементы должны 
сдвигаться, чтобы создать место для нового элемента. Такого антишаблона 
производительности следует избегать.
1
См. документацию Python «Использование списков в качестве стеков»: 
https://docs .
python .org/3/tutorial/datastructures .html

---

5 .5 . Стеки (с дисциплиной доступа LIFO) 187
>>> s = [] 
>>> s.append('есть') 
>>> s.append('спать') 
>>> s.append('программировать')
>>> s 
['есть', 'спать', 'программировать'] 
>>> s.pop() 
'программировать' 
>>> s.pop() 
'спать' 
>>> s.pop() 
'есть' 
>>> s.pop() 
IndexError: "pop from empty list"
collections .deque — быстрые и надежные стеки
Класс 
deque
реализует очередь с двусторонним доступом, которая под-
держивает добавление и удаление элементов с любого конца за O(1) 
(неамортизируемое) время. Поскольку двусторонние очереди одинаково 
хорошо поддерживают добавление и удаление элементов с любого конца, 
они могут служить и в качестве очередей, и в качестве стеков
1
.
Объекты Python 
deque
реализованы как двунаправленные связные спи-
ски, что дает им стабильную производительность для операций вставки 
и удаления элементов, но при этом плохую O(n) производительность для 
произвольного доступа к элементам в середине очереди
2
.
В целом двусторонняя очередь 
collections.deque
– отличный выбор, 
если вы ищете стековую структуру данных в стандартной библиотеке 
Python, которая обладает характеристиками производительности, ана-
логичными реализации на основе связного списка.
1
См. документацию Python «collections.deque»: 
https://docs .python .org/3 .6/library/collections .
html#collections .deque
2
См. CPython «_collectionsmodule.c»: 
https://github .com/python/cpython/blob/master/Modules/_
collectionsmodule .c

---

188 Глава 5 • Общие структуры данных Python
>>> from collections import deque 
>>> s = deque() 
>>> s.append('есть') 
>>> s.append('спать') 
>>> s.append('программировать')
>>> s 
deque(['есть', 'спать', 'программировать']) 
>>> s.pop()