Как сделать стек. Реализация стека на Python: эффективные методы и примеры кода

Как реализовать стек в Python. Какие методы нужны для работы со стеком. Как выбрать оптимальную структуру данных для стека. Примеры кода для push, pop и других операций со стеком.

Что такое стек и зачем он нужен

Стек — это абстрактная структура данных, работающая по принципу «последним пришел — первым вышел» (LIFO — Last In, First Out). Основные операции со стеком:

• push — добавление элемента на вершину стека
• pop — удаление элемента с вершины стека
• peek — просмотр верхнего элемента без его удаления

Стеки используются во многих алгоритмах и приложениях, например:

• Отмена действий в редакторах
• Обход дерева в глубину
• Вызовы функций в языках программирования
• Проверка корректности скобочных последовательностей

Реализация стека в Python позволяет эффективно решать подобные задачи.

Варианты реализации стека в Python

Существует несколько способов реализовать стек на Python:

1. На основе списка (list)
2. С помощью collections.deque
3. Через queue.LifoQueue
4. Создание собственного класса

Давайте рассмотрим плюсы и минусы каждого подхода.

Реализация стека на основе списка

Самый простой способ — использовать встроенный тип list:

«`python class Stack: def __init__(self): self.items = [] def is_empty(self): return len(self.items) == 0 def push(self, item): self.items.append(item) def pop(self): if not self.is_empty(): return self.items.pop() raise IndexError(«Stack is empty») def peek(self): if not self.is_empty(): return self.items[-1] raise IndexError(«Stack is empty») def size(self): return len(self.items) «`

Преимущества такой реализации:

• Простота и понятность кода
• Использование встроенных методов списка

Недостатки:

• При увеличении размера может потребоваться перераспределение памяти
• Не потокобезопасна

Реализация на основе collections.deque

Более эффективный вариант — использовать двустороннюю очередь deque:

«`python from collections import deque class Stack: def __init__(self): self.items = deque() def is_empty(self): return len(self.items) == 0 def push(self, item): self.items.append(item) def pop(self): if not self.is_empty(): return self.items.pop() raise IndexError(«Stack is empty») def peek(self): if not self.is_empty(): return self.items[-1] raise IndexError(«Stack is empty») def size(self): return len(self.items) «`

Преимущества deque:

• Эффективнее при добавлении/удалении с обоих концов
• Не требует перераспределения памяти при росте

Недостатки:

• Немного сложнее в использовании, чем обычный список
• Все еще не потокобезопасна

Потокобезопасная реализация с queue.LifoQueue

Для многопоточных приложений лучше использовать LifoQueue:

«`python from queue import LifoQueue class Stack: def __init__(self): self.items = LifoQueue() def is_empty(self): return self.items.empty() def push(self, item): self.items.put(item) def pop(self): if not self.is_empty(): return self.items.get() raise IndexError(«Stack is empty») def peek(self): if not self.is_empty(): item = self.items.get() self.items.put(item) return item raise IndexError(«Stack is empty») def size(self): return self.items.qsize() «`

Основные преимущества:

• Потокобезопасность
• Встроенные методы для работы со стеком

Недостатки:

• Меньшая производительность в однопоточных приложениях
• Отсутствие метода peek, требуется дополнительная реализация

Оптимальный выбор реализации стека

Какую реализацию выбрать? Это зависит от конкретной задачи:

• Для простых однопоточных приложений подойдет реализация на основе списка или deque
• Для сложных или многопоточных систем лучше использовать LifoQueue
• При необходимости специфичной функциональности можно создать собственный класс

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

Примеры использования стека

Рассмотрим несколько практических примеров использования стека в Python.

Проверка сбалансированности скобок

Задача: проверить, сбалансированы ли скобки в выражении. Например, «{[()]}» — сбалансировано, а «{[(])}» — нет.

