что такое стек в питоне

Стек в Python

Чтобы начать работу с этим руководством, вы должны сначала знать, что такое Stack в Python. В основном стек – это структура данных Last-In-First-Out. Это означает, что сначала будет удален элемент, который был введен в систему последним.

Например, предположим, что у вас есть труба только с одним открытым концом. И у вас есть несколько мячей, которые отлично помещаются в трубу. Когда вы вставите эти шары в трубу, они сложатся друг на друга. Однако, когда вы удалите шары, последний будет удален первым.

Вставка стека

Что ж, дополнительной структуры данных в виде стека в python нет. Но поскольку стек – это очень распространенная структура данных, мы постараемся реализовать это.

Итак, если вы уже изучили стек, вы должны знать, что он имеет две операции. Один – push, другой – pop. В этом разделе мы обсудим операцию push. Она используется для добавления элементов в стек. Поскольку мы будем использовать List в качестве стека, мы можем использовать функцию append() для вставки элементов в список.

Результат приведенного выше примера реализации Stack будет таким, как на изображении ниже.

Stack с добавлением pop

Теперь нам нужно научиться извлекать предметы из стека. В списке Python есть функция pop(), которая удаляет последний элемент из списка. Но перед удалением необходимо проверить, пуст ли стек. Итак, если мы добавим реализацию pop к предыдущему коду, то окончательный код будет таким, как показано ниже.

Итак, результат будет таким, как показано ниже.

Реализация

Как видите, мы можем использовать функции List append() и pop() для создания нашего класса реализации Stack. Вот пример реализации класса Stack.

Приведенный выше код будет выводиться следующим образом

Источник

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

Возможно вы что то слышали о стеках и задавались вопросом, что это такое? У вас есть общее представление об этом, но вам интересно, как реализовать стек в Python? Тогда вы пришли в нужное место!

В этой статье вы узнаете:

Это руководство предназначено для питонистов, которые хорошо разбираются в сценариях, знают, что такое списки и как их использовать, и интересуются, как реализовать стек в Python.

Что такое стек?

Стек — это структура данных, в которой элементы хранятся в порядке поступления. Его еще часто называют LIFO (Last-In/First-Out). Это отличается его от очереди, в которой элементы хранятся в порядке «первым пришел / первым обслужен» (FIFO).

Вероятно, проще всего понять стек, если вы представите сценарий использования, с которым вы, вероятно, знакомы: функция отмены (Undo) в вашем редакторе.

Давайте представим, что вы редактируете вашу программу на Python. Сначала вы добавляете новую функцию. Это добавляет новый элемент в стек отмены:

Вы можете видеть, что в стеке теперь есть операция Add Function. После добавления функции вы удаляете слово из комментария. Это также добавляется в стек отмены:

Обратите внимание, как элемент «Delete Word» помещается на вершину стека. Наконец, вы делаете отступ для комментария, чтобы он выстроился правильно:

Вы можете видеть, что каждая из этих команд хранится в стеке отмены, а каждая новая команда помещается сверху. Когда вы работаете со стеком, добавление новых элементов, подобных этому, называется push.

Теперь вы решили отменить все три изменения, поэтому вы нажимаете команду отмены. Далее берется элемент в верхней части стека, который делал отступ для комментария, и удаляется из стека:

Ваш редактор отменяет отступ, а стек отмены теперь содержит два элемента. Эта операция противоположна push и обычно называется pop.

Когда вы снова нажмете кнопку «Отменить», из стека выскочит следующий предмет:

Удалится элемент «Delete Word», оставляя только одну операцию в стеке.

Наконец, если вы нажмете Отменить в третий раз, то последний элемент будет вытолкнут из стека:

Реализация стека в Python

Есть несколько вариантов, когда вы реализуете стек в Python. Эта статья не охватывает все из них, только основные, которые будут соответствовать почти всем вашим потребностям. Мы сосредоточимся на использовании структур данных, которые являются частью библиотеки Python, и не используют сторонних пакетов.

Мы посмотрим на следующие реализации стека:

Использование list для создания стека

