Что такое стек в python
Стек в 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
Структуры данных организуют хранилище на компьютерах, чтобы мы могли эффективно получать доступ к данным и изменять их. Стеки и очереди – одни из самых ранних структур данных, определенных в информатике.
Их легко изучить и легко реализовать, они широко используются, и вы, скорее всего, обнаружите, что включаете их в свое программное обеспечение для различных задач.
Обычно стеки и очереди реализуются с помощью массива или связанного списка. Мы будем полагаться на структуру данных 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 – основы и примеры
В этом руководстве мы изучим основы стека и реализуем его с помощью кода 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 можно использовать в реальных программах, выбрав любую реализацию метода в соответствии с нашими требованиями. Мы также определили стек со средой потоковой передачи.
Как реализовать стек в 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.
8 структур данных Python
Решая реальные проблемы кодирования, работодатели и рекрутеры стремятся как к эффективности времени выполнения, так и к ресурсоэффективности.
Знание того, какая структура данных лучше всего подходит для текущего решения, повысит производительность программы и сократит время, необходимое для её создания. По этой причине большинству ведущих компаний требуется чёткое понимание структур данных и их тщательное тестирование на собеседовании по кодированию.
Что такое структуры данных?
Структуры данных — это структуры кода для хранения и организации данных, которые упрощают изменение, навигацию и доступ к информации. Структуры данных определяют способ сбора данных, функциональные возможности, которые мы можем реализовать, и отношения между данными.
Структуры данных используются практически во всех областях информатики и программирования, от операционных систем до интерфейсной разработки и машинного обучения.
Структуры данных помогают:
Структуры данных являются жизненно важными строительными блоками для эффективного решения реальных проблем. Структуры данных — это проверенные и оптимизированные инструменты, которые дают вам удобную основу для организации ваших программ. В конце концов, вам не нужно переделывать колесо (или конструкцию) каждый раз, когда это нужно.
У каждой структуры данных есть задача или ситуация, для решения которой она наиболее подходит. Python имеет 4 встроенных структуры данных, списки, словари, кортежи и наборы. Эти встроенные структуры данных поставляются с методами по умолчанию и негласной оптимизацией, которая упрощает их использование.
Большинство структур данных в Python являются их модифицированными формами или используют встроенные структуры в качестве основы.
Теперь давайте посмотрим, как мы можем использовать эти структуры для создания всех сложных структур, которые ищут интервьюеры.
Массивы (списки) в Python
Python не имеет встроенного типа массива, но вы можете использовать списки для всех тех же задач. Массив — это набор значений одного типа, сохранённых под тем же именем.
Каждое значение в массиве называется «элементом», и индексирование соответствует его положению. Вы можете получить доступ к определённым элементам, вызвав имя массива с индексом желаемого элемента. Вы также можете получить длину массива с помощью len()метода.
В отличие от языков программирования, таких как Java, которые имеют статические массивы после объявления, массивы Python автоматически увеличиваются или уменьшаются при добавлении / вычитании элементов.
Например, мы могли бы использовать этот append()метод для добавления дополнительного элемента в конец существующего массива вместо объявления нового массива.
Это делает массивы Python особенно простыми в использовании и адаптируемыми на лету.