«`python def is_balanced(expression): stack = [] opening = «({[» closing = «)}]» pairs = {«)»: «(«, «}»: «{«, «]»: «[«} for char in expression: if char in opening: stack.append(char) elif char in closing: if not stack or stack.pop() != pairs[char]: return False return len(stack) == 0 # Примеры использования print(is_balanced(«{[()]}»)) # True print(is_balanced(«{[(])}»)) # False print(is_balanced(«((()))»)) # True print(is_balanced(«((()»)) # False «`

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

Реализация функции отмены действий

Стек отлично подходит для реализации функции отмены действий в различных приложениях. Рассмотрим простой пример текстового редактора:

«`python class TextEditor: def __init__(self): self.text = «» self.undo_stack = [] def add_text(self, new_text): self.undo_stack.append(self.text) self.text += new_text def delete_last_char(self): if self.text: self.undo_stack.append(self.text) self.text = self.text[:-1] def undo(self): if self.undo_stack: self.text = self.undo_stack.pop() # Пример использования editor = TextEditor() editor.add_text(«Hello») editor.add_text(» World») print(editor.text) # «Hello World» editor.delete_last_char() print(editor.text) # «Hello Worl» editor.undo() print(editor.text) # «Hello World» editor.undo() print(editor.text) # «Hello» «`

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

Оптимизация производительности стека

При работе с большими объемами данных важно оптимизировать производительность стека. Вот несколько советов:

• Используйте collections.deque вместо списка для лучшей производительности при частых операциях push/pop
• Избегайте использования list.insert(0, item) для добавления элементов в начало списка, так как это имеет сложность O(n)
• Если вы знаете максимальный размер стека заранее, используйте фиксированный массив для экономии памяти
• Для очень больших стеков рассмотрите возможность использования внешней памяти или базы данных

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

Заключение

Стек — это мощная и гибкая структура данных, которая находит применение во многих областях программирования. Python предоставляет несколько способов реализации стека, каждый со своими преимуществами и недостатками. Выбор конкретной реализации зависит от требований вашего проекта.

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

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

Spread the love

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стек отмены теперь пуст. Повторное нажатие кнопки «Отменить» после этого не даст никакого эффекта, поскольку ваш стек отмены пуст, по крайней мере, в большинстве редакторов. Вы увидите, что произойдет, когда вы вызовете .pop() для пустого стека в описании реализации ниже.

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

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

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

• list
• collections. deque
• queue.LifoQueue

Использование 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, если ваш код не использует многопоточность.

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

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

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

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

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

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

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

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

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

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

Ответ находится в модуле очереди, 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.

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

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

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

Заключение

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

Теперь вы можете:

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

Оригинальная статья: Jim Anderson  How to Implement a Python Stack

Была ли вам полезна эта статья?

[20 / 3. 7]

Spread the love

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

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

Концепции стеков и очередей довольно простые. Стек (англ. stack — стопка) похож на стопку тарелок. Если у вас есть такая стопка, убирать тарелки вы будете, начиная сверху. Таким образом, последняя тарелка, которую вы положили на стопку, будет убрана первой. Вероятно, вы слышали термин LIFO — Last In First Out («последним пришел, первым ушел»).

А в очередях все наоборот: первый элемент в очереди удаляется тоже первым. Представьте себе очередь в Starbucks. Первый человек в очереди всегда получает свой кофе первым.

Создаем стек на Python

Итак, давайте рассмотрим упрощенный пример задачи, которую вам могут дать на техническом собеседовании. Советуем параллельно с чтением писать этот код в своем редакторе.

 # Реализуйте стек со следующими методами:
 # 1. push(item), добавляющий элемент на вершину стека
 # 2. pop(), удаляющий самый верхний элемент стека и возвращающий его.
 # Если в стеке нет элементов, метод должен выбросить ошибку или вернуть null.
 # Каждый метод должен иметь постоянную временную сложность.

Задача начинается со слова «Реализуйте». Это намекает на то, что от вас ожидается создание класса. Если вы не привыкли еще работать с классами, можете считать их чем-то вроде шаблона объекта. При инициации нового объекта класса Stack он будет иметь все свойства и методы, которые мы определим для этого класса.