Встроенная структура list, которую вы, вероятно, часто используете в своих программах, может использоваться и в качестве стека. Вместо .push() можно использовать .append() для добавления новых элементов в верхнюю часть стека, в то время как .pop() удаляет элементы в порядке LIFO:

В последней команде вы можете видеть, что список вызовет IndexError, если вы вызовете .pop() в пустом стеке.

list имеет преимущество, в том что он прост и вы знаете, как он работает и, вероятно, уже использовали его в своих программах.

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

Если ваш стек становится больше, чем блок памяти, в котором он находится на данный момент, то Python должен сделать некоторое дополнительное выделения памяти. Это может привести к тому, что некоторые вызовы .append() будут занимать намного больше времени, чем другие.

Есть и менее серьезная проблема. Если вы используете .insert() для добавления элемента в ваш стек в позиции, отличной от конца, это может занять гораздо больше времени. Однако обычно это не то, что вы делаете со стеком.

Следующая структура данных поможет вам обойти проблему перераспределения памяти.

Использование collection.deque для создания стека

Модуль collection содержит deque, который полезен для создания стеков. deque переводиться как «колода» и означает «двусторонняя очередь».

Это выглядит почти идентично приведенному выше примеру со списком. В этот момент вам может быть интересно, почему разработчики ядра Python создают две структуры данных, которые выглядят одинаково.

Зачем нужен deque если есть list?

Как вы видели в обсуждении списка выше, он был построен на блоках непрерывной памяти, что означает, что элементы в списке хранятся рядом друг с другом:

Это отлично работает для нескольких операций, таких как индексация в списке. Так получение элемента по индексу myList[3] работает быстро, так как Python точно знает, где искать в памяти. Эта схема памяти также позволяет хорошо работать со срезами списков.

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

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

Добавление новой записи в структуру связанного списка требует только установки ссылки на новую запись так, чтобы она указывала на текущую вершину стека, а затем указывала вершину стека на новую запись:

Однако это постоянное добавление и удаление записей в стеке сопряжено с компромиссом. Получение данных по индексу myDeque[3] медленнее, чем для списка, потому что Python должен пройти через каждый узел списка, чтобы добраться до третьего элемента.

К счастью, вы редко будете выполнять случайную индексацию или использовать срезы в стеке. Большинство операций над стеком будут push или pop.

Операции .append() и .pop() с постоянным временем делают deque отличным выбором для реализации стека Python, если ваш код не использует многопоточность.

Python стеки и многопоточность

Стеки Python могут быть полезны и в многопоточных программах.

Два варианта, которые вы видели до сих пор, list и deque, ведут себя по-разному, если в вашей программе есть потоки.

Начнем с более простого, запомните вы никогда не должны использовать list для какой-либо структуры данных, к которой могут обращаться несколько потоков. Список не является потокобезопасным.

Примечание. Если вам нужно освежить в памяти информацию о безопасности потоков и условиях гонки, ознакомьтесь с Введение в потоки в Python (An Intro to Threading in Python).

Однако, с deque немного иначе. Если вы прочтете документацию по deque, в ней будет четко указано, что обе операции .append() и .pop() являются атомарными, то есть они не будут прерваны другим потоком.

Так что если вы ограничитесь использованием только .append() и .pop(), то у вас не будет проблем с потоками.

Проблема использования deque в многопоточной среде заключается в том, что в этом классе есть и другие методы, которые специально не предназначены для атомарной работы и не являются поточно-ориентированными.

Таким образом, хотя можно создать потокобезопасный стек Python с использованием deque, это подвергает вас опасности тому, что кто-то в будущем злоупотребит им и вызовет условия гонки.

Хорошо, если вы работаете с потоками, вы не можете использовать list для стека и, вероятно, не захотите использовать deque для стека, так как же вы можно построить стек Python для многопоточной программы?

В то время как интерфейс для list и deque похожи, LifoQueue использует .put() и .get() для добавления и удаления данных из стека:

В отличие от deque, LifoQueue разработан так, чтобы быть полностью поточно-ориентированным. Все его методы безопасны для использования в многопоточной среде. Он также добавляет дополнительные тайм-ауты для своих операций, которые часто могут быть обязательной функцией в многопоточных программах.

