что такое стек в питоне
Стек в 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: стек
Как реализовать структуру данных стека (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.
В этой статье чего-то не хватает или вы нашли ошибку? Помогите коллеге и оставьте комментарий ниже.
Стек и очередь в Python
Структуры данных организуют хранилище на компьютерах, чтобы мы могли эффективно получать доступ к данным и изменять их. Стеки и очереди – одни из самых ранних структур данных, определенных в информатике.
Их легко изучить и легко реализовать, они широко используются, и вы, скорее всего, обнаружите, что включаете их в свое программное обеспечение для различных задач.
Обычно стеки и очереди реализуются с помощью массива или связанного списка. Мы будем полагаться на структуру данных List для размещения, как стеков, так и очередей.
Как они работают?
Стеки, как следует из названия, следуют принципу Last-in-First-Out (LIFO). Как будто укладывая монеты одна на другую, последняя монета, которую мы кладем на вершину, — это та, которая будет первой удаляться из стопки позже.
Очереди
Очереди, как следует из названия, следуют принципу «первым пришел – первым обслужен» (FIFO). Как будто ожидая в очереди за билетами в кино, первым в очереди встает тот, кто первым покупает билет и наслаждается просмотром.
С использованием списков
Встроенная в Python структура данных List поставляется в комплекте с методами для имитации операций стека и очереди.
Рассмотрим стопку букв:
Мы можем использовать те же функции для реализации очереди. Функция pop необязательно принимает в качестве аргумента индекс элемента, который мы хотим получить.
Таким образом, мы можем использовать pop с первым индексом списка, т.е. 0, чтобы получить поведение, подобное очереди.
Рассмотрим «очередь» фруктов:
Опять же, здесь мы используем операции добавления и извлечения списка для имитации основных операций очереди.
С библиотекой Deque
Python имеет библиотеку deque (произносится как «колода»), которая предоставляет последовательность с эффективными методами для работы в качестве стека или очереди.
deque – это сокращение от Double Ended Queue – обобщенная очередь, которая может получить первый или последний сохраненный элемент:
Более строгие реализации
Если вашему коду нужен стек, а вы предоставляете список, ничто не мешает программисту вызывать функции вставки, удаления или другие функции списка, которые повлияют на порядок вашего стека! Это в корне нарушает суть определения стека, поскольку он больше не работает так, как должен.
Бывают случаи, когда мы хотим убедиться, что с нашими данными могут выполняться только допустимые операции.
Мы можем создавать классы, которые предоставляют только необходимые методы для каждой структуры данных.
Для этого давайте создадим новый файл с именем stack_queue.py и определим два класса:
Программистам, использующим наши стек и очередь, теперь предлагается использовать вместо этого методы, предоставленные для управления данными.
Примеры
Представьте, что вы разработчик, работающий над новым текстовым процессором. Вам поручено создать функцию отмены, позволяющую пользователям отменять свои действия до начала сеанса.
Стек идеально подходит для этого скрипта. Мы можем записывать каждое действие пользователя, помещая его в стек. Когда пользователь хочет отменить действие, он выталкивает его из стека. Мы можем быстро смоделировать эту функцию следующим образом:
Очереди также широко используются в программировании. Подумайте о таких играх, как Street Fighter или Super Smash Brothers. Игроки в этих играх могут выполнять особые движения, нажимая комбинацию кнопок. Эти комбинации кнопок можно сохранить в очереди.
А теперь представьте, что вы разработчик, работающий над новым файтингом. В вашей игре каждый раз, когда нажимается кнопка, запускается событие ввода. Тестировщик заметил, что при слишком быстром нажатии на кнопки игра обрабатывает только первую, а специальные ходы работать не будут!
Вы можете исправить это с помощью очереди. Мы можем ставить в очередь все входные события по мере их поступления. Таким образом, не имеет значения, если входные события происходят с небольшим промежутком времени между ними, все они будут сохранены и доступны для обработки. Когда мы обрабатываем ходы, мы можем удалить их из очереди. Особый ход можно проработать так:
Заключение
Стеки и очереди – это простые структуры данных, которые позволяют нам сохранять и извлекать данные последовательно. В стеке последний элемент, который мы вводим, выходит первым. В очереди первый элемент, который мы вводим, выходит первым.
Мы можем добавлять элементы в стек с помощью операции push и извлекать элементы с помощью операции pop. С очередями мы добавляем элементы с помощью операции постановки в очередь и получаем элементы с помощью операции постановки из очереди.
В Python мы можем реализовать стеки и очереди, просто используя встроенную структуру данных List. Python также имеет библиотеку deque, которая может эффективно предоставлять операции стека и очереди в одном объекте. Наконец, мы создали классы стека и очереди для более жесткого контроля над нашими данными.
Существует множество реальных вариантов использования стеков и очередей, понимание которых позволяет нам легко и эффективно решать многие проблемы с хранением данных.
Реализация стека на Python
На собеседовании вам вполне могут предложить написать код для реализации стека или очереди. Да, на работе вам, вероятно, за всю карьеру не случится этого делать, но задачи для вайтбоардинга отличаются своей нежизненностью. Несмотря на это, такие задачи — отличный способ продемонстрировать, что вы умеете реализовывать классы (т. е. создавать вещи, которые делают то, что вы сказали им делать).
Концепции стеков и очередей довольно простые. Стек (англ. stack — стопка) похож на стопку тарелок. Если у вас есть такая стопка, убирать тарелки вы будете, начиная сверху. Таким образом, последняя тарелка, которую вы положили на стопку, будет убрана первой. Вероятно, вы слышали термин LIFO — Last In First Out («последним пришел, первым ушел»).
А в очередях все наоборот: первый элемент в очереди удаляется тоже первым. Представьте себе очередь в Starbucks. Первый человек в очереди всегда получает свой кофе первым.
Создаем стек на Python
Итак, давайте рассмотрим упрощенный пример задачи, которую вам могут дать на техническом собеседовании. Советуем параллельно с чтением писать этот код в своем редакторе.
Задача начинается со слова «Реализуйте». Это намекает на то, что от вас ожидается создание класса. Если вы не привыкли еще работать с классами, можете считать их чем-то вроде шаблона объекта. При инициации нового объекта класса Stack он будет иметь все свойства и методы, которые мы определим для этого класса.
Но погодите! У нас есть проблема. Что, если в стеке не останется элементов для удаления? К счастью, в условии задачи нам напомнили о такой ситуации:
Вот и все! Повторим:
Марк Лутц «Изучаем Python»
Скачивайте книгу у нас в телеграм
Проверка нашего стека
Надеемся, вы не только читали статью, но и параллельно писали этот код. Но в таком случае вы, вероятно, заметили, что при его запуске ничего не происходит.
Итак, вы реализовали свой первый стек на Python. Можно сказать, изучили свою первую структуру данных.
Бонус: интеграция метода max()
Подобная задача давалась кандидату на интервью в Amazon. Но там запрашивался еще один дополнительный метод:
И в конце мы будем возвращать значение, которое удалили из стека. Целиком наш метод будет выглядеть так:
Стек в Python – основы и примеры
В этом руководстве мы изучим основы стека и реализуем его с помощью кода Python.
Что такое стек в Python?
Стек в Python – это линейная структура данных, в которой данные расположены объектами друг над другом. Он хранит данные в режиме LIFO (Last in First Out). Данные хранятся в том же порядке, в каком на кухне тарелки располагаются одна над другой. Мы всегда выбираем последнюю тарелку из стопки тарелок. В стеке новый элемент вставляется с одного конца, и элемент может быть удален только с этого конца.
Простым примером стека является функция «Отменить» в редакторе. Функция отмены работает с последним выполненным нами событием. Мы можем выполнять две операции в стеке – PUSH и POP. Операция PUSH – это когда мы добавляем элемент, а операция POP – когда мы удаляем элемент.
Методы стека
Python предоставляет следующие методы, которые обычно используются со стеком.
Реализация
Python предлагает различные способы реализации стека. В этом разделе мы обсудим реализацию с использованием Python и его модуля. Мы можем реализовать стек на Python следующими способами:
Реализация с использованием списка
Список Python можно использовать как стек. Он использует метод append() для вставки элементов, где стек использует метод push(). В списке также есть метод pop() для удаления последнего элемента.
Но в списке есть недостаток: он становится медленнее по мере роста. Новый элемент в нем хранится рядом с другим. Если список растет и выходит за пределы блока памяти, Python выделяет некоторую память. Вот почему список становится медленным. Разберем на примере –
В приведенном выше коде мы определили пустой список. Мы вставляли элементы один за другим, используя метод append(), похожий на метод push(). Мы также удалили элементы с помощью метода pop(), который возвращает последний элемент списка.
С использованием collection.deque
Модуль коллекции предоставляет класс deque, который используется для создания стеков Python. Deque произносится как «колода», что означает «двусторонняя очередь». Двухсторонняя очередь может быть предпочтительнее списка, поскольку она выполняет операции добавления и извлечения быстрее, чем список. Временная сложность – O (1), где список занимает O (n).
Приведенный выше код почти аналогичен предыдущему примеру. Однако единственная разница в том, что мы импортировали двухстороннюю очередь из модуля коллекции.
Сравнение Deque и список
Список хранит элементы рядом друг с другом и использует непрерывную память. Это наиболее эффективно для нескольких операций, таких как индексация в списке. Например, получение list1 [2] выполняется быстро, поскольку Python знает точное положение определенного элемента. Непрерывная память также позволяет хорошо работать со списками.
Список требует больше времени, чтобы добавить некоторые объекты, чем другие. Если блок непрерывной памяти заполнен, он получит другой блок, который может занять гораздо больше времени, чем обычная функция append().
Модуль LifeQueue
Модуль очереди имеет очередь LIFO, которая совпадает со стеком. Обычно очередь использует метод put() для добавления данных и метод () для получения данных.
Ниже приведены несколько методов, доступных в очереди.
Выше мы импортировали модуль очереди, который является LIFOqueue. Он работает так же, как стек, но этот модуль включает некоторые дополнительные функции, упомянутые выше. Мы определили стек с максимальным размером, что означает, что он может содержать максимум пять значений в нем.
Начальный размер массива равен нулю; мы поместили три элемента в стек с помощью метода put(). Теперь мы снова проверили, пуст ли стек и его размер. Мы имеем три элемента. Выдвинем элемент с помощью метода get(). Сначала удаляется последний добавленный элемент. После удаления всех элементов получаем пустой стек.
Стеки и потоки Python
Мы также можем использовать стек Python в многопоточной программе. Это сложная тема, но она используется не часто, поэтому вы можете пропустить этот раздел, если вас не интересует многопоточность.
Список и двухсторонняя очередь ведут себя по-разному, если мы используем многопоточность в нашей программе. Использование списка в многопоточном программировании не является потокобезопасным.
С другой стороны, двухсторонняя очередь немного сложна, потому что ее методы append() и pop() являются атомарными, что означает, что они не будут прерываться другим потоком.
Мы можем построить многопоточную программу, используя двухстороннюю очередь, но это может вызвать некоторые сложности в будущем. Теперь возникает вопрос, как мы можем построить программу из стека Python с потоковой передачей.
Ответ заключается в том, что мы можем использовать LIFOqueue, и мы знаем, что LIFO означает Last In First Out. Он использует put() и gets() для добавления и удаления элемента стека.
Какую реализацию стека следует рассмотреть?
Мы упомянули три метода реализации стека в Python. Вышеупомянутые методы имеют свои преимущества или недостатки.
Давайте устраним путаницу; если мы используем стек с потоковой передачей, то должны использовать Lifoqueue, но убедившись в его производительности для вытеснения и удаления элементов. Но если мы не используем потоки, то применяем двухстороннюю очередь.
Мы также можем использовать список для реализации стека, но он может иметь потенциальные проблемы с перераспределением памяти. Список и двухсторонняя очередь одинаковы в интерфейсе, но двухсторонняя очередь не имеет проблем с распределением памяти.
Заключение
Мы вкратце определили стек и его реализацию. Стек Python можно использовать в реальных программах, выбрав любую реализацию метода в соответствии с нашими требованиями. Мы также определили стек со средой потоковой передачи.