Начнем с определения класса, а затем добавим метод __init__. Кроме того мы добавим пустые методы pop() и push(). Ключевое слово pass нужно только для того, чтобы Python не ругался на наличие пустых методов.

class Stack:
    def __init__():
        pass
    def pop():
        pass
    def push():
        pass

Отлично, теперь у нас есть класс Stack. Давайте определим метод __init__, который будет устанавливать все свойства стека при инициализации. То есть, при рождении каждого нового стека мы будем наделять его кое-чем. Есть идеи, чем именно?

Стек по сути своей — список (в Python массивы называются списками) с особыми свойствами: вы можете добавлять или удалять только самый недавний элемент. Исходя из этого, мы представим стек как список и назовем его stack. Чтобы определить свойство класса, в Python используется ключевое слово self. Для доступа к этому ключевому слову его нужно передать в качестве аргумента в метод.

def __init__(self):
    self.stack = []

Хорошо, теперь давайте перейдем к методу push(). Он тоже будет принимать self в качестве аргумента, чтобы мы могли иметь доступ к только что определенной переменной stack. Кроме того, он будет принимать item — элемент, который мы хотим добавить на вершину стека.

def push(self, item):
    pass

При добавлении и удалении элементов из стека его вершиной будем считать конец списка. В Python это все облегчает, поскольку мы можем использовать метод .append() для добавления элемента в конец списка:

def push(self, item):
    self.stack.append(item)

Метод pop() будет аналогичным. В Python есть метод .pop(), удаляющий последний элемент списка. Очень удобно! Этот метод возвращает удаляемый элемент. Мы будем сохранять этот элемент в переменную removed, а затем возвращать переменную.

def pop(self):
    removed = self.stack.pop()
    return removed

Но погодите! У нас есть проблема. Что, если в стеке не останется элементов для удаления? К счастью, в условии задачи нам напомнили о такой ситуации:

 # Если в стеке нет элементов, метод должен выбросить ошибку или вернуть null.

Все, что нам нужно сделать, это добавить условное выражение для проверки этого крайнего случая. Для этого перед запуском .pop мы добавим предложение if, проверяющее, не пуст ли стек. Единственный тип null в Python — это None, так что его мы и вернем, если стек все же пуст.

def pop(self):
    if len(self. stack) == 0:
        return None
    removed = self.stack.pop()
    return removed

Вот и все! Повторим:

class Stack:
    def __init__(self):
        self.stack = []
    def push(self, item):
        self.stack.append(item)
    def pop(self):
        if len(self.stack) == 0:
            return None
        removed = self.stack.pop()
        return removed

Есть еще одна вещь, на которую следует обратить внимание. Все наши методы должны иметь постоянную временную сложность — O(1). Это означает, что их работа должна занимать одинаковое время, независимо от длины стека. Если бы нам пришлось, к примеру, перебирать список в цикле, временная сложность была бы O(n), где n — длина списка. Но нам ничего такого делать не пришлось, так что все в порядке.

[python_ad_block]

Проверка нашего стека

Надеемся, вы не только читали статью, но и параллельно писали этот код. Но в таком случае вы, вероятно, заметили, что при его запуске ничего не происходит.

Как уже было сказано, классы — это своего рода шаблоны объектов. Мы создали шаблон. Теперь давайте проверим его, создав объект. Вы можете это сделать или в оболочке Python, или внизу вашего файла stack.py. Для простоты назовем стек s.

>>> s = Stack()

Теперь давайте протестируем наш прекрасный метод push(), добавив в стек несколько чисел.

>>> s. push(1)
>>> s.push(2)
>>> s.push(3)

Если мы выведем наш s.stack, мы получим [1, 2, 3]. Отлично. Давайте теперь проверим метод pop().

>>> s.pop()