Однако такая полная безопасность потоков обходится дорого. Чтобы достичь этой безопасности, LifoQueue должен выполнять немного больше работы над каждой операцией, а это значит, что это займет немного больше времени.

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

Стеки Python: какую реализацию следует использовать?

В общем случае, вы должны использовать deque, если вы не используете многопоточность. Если вы используете многопоточность, то вам следует использовать LifoQueue.

Список может быть прост, но его следует избегать, потому что он может иметь проблемы с перераспределением памяти. Интерфейсы для deque и list идентичны, и deque не имеет этих проблем, что делает deque лучшим выбором для вашего непоточного стека Python.

Заключение

Теперь вы знаете, что такое стек, и видели ситуации, когда их можно использовать в реальных программах. Мы оценили три различных варианта реализации стеков и увидели, что deque — отличный выбор для непоточных программ. Если вы реализуете стек в среде многопоточности, то, вероятно, будет хорошей идеей использовать LifoQueue.

Источник

Руководства по структурам данных Python: стек

Как реализовать структуру данных стека (LIFO એ ) в Python, используя только встроенные типы и классы из стандартной библиотеки?

Вот вам аналогия для структуры стековых данных из реальной жизни — стопка пластинок:

Новые пластинки складываются наверх стопки. А поскольку пластинки хрупкие и представляют великую ценность для меломанов, то можно снимать только самую верхнюю пластинку (последний пришел, первый вышел). Чтобы достать пластинку снизу, необходимо одну за другой снять самые верхние пластинки.

Стеки и очереди похожи. Они представляют собой линейные коллекции объектов, а разница заключается в порядке доступа к объектам: в очереди вы удаляете самые ранний добавленный объект (first-in, first-out или FIFO એ ); а в стеке наоборот вы удаляете последний добавленный объект (last-in, first-out или LIFO એ ),

С точки зрения производительности ожидается, что при правильной реализации стека потребуется O(1) времени для вставки и удаления.

Стек используется во многих алгоритмах, от, например, синтаксического анализа языка до управления памятью («стек вызовов»). Короткий и красивый алгоритм с использованием стека — поиск в глубину એ (DFS) в деревьях и графах.

В Python есть несколько реализаций стека, каждая из которых имеет свои особенности. Давайте посмотрим на них:

Cписок — list

По сути, списки являются динамическими массивами и им иногда необходимо изменить размер пространства для хранения элементов при добавлении или удалении. В списке происходит перераспределение памяти, так что не каждый push или pop требует изменения размера, отсюда и получается оценка O(1) для этих операций.

Добавление и удаление в начало происходит намного медленнее и занимает O(n) времени, так как существующие элементы должны быть смещены по кругу для освобождения место для нового элемента.

Класс collections.deque

Поскольку двусторонние очереди одинаково хорошо поддерживает добавление и удаление элементов с обоих концов, то они могут служить и очередями, и стеками.

Объекты deque в Python реализованы в виде двусвязных списков, что дает им отличную и стабильную производительность для вставки и удаления элементов, но низкую производительность O(n) для случайного доступа к элементам в середине стека.

collection.deque — отличный выбор из стандартной библиотеки Python для реализации стека с характеристиками производительности связанного списка.

Класс queue.LifoQueue

Эта реализация стека в стандартной библиотеке Python синхронизирована и обеспечивает семантику блокировки для поддержки нескольких одновременно работающих процессов.

Модуль queue содержит несколько других классов, реализующих многопоточные и многопользовательские очереди, которые полезны для параллельных вычислений.

В зависимости от варианта использования блокировки может оказаться полезной или просто повлечь за собой ненужные накладные расходы. В этом случае вам лучше использовать list или deque в качестве стека общего назначения.

Лучший выбор по умолчанию: collections.deque

Исходя из этих соображений collection.deque является отличным выбором для реализации стека (очереди LIFO) в Python.

В этой статье чего-то не хватает или вы нашли ошибку? Помогите коллеге и оставьте комментарий ниже.

Источник