Как реализовать стек Python

>>> myStack = []

>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')

>>> myStack
['a', 'b', 'c']

>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'

>>> myStack.pop()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
IndexError: pop from empty list


В последней команде вы можете видеть, что list вызовет IndexError, если вы вызовете .pop() в пустом стеке.
list преимущество этого метода в том, что он хорошо знаком. Вы знаете, как он работает, и, вероятно, уже использовали его в своих программах.
К сожалению, list имеет несколько недостатков по сравнению с другими структурами данных, которые вы рассмотрите. Самая большая проблема заключается в том, что по мере роста производительности могут возникнуть проблемы со скоростью. Элементы в list хранятся с целью обеспечения быстрого доступа к случайным элементам в list. На высоком уровне это означает, что элементы хранятся в памяти рядом друг с другом.
Если ваш стек становится больше, чем объем занимаемого в данный момент блока памяти, то Python должен выполнить некоторое распределение памяти. Это может привести к тому, что некоторые вызовы .append() будут выполняться намного дольше, чем другие.
Существует и менее серьезная проблема. Если вы используете .insert() для добавления элемента в свой стек в позиции, отличной от конца, это может занять гораздо больше времени. Однако обычно это не то, что вы бы сделали со стеком.
Следующая структура данных поможет вам обойти проблему перераспределения, с которой вы столкнулись при list.
Использование collections.deque для создания стека Python
Модуль collections содержит deque,, который полезен для создания стеков Python. deque произносится как “колода” и расшифровывается как “двусторонняя очередь.”
Вы можете использовать те же методы для deque, что и для list, .append(), и .pop():

>>> from collections import deque
>>> myStack = deque()

>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')

>>> myStack
deque(['a', 'b', 'c'])

>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'

>>> myStack.pop()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
IndexError: pop from an empty deque


Это выглядит почти так же, как в примере list, приведенном выше. На этом этапе вам может быть интересно, почему разработчики ядра Python создали две структуры данных, которые выглядят одинаково.
Зачем нужны deque и list?
Как вы видели в обсуждении list выше, он был построен на блоках непрерывной памяти, что означает, что элементы в списке хранятся рядом друг с другом:

Это отлично работает для нескольких операций, таких как индексация в list. Получение myList[3] происходит быстро, поскольку Python точно знает, где искать в памяти, чтобы найти это. Такое расположение памяти также позволяет фрагментам хорошо работать со списками.
Расположение непрерывной памяти является причиной того, что list для .append() некоторых объектов может потребоваться больше времени, чем для других. Если блок непрерывной памяти заполнен, то ему нужно будет получить другой блок, что может занять гораздо больше времени, чем обычный .append():

deque, с другой стороны, он построен на основе двусвязного списка. В структуре связанного списка каждая запись хранится в отдельном блоке памяти и содержит ссылку на следующую запись в списке.
Двусвязный список ничем не отличается, за исключением того, что каждая запись содержит ссылки как на предыдущую, так и на следующую запись в списке. Это позволяет легко добавлять узлы в любой конец списка.
Для добавления новой записи в структуру связанного списка требуется только установить ссылку на новую запись так, чтобы она указывала на текущую вершину стека, а затем указать вершину стека на новую запись:

Однако это постоянное добавление и удаление записей в стек требует компромисса. Получение myDeque[3] выполняется медленнее, чем для списка, потому что Python должен пройти через каждый узел списка, чтобы добраться до третьего элемента.
К счастью, вам редко требуется выполнять случайную индексацию или разбиение на части в стеке. Большинство операций со стеком выполняются либо push, либо pop.
 Операции с постоянным временем .append() и .pop() делают deque отличным выбором для реализации стека Python, если ваш код не использует многопоточность.
Стеки и многопоточность Python
Стеки Python также могут быть полезны в многопоточных программах, но если вы не заинтересованы в многопоточности, то можете смело пропустить этот раздел и перейти к краткому изложению.
Два варианта, которые вы видели до сих пор, list и deque ведут себя по-разному, если в вашей программе есть потоки.
Начнем с более простого: вы никогда не должны использовать list для любой структуры данных, к которой могут обращаться несколько потоков. list не является потокобезопасным.
 Примечание: Если вам нужны дополнительные сведения о потокобезопасности и условиях гонки, ознакомьтесь с Введением к потоковой обработке в Python.