Если мы теперь выведем s.stack, мы получим [1, 2]. Обратите внимание, что удалился только последний элемент, при этом вернулось значение 3. Но что будет, если мы продолжим удалять элементы? Нам нужно увидеть, вернет ли наш метод None. Для этого мы повторим ту же команду несколько раз, а затем выведем значение return.

>>> s.pop()
>>> s. pop()
>>> print(s.pop())

Итак, вы реализовали свой первый стек на Python. Можно сказать, изучили свою первую структуру данных.

Бонус: интеграция метода max()

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

 # 3. max(), возвращающий максимальное значение в стеке на данный момент.
 # Если в стеке нет элементов, метод должен выбросить ошибку или вернуть null.

Чтобы это сработало, нам нужно кое-что изменить в нашем классе Stack. Начнем с __init__. Давайте добавим переменную max для отслеживания максимального значения в стеке. Условие предлагает нам вернуть нулевое значение, если стек пуст. Поэтому мы инициализируем переменную как None.

def __init__(self):
    self. stack = []
    self.max = None

Круто. Теперь давайте обновим метод push(). Нам нужно проверить два варианта:

1. Является ли этот элемент первым элементом, добавляемым в стек. В этом случае текущее значение max — None, и нам нужно инициализировать переменную первым добавляемым значением.
2. Если max уже имеет какое-то значение, нам нужно сравнить его со значением добавляемого элемента и соответственно обновить.

В обоих случаях мы будем устанавливать новое значение max для добавляемого элемента. Это удачный момент для применения однострочного условия с or.

def push(self, item):
    self.stack.append(item)
    if len(self.stack) == 1 or item > self.max:
        self.max = item

А теперь давайте взглянем на pop(). Опять же, нам нужно проверить два варианта:

1. Является ли удаляемый элемент последним в стеке. Если стек пуст, нужно установить max в None.
2. Если удаляемый элемент равен значению max, нужно перебрать в цикле список и найти новое значение.

С первым случаем все просто. После вызова .pop() для списка мы проверяем, стала ли длина списка равной нулю.

if len(self.stack) == 0:
    self.max = None

Для проверки второго случая мы используем цикл for. Начнем с установки для max значения, которое, как мы знаем, уже есть в стеке, — первого значения. Затем переберем в цикле весь список и сверим каждое значение с первым. Если значение будет больше self.max, будем обновлять self. max новым, большим значением.

elif removed == self.max:
    self.max = self.stack[0]
    for value in self.stack:
        if value > self.max:
            self.max = value

И в конце мы будем возвращать значение, которое удалили из стека. Целиком наш метод будет выглядеть так:

def pop(self):
    if len(self.stack) == 0:
        return None
    removed = self.stack.pop()
    if len(self.stack) == 0:
        self.max = None
    elif removed == self.max:
        self.max = self.stack[0]
        for value in self.stack:
            if value > self.max:
                self.max = value
    return removed

Наконец, давайте реализуем метод max(). Назначение этого метода — просто возвращать значение определенной нами переменной max. Но в Python мы можем просто получить доступ к этому значению вне определения класса, вызвав s.max. Зачем же нам писать целый метод, чтобы просто вернуть его?

Это пережиток объектно-ориентированного программирования на Java. Традиционно считается best practice делать все переменные приватными. Если бы вы создавали, скажем, радио, вы бы не захотели, чтобы пользователи копались в проводах. Пользователь должен пользоваться регуляторами и кнопками снаружи. В Java вы бы инициализировали поле max ключевым словом private. Затем вы бы написали метод max или get_max(), возвращающий это значение, и это был бы единственный способ доступа к нему.

В Python мы можем делать переменные приватными, просто определяя их с двойным символом подчеркивания перед именем: __max. Хотите ли вы это делать, зависит от вас. На интервью лучше спросить интервьюера, чего он ждет. Тот факт, что вы вообще зададите этот вопрос, сам по себе будет говорить в вашу пользу. К тому же, в итоге вы сделаете именно то, что от вас ожидалось.

