Использование list для создания стека
Встроенная структура list, которую вы, вероятно, часто используете в своих программах, может использоваться и в качестве стека. Вместо .push() можно использовать .append() для добавления новых элементов в верхнюю часть стека, в то время как .pop() удаляет элементы в порядке LIFO:
· >>> 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
В последней команде вы можете видеть, что список вызовет IndexError, если вы вызовете .pop() в пустом стеке.
list имеет преимущество, в том что он прост и вы знаете, как он работает и, вероятно, уже использовали его в своих программах.
К сожалению, у list есть несколько недостатков по сравнению с другими структурами данных. Самая большая проблема заключается в том, что он может столкнуться с проблемами по скорости по мере увеличение размера данных. Элементы в списке хранятся с целью обеспечения быстрого доступа к случайным элементам в списке. На низком уровне это означает, что элементы хранятся рядом друг с другом в памяти.
Если ваш стек становится больше, чем блок памяти, в котором он находится на данный момент, то Python должен сделать некоторое дополнительное выделения памяти. Это может привести к тому, что некоторые вызовы .append() будут занимать намного больше времени, чем другие.
|
|
|
Есть и менее серьезная проблема. Если вы используете .insert() для добавления элемента в ваш стек в позиции, отличной от конца, это может занять гораздо больше времени. Однако обычно это не то, что вы делаете со стеком.
Следующая структура данных поможет вам обойти проблему перераспределения памяти.
Использование collection.deque для создания стека
Модуль collection содержит deque, который полезен для создания стеков. 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
Это выглядит почти идентично приведенному выше примеру со списком. В этот момент вам может быть интересно, почему разработчики ядра Python создают две структуры данных, которые выглядят одинаково.
Зачем нужен deque если есть list?
Как вы видели в обсуждении списка выше, он был построен на блоках непрерывной памяти, что означает, что элементы в списке хранятся рядом друг с другом:
|
|
|
Это отлично работает для нескольких операций, таких как индексация в списке. Так получение элемента по индексу myList[3] работает быстро, так как Python точно знает, где искать в памяти. Эта схема памяти также позволяет хорошо работать со срезами списков.
Непрерывное расположение памяти – причина, по которой списку может потребоваться больше времени для .append() одних объектов, чем других. Если блок смежной памяти заполнен, то ему потребуется получить другой блок, который может занять намного больше времени, чем обычный .append():
deque, с другой стороны, основан на двусвязном списке. В структуре связанного списка каждая запись хранится в своем собственном блоке памяти и имеет ссылку на следующую запись в списке.
Дважды связанный список точно такой же, за исключением того, что каждая запись имеет ссылки как на предыдущую, так и на следующую запись в списке. Это позволяет вам легко добавлять узлы в любой конец списка.
Добавление новой записи в структуру связанного списка требует только установки ссылки на новую запись так, чтобы она указывала на текущую вершину стека, а затем указывала вершину стека на новую запись:
|
|
|
Однако это постоянное добавление и удаление записей в стеке сопряжено с компромиссом. Получение данных по индексу myDeque[3] медленнее, чем для списка, потому что Python должен пройти через каждый узел списка, чтобы добраться до третьего элемента.
К счастью, вы редко будете выполнять случайную индексацию или использовать срезы в стеке. Большинство операций над стеком будут push или pop.
Операции .append() и .pop() с постоянным временем делают deque отличным выбором для реализации стека Python, если ваш код не использует многопоточность.
Дата добавления: 2022-12-03; просмотров: 27; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!