На этом шаге мы рассмотрим список с точки зрения организации стека.
Встроенный в Python тип list создает нормальную стековую структуру данных, поскольку он поддерживает операции вталкивания и выталкивания за амортизируемое O(1) время.
См. документацию Python "Использование списков в качестве стеков": https://docs.python.org/3/tutorial/datastructures.html.
На внутреннем уровне списки Python реализованы как динамические массивы, а значит, при добавлении или удалении элементов им время от времени нужно изменять пространство оперативной памяти для хранящихся в них элементов. Список выделяет избыточную резервную память, с тем чтобы не каждая операция вталкивания и выталкивания требовала изменения размера памяти, и, как результат, для этих операций вы получаете амортизируемую временную сложность O(1).
Недостаток же состоит в том, что это делает показатели их производительности менее надежными, чем стабильные вставки и удаления с временной сложностью O(1), которые обеспечиваются реализацией на основе связного списка (такого, как collections.deque, см. следующий шаг). С другой стороны, списки реально обеспечивают быстрый (со временем O(1)) произвольный доступ к элементам в стеке, и это может быть дополнительным преимуществом.
Используя списки в качестве стеков, необходимо учитывать одно важное предостережение относительно производительности.
Чтобы получить производительность с амортизируемым временем O(1) для вставок и удалений, новые элементы должны добавляться в конец списка методом append() и снова удалятся из конца методом pop(). Для оптимальной производительности стеки на основе списков Python должны расти по направлению к более высоким индексам и сжиматься к более низким.
Добавление и удаление элементов в начале списка намного медленнее и занимает O(n) времени, поскольку существующие элементы должны сдвигаться, чтобы создать место для нового элемента. Такого антишаблона производительности следует избегать.
>>> s = [] >>> s.append('есть') >>> s.append('спать') >>> s.append('программировать') >>> s ['есть', 'спать', 'программировать'] >>> s.pop() 'программировать' >>> s.pop() 'спать' >>> s.pop() 'есть' >>> s.pop() Traceback (most recent call last): . . . . IndexError: pop from empty list
На следующем шаге мы рассмотрим класс collections.deque.