Итак, мы имеем:

class Stack:
    def __init__(self):
        self.stack = []
        self.max = None
    def pop(self):
        if len(self.stack) == 0:
            return None
        removed = self.stack.pop()
        if len(self.stack) == 0:
            self.max = None
        elif removed == self.max:
            self.max = self.stack[0]
            for value in self.stack:
                if value > self.max:
                    self.max = value
        return removed
    def push(self, item):
        self.stack.append(item)
        if len(self.stack) == 1 or item > self.max:
            self.max = item
    def get_max(self):
        return self. max

Теперь можно протестировать наш код, добавляя и удаляя элементы и проверяя при этом, правильно ли обновляется переменная max.

>>> s = Stack()
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> s.max
3
>>> s.pop()
3
>>> s.max
2

Создание стека в Python

Предварительные требования: Python
Версии: Python 3.8

Введение

В информатике стек представляет собой набор элементов данных. Модель доступа по принципу «вошел-первый-вышел» (LIFO).

Существуют две основные операции для этой структуры данных:

• Функция .push() , которая добавляет элемент в стек.
• Функция .pop() , которая удаляет последний добавленный элемент в стек.

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

Планирование реализации нашего стека

Прежде чем мы начнем, нам нужно решить, какие возможности нам нужны в нашей реализации стека. Функции .push() и .pop() соответствуют минимальным требованиям. Но нам также может понадобиться следующее:

• Функция Python len() , чтобы сообщить нам, сколько элементов находится в стеке, и предупредить нас, когда стек пуст. Хорошей практикой является проверка наличия пустого стека при использовании его в программе.
• Функция .peek() , сообщающая нам значение верхнего элемента стека без его удаления.

Наконец, мы хотим решить, как будут вести себя методы . peek() или .pop() , когда они вызываются для пустого стека. Мы могли бы вернуть что-то вроде NaN , но это может привести к незначительным ошибкам в дальнейшем, особенно если в стек добавляется значение NaN . Лучшей практикой в ​​этом сценарии является создание исключения, когда мы пытаемся использовать эти функции в пустом стеке. Таким образом, такое событие может быть перехвачено во время тестирования, и код, использующий стек, может быть соответствующим образом обновлен.

Начинаем создавать класс стека

Наш стек будет классом Python. Как только мы объявим наш класс, первое, что мы хотим добавить, — это контейнер для хранения элементов в нашем стеке. Для этого мы создаем внутреннюю переменную:

 
 
 class stack: 
 
 def __init__(self): 
 
 self.__index = [] 
 

При инициализации нашего стека класс инициализируется __index переменная как пустой список. Этот список будет содержать элементы в нашем стеке.

Настройка функции

len()

Сначала мы настроим функцию len() для нашего класса, так как мы хотим проверить ее перед использованием наших .pop() и . peek() метода. Мы сделаем это, реализуя «магический» метод, также называемый методом Dunder (двойное подчеркивание). Методы Dunder позволяют нам переопределить поведение встроенных операций Python. Для нашего стека мы можем использовать метод len() Dunder, чтобы установить необходимое поведение «длины»:

 
 
 Стек класса: 
 
 def __init __ (Self): 
 
 Self .__ index = [] 
 
 def __len __ (self): 
 
 return len (self .__ ____) 
 

Теперь, когда мы вызов

9002

, когда мы вызов We Self

, когда мы вызов

, когда мы вызов

. len(stack_instance) , он вернет количество элементов в нашей переменной __index .

 
 
 >>> s = stack() 
 
 >>> # сюда идут некоторые дополнительные операции со стеком 
 
 >>> len(s) # выборка количества элементов в стеке 
 
 2 
 

Настройка метода

.push()

Далее мы хотим настроить наш метод .push() , который будет размещать элементы в нашей переменной __index . Поскольку __index — это список, наше основное решение будет заключаться в том, в какой «конец» списка мы должны вставлять наши элементы.

