На этом шаге мы дадим ряд советов по организации стека.
Как вы убедились, Python поставляется с несколькими реализациями стековой структуры данных. Все они обладают слегка различающимися характеристиками, а также компромиссным соотношением производительности и применения.
Если вам не нужна поддержка параллельной обработки (или вы не хотите обрабатывать блокировку и снятие блокировки вручную), то ваш выбор сводится к встроенному типу list или collections.deque. Разница лежит в используемой за кадром структуре данных и общей простоте использования:
- Список list поддерживается динамическим массивом, который делает его отличным выбором для быстрого произвольного доступа, но при этом
требует нерегулярного изменения размеров во время добавления или удаления элементов. Список выделяет излишнюю резервную память, чтобы не каждая
операция вталкивания и выталкивания требовала изменения размеров, и для этих операций вы получаете амортизируемую временную сложность O(1).
Однако вам следует быть внимательными и стараться выполнять вставку и удаление элементов "с правильной стороны", используя методы append() и
pop(). В противном случае производительность замедлится до O(n).
- Двусторонняя очередь collections.deque поддерживается двунаправленным связным списком, который оптимизирует добавления и удаления с
обоих концов и обеспечивает для этих операций стабильную производительность O(1). Производительность класса deque не только стабильнее,
но его также легче использовать, потому что вам не приходится переживать по поводу добавления или удаления элементов "не с того конца".
Резюмируя, можно сказать, что двусторонняя очередь collections.deque представляет собой отличный вариант для реализации стека (очереди LIFO) на Python.
На следующем шаге мы подитожим изученный материал.