deque однако это немного сложнее. Если вы прочитаете документацию для deque, то в ней четко указано, что обе операции .append() и .pop() являются атомарными, что означает, что они не будут прерваны другим потоком.
Таким образом, если вы ограничитесь использованием только .append() и .pop(), то вы будете потокобезопасны.
Проблема, связанная с использованием deque в многопоточной среде, заключается в том, что в этом классе есть другие методы, и они специально не предназначены для того, чтобы быть атомарными, и они не являются потокобезопасными.
Таким образом, хотя и возможно создать потокобезопасный стек Python, используя deque, при этом вы рискуете, что кто-то неправильно воспользуется им в будущем и создаст условия гонки.
Хорошо, если вы используете многопоточность, вы не можете использовать list для стека и, вероятно, не хотите использовать deque для стека, так как же  может вы создаете стек Python для многопоточной программы?
Ответ находится в модуле queue, queue.LifoQueue. Помните, как вы узнали, что стеки работают по принципу "Последний вход/первый выход"? Ну, вот что означает часть “Lifo” в LifoQueue.
В то время как интерфейс для list и deque был схож, LifoQueue использует .put() и .get() для добавления и удаления данных из стека:

>>> from queue import LifoQueue
>>> myStack = LifoQueue()

>>> myStack.put('a')
>>> myStack.put('b')
>>> myStack.put('c')

>>> myStack
<queue.LifoQueue object at 0x7f408885e2b0>

>>> myStack.get()
'c'
>>> myStack.get()
'b'
>>> myStack.get()
'a'

>>> # myStack.get() <--- waits forever
>>> myStack.get_nowait()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
  File "/usr/lib/python3.7/queue.py", line 198, in get_nowait
    return self.get(block=False)
  File "/usr/lib/python3.7/queue.py", line 167, in get
    raise Empty
_queue.Empty


В отличие от deque, LifoQueue разработан таким образом, чтобы быть полностью потокобезопасным. Все его методы безопасны для использования в многопоточной среде. Он также добавляет дополнительные тайм-ауты к своим операциям, которые часто могут быть обязательными в многопоточных программах.
Однако за полную потокобезопасность приходится платить. Для достижения этой потокобезопасности LifoQueue приходится выполнять небольшую дополнительную работу над каждой операцией, что означает, что это займет немного больше времени.
Часто это небольшое замедление не влияет на общую скорость работы программы, но если вы измерили свою производительность и обнаружили, что ваши стековые операции являются узким местом, то, возможно, стоит осторожно переключиться на deque.
Я хотел бы еще раз подчеркнуть, что переход с LifoQueue на deque, поскольку это быстрее, без проведения измерений, показывающих, что ваши стековые операции являются узким местом, является примером преждевременной оптимизации. Не делай этого.
Стеки Python: Какую реализацию следует использовать?
В общем, вам следует использовать deque, если вы не используете многопоточность. Если вы используете многопоточность, то вам следует использовать LifoQueue, если только вы не измерили свою производительность и не обнаружили, что небольшое увеличение скорости нажатия и выскакивания будет иметь достаточное значение, чтобы оправдать риски, связанные с обслуживанием.
list может показаться знакомым, но его следует избегать, поскольку это потенциально может привести к проблемам с перераспределением памяти. Интерфейсы для deque и list идентичны, а в deque нет этих проблем, что делает deque лучшим выбором для вашего непоточного стека Python.
Заключение
Теперь вы знаете, что такое стек, и познакомились с ситуациями, когда его можно использовать в реальных программах. Вы оценили три различных варианта реализации стеков и убедились, что deque - отличный выбор для непоточных программ. Если вы реализуете стек в многопоточной среде, то, вероятно, было бы неплохо использовать LifoQueue.
Теперь вы можете:

Определите, когда стек был бы хорошей структурой данных
Выберите, какая реализация подходит для вашей задачи

Если у вас все еще есть вопросы, не стесняйтесь обращаться к нам в комментариях ниже. А теперь приступайте к написанию кода, поскольку вы получили еще один инструмент, который поможет вам решить ваши проблемы с программированием!
<статус завершения article-slug="как реализовать стек python" class="btn-group mb-0" data-api-article-bookmark-url="/api/версия 1/статьи/как реализовать стек python/bookmark/" data-api-article-completion-status-url="/api/v1/articles/how-to-implement-python-stack/completion_status/">



<кнопка поделиться bluesky-text="Интересная статья на #Python от @realpython.com :" email-body="Ознакомьтесь с этой статьей о Python:%0A%0Ah Как реализовать стек Python" email-subject="Статья о Python для вас" twitter-text="Интересная статья о Python от @realpython:" url="https://realpython.com/how-to-implement-python-stack /" url-title="Как реализовать стек Python">

 Смотрите сейчас, к этому уроку прилагается соответствующий видеокурс, созданный командой Real Python. Посмотрите его вместе с письменным руководством, чтобы углубить свое понимание:  Реализация стека в Python

                







                 Back to Top