Первым импульсом может быть добавление элементов в наш список __index , поскольку мы обычно думаем, что элемент с самым высоким индексом является «верхним». Однако такой подход может быть проблематичным для наших целей. Это связано с тем, что наша ссылка, «верхний» индекс, всегда будет меняться, когда мы выполняем операции в нашем стеке. Кроме того, это значение нужно будет пересчитывать каждый раз, когда мы на него ссылаемся.

Более эффективно добавлять и удалять элементы из «начала» нашего списка, так как индекс «начала» никогда не меняется. Он всегда будет равен нулю. Следовательно, наша переменная __index будет упорядочена с «верхним» элементом в качестве первого элемента нашего списка. Поскольку мы работаем со списком Python, это можно сделать с помощью встроенного метода .insert() :

 
 
 class stack: 
 
 def __init__(self): 
 
 self.__index = [] 
 
 по определению __len__(я): 
 
 return len(self.__index) 
 
 def push(self,item): 
 
 self.__index.insert(0,item) 
 

Настройка метода

.peek()

2 . peek() довольно прост. Он возвращает «верхнее» значение стека, которое относится к первому элементу в нашем списке, __index[0] . Однако нам нужно принять во внимание возможность того, что наш список пуст. Мы хотим проверить наш стек с помощью функции len() и выдать исключение, если мы пытаемся использовать . peek() в пустом стеке:

 
 
 стек класса: 
 
 def __init__(self): 
 
 self.__index = [] 
 
 def __len__(self): 
 return_index 
_ ) 
 
 def push(self,item): 
 
 self.__index.insert(0,item) 
 
 def peek(self): 
 
 if len(self) == 0: 
 
 поднять Exception("peek( ) вызывается из пустого стека.") 
 
 return self.__index[0] 
 

Настройка

.pop() 9Метод 0022

Метод .pop() точно такой же, как и метод .peek() с дополнительным шагом удаления возвращаемого элемента из стека. Как и .peek() , мы хотим проверить пустой список перед попыткой вернуть значение:

 
 
 class stack: 
 
 def __init__(self): 
 
 self.__index = [] 
 
 def __len__(self): 
 
 return len(self.__index) 
 
 def push(self,item): 
 
 self.__index.insert(0,item) 
 
 def peek(self): 
 
 if len(self) == 0: 
 
 raise Exception("peek() вызывается для пустого стека") 
 
 return self. __index[0] 
 
 def pop(self ): 
 
 if len(self) == 0: 
 
 raise Exception("pop() вызывается из пустого стека") 
 
 return self.__index.pop(0) 
 

Важно отметить, что У списка Python есть собственный метод .pop() , который ведет себя почти так же, как метод стека .pop(), за исключением того, что версия списка может брать индекс и «выталкивать» элемент из любого места в списке. .

Настройка функции

str()

Дополнительно мы можем указать Python, как мы хотим, чтобы наш стек печатался с помощью функции str() . На данный момент его использование дает следующие результаты:

 
 
 >>> s = stack() 
 
 >>> print(str(s)) 
 
 '<__main__.объект стека по адресу 0x000002296C8ED160>' 
 

Чтобы понять содержимое нашего стека, нам понадобится нечто более полезное. Вот где __str__() Метод Дандера пригодится:

 
 
 стек классов: 
 
 def __init__(self): 
 
 self. __index = [] 
 
 def __lendex__(self) return): 
2 
 ) 
 
 def push(self,item): 
 
 self.__index.insert(0,item) 
 
 def peek(self): 
 
 if len(self) == 0: 
 
 поднять Exception("peek( ) вызывается из пустого стека.") 
 
 return self.__index[0] 
 
 def pop(self): 
 
 if len(self) == 0: 
 
 поднять исключение ("вызывается pop() для пустого стека") 
 
 return self.__index.pop(0) 
 
 def __str__(self): 
 
 return str(self.__index) 
 

Это будет вернуть содержимое нашего стека, точно так же, как распечатать элементы общего списка.

Использование класса

стека

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

 
 
 >>> s = stack() 
 
 >>> s.peek() # stack = [] 
 
 Исключение: функция peek() вызывается для пустого стека.  
 
 >>> len(s) 
 
 >>> s.push(5) # stack = [5] 
 
 >>> s.peek() 
 
 5 
 
 >>> s.push('Apple ') # stack = ['Apple',5] 
 
 >>> s.push({'A':'B'}) # stack = [{'A':'B'},'Apple',5 ] 
 
 >>> s.push(25) # стек = [25,{'A':'B'},'Apple',5] 
 
 >>> len(s) 
 
 4 
 
 >>> str(s) 
 
 "[25, {'A': 'B'}, 'Apple', 5]" 
 
 >>> s .pop() # стек = [{'A':'B'},'Apple',5] 
 
 25 
 
 >>> s.pop() # стек = ['Apple',5] 
 
 { 'A': 'B'} 
 
 >>> str(s) 
 
 "['Apple', 5]" 
 
 >>> len(s) 
 
 2 
 

Заключение

У нас есть Теперь вы узнали, как реализовать основные функции класса стека в Python. Мы определенно могли бы добавить больше функций в эту реализацию, если бы захотели. Некоторые примеры могут включать:

• Рефакторинг .peek() для просмотра любого элемента в стеке по индексу.
• Поддержка добавления содержимого списков в виде серии элементов в нашем стеке.
• Добавление метода . clear() для очистки стека.
• Определение верхнего предела размера стека, который может быть полезен в производственной среде, чтобы предотвратить повторное добавление элементов в стек неконтролируемыми операциями и возникновение исключения «Недостаточно памяти».

Взяв это за основу, мы уверенно продвигаемся по пути разработки собственной реализации стека.

Узнайте больше о Codecademy

Карьерный рост

Информатика

Ищете введение в теорию программирования? Осваивайте Python, изучая структуры данных, алгоритмы и многое другое!

Checker Dense

Включает

5 курсов

Checker DenseCertificate Icon

С

Professional Certification

Checker DenseLevel Icon

2 Beginner 0410 82 Уроки

Курс

Изучение Python 3

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

Checker DenseCertificate Icon

With

Certificate

Checker DenseLevel Icon

Новичок Friendly

14 Уроки

Stack in Python | Что такое стек Python и как его реализовать

Стать сертифицированным специалистом

Привет, возможно, вы попали сюда в поисках Stack in Python, что ж, мы разобрались для вас. В этом блоге мы проведем глубокий анализ того, КАК, ПОЧЕМУ и ГДЕ использовать стек в Python .

Блог состоит из следующих тем:

• Что такое стек в структурах данных?
• Почему и когда мы используем стеки?
• Как мы можем реализовать стек в Python?
• Простая программа для иллюстрации стека в Python.
• Подробнее об использовании стеков в Python и связанных программах
• Список встроенных
• Класс collections.deque
• Класс Queue.LifoQueue

Что такое стек в структурах данных?

Структуры данных являются ключом к организации хранения в компьютерах, чтобы мы могли эффективно получать доступ к данным и редактировать их. Стеки — одна из первых структур данных, определенных в информатике. Проще говоря, стек — это линейный набор элементов. Это набор объектов, который поддерживает быструю семантику «последним пришел — первым обслужен» (LIFO) для вставки и удаления. Это структура массива или списка вызовов функций и параметров, используемых в современном компьютерном программировании и архитектуре ЦП. Подобно стопке тарелок в ресторане, элементы в стопке добавляются или удаляются из верхней части стопки в порядке «последним пришел — первым вышел». В отличие от списков или массивов, произвольный доступ к объектам, содержащимся в стеке, запрещен.

В стеке есть два типа операций:

• Push — добавление данных в стек.
• Pop — для удаления данных из стека.

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

Почему и когда мы используем стек?

Стеки — это простые структуры данных, которые позволяют нам хранить и извлекать данные последовательно.

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

Чтобы понять стек на уровне земли, представьте стопку книг. Вы добавляете книгу на вершину стопки, поэтому первая книга, которую вы возьмете, будет последней, добавленной в стопку.

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

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

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

В Python мы можем реализовать стеки Python:

1. Использование встроенной структуры данных List. Встроенная в Python структура данных List содержит методы для имитации операций стека и очереди .
2. Использование библиотеки deque, которая эффективно обеспечивает операции стека и очереди в одном объекте.
3. Использование класса queue.LifoQueue.

Как упоминалось ранее, мы можем добавлять элементы в стек с помощью операции «PUSH» и удалять элементы с помощью операции «POP».

PUSH Operation

Push — добавляет элемент на вершину стека. Обратитесь к изображению ниже для большего понимания:

Операция POP

Pop — удаляет элемент из вершины стека.

Вот простая программа, иллюстрирующая Stack в Python —

 class Stack
def_init_(я):
self. items=[]
определение is_empty (я):
вернуть self.items==[]
def push(я, данные):
self.items.append(данные)
деф поп(сам):
вернуть self.items.pop()
с = стек ()
пока верно:
print('push<значение>')
распечатать («поп»)
распечатать («выйти»)
do= input('Что бы вы хотели сделать?').split()
операция = сделать [0].strip().lower()
если операция == 'push':
s.push (int (делать [1]))
Элиф операция == 'поп':
если s.is_empty():
print('Стек пуст')
еще:
print('Извлеченное значение:', s.pop())
операция elif=='выход':
перерыв
 

 

Подробнее об использовании стеков в Python и связанных с ним программах

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

 Список  Встроенный

Встроенный тип списка Python создает достойную структуру данных стека, поскольку он поддерживает операции push и pop в амортизированном O(1)

Списки Python внутренне реализованы как динамические массивы, что означает, что им иногда нужно изменять размер пространства для хранения элементов, хранящихся в них, всякий раз, когда они добавляются или удаляются. Места для хранения выделяется больше, чем требуется, поэтому не каждое нажатие или извлечение требует изменения размера, и вы получаете амортизированный  O(1)  время сложности этих операций.

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

Важное предупреждение о производительности при использовании списков в качестве стеков:

удаляется с конца с помощью pop(). Стеки, основанные на списках Python, расширяются вправо и сжимаются влево.

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

# Использование списка Python в качестве стека (LIFO):

с = []
 
s.append('есть')
s.append('сон')
s.append('код')
 
>>> с
['есть', 'спать', 'кодировать']
 
>>> s.pop()
'код'
>>> s.pop()
'спать'
>>> s.pop()
'есть'
 
>>> s.pop()
IndexError: "вытолкнуть из пустого списка"
 

Класс collections.deque

).

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

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

collections.deque — хороший выбор, если вы ищете структуру данных стека в стандартной библиотеке Python с характеристиками производительности реализации связанного списка.

# Использование collections.deque в качестве стека (LIFO):

очередь импорта из коллекций
q = очередь ()
 
q.append('есть')
q.append('сон')
q.append('код')
 
>>> д
deque(['есть', 'спать', 'код'])
 
>>> q.pop()
'код'
>>> q.pop()
'спать'
>>> q.pop()
'есть'
 
>>> q.pop()
IndexError: "извлечь из пустой деки"
 

Очередь . LifoQueue Класс

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

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

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

# Использование queue.LifoQueue в качестве стека:

 из очереди импорта LifoQueue
s = LifoQueue()
 
s.put('есть')
s.put('сон')
s.put('код')
 
>>> с
<объект очереди.LifoQueue по адресу 0x108298dd8>
 
>>> с.получить()
'код'
>>> с.получить()
'спать'
>>> с.получить()
'есть'
 
>>> s.get_nowait()
очередь.Пустой
 
>>> с.получить()
# Блокирует/ждет вечно...
 

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