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

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

• Convert Infix expression to Postfix expression
• Prefix to Infix Conversion
• Prefix to Postfix Conversion
• Postfix to Prefix Conversion
• Postfix to Infix
• Convert Infix To Prefix Notation
• Check for Balanced Brackets in an expression (well-formedness)
• Arithmetic Expression Evaluation
• Evaluation of Postfix Expression
• How to Reverse a Stack using Recursion
• Reverse individual words
• How to Reverse a String using Stack
• Reversing a Queue

• How to create mergeable stack?
• The Stock Span Problem
• Next Greater Element (NGE) for every element in given Array
• Next Greater Frequency Element
• Maximum product of indexes of next greater on left and right
• Iterative Tower of Hanoi
• Sort a stack using a temporary stack
• Reverse a stack without using extra space in O(n)
• Delete middle element of a stack
• Check if a queue can be sorted into another queue using a stack
• Check if an array is stack sortable
• Largest Rectangular Area in a Histogram using Stack
• Find maximum of minimum for every window size in a given array
• Find index of closing bracket for a given opening bracket in an expression
• Find maximum difference between nearest left and right smaller elements
• Delete consecutive same words in a sequence
• Check mirror in n-ary tree
• Reverse a number using stack
• Reversing the first K elements of a Queue

• The Celebrity Problem
• Print next greater number of Q queries
• Iterative Postorder Traversal | Set 2 (Using One Stack)
• Print ancestors of a given binary tree node without recursion
• Length of the longest valid substring
• Expression contains redundant bracket or not
• Find if an expression has duplicate parenthesis or not
• Find next Smaller of next Greater in an array
• Iterative method to find ancestors of a given binary tree
• Stack Permutations (Check if an array is stack permutation of other)
• Spaghetti Stack
• Remove brackets from an algebraic string containing + and – operators
• Range Queries for Longest Correct Bracket Subsequence Set | 2

• Convert Infix expression to Postfix expression
• Prefix to Infix Conversion
• Prefix to Postfix Conversion
• Postfix to Prefix Conversion
• Postfix to Infix
• Convert Infix To Prefix Notation
• Check for Balanced Brackets in an expression (well-formedness)
• Arithmetic Expression Evaluation
• Evaluation of Postfix Expression
• How to Reverse a Stack using Recursion
• Reverse individual words
• How to Reverse a String using Stack
• Reversing a Queue

• How to create mergeable stack?
• The Stock Span Problem
• Next Greater Element (NGE) for every element in given Array
• Next Greater Frequency Element
• Maximum product of indexes of next greater on left and right
• Iterative Tower of Hanoi
• Sort a stack using a temporary stack
• Reverse a stack without using extra space in O(n)
• Delete middle element of a stack
• Check if a queue can be sorted into another queue using a stack
• Check if an array is stack sortable
• Largest Rectangular Area in a Histogram using Stack
• Find maximum of minimum for every window size in a given array
• Find index of closing bracket for a given opening bracket in an expression
• Find maximum difference between nearest left and right smaller elements
• Delete consecutive same words in a sequence
• Check mirror in n-ary tree
• Reverse a number using stack
• Reversing the first K elements of a Queue

• The Celebrity Problem
• Print next greater number of Q queries
• Iterative Postorder Traversal | Set 2 (Using One Stack)
• Print ancestors of a given binary tree node without recursion
• Length of the longest valid substring
• Expression contains redundant bracket or not
• Find if an expression has duplicate parenthesis or not
• Find next Smaller of next Greater in an array
• Iterative method to find ancestors of a given binary tree
• Stack Permutations (Check if an array is stack permutation of other)
• Spaghetti Stack
• Remove brackets from an algebraic string containing + and – operators
• Range Queries for Longest Correct Bracket Subsequence Set | 2

Источник

Стек в Python – основы и примеры

В этом руководстве мы изучим основы стека и реализуем его с помощью кода Python.

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

Стек в Python – это линейная структура данных, в которой данные расположены объектами друг над другом. Он хранит данные в режиме LIFO (Last in First Out). Данные хранятся в том же порядке, в каком на кухне тарелки располагаются одна над другой. Мы всегда выбираем последнюю тарелку из стопки тарелок. В стеке новый элемент вставляется с одного конца, и элемент может быть удален только с этого конца.

Простым примером стека является функция «Отменить» в редакторе. Функция отмены работает с последним выполненным нами событием. Мы можем выполнять две операции в стеке – PUSH и POP. Операция PUSH – это когда мы добавляем элемент, а операция POP – когда мы удаляем элемент.

Методы стека

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

• empty() – возвращает истину, если стек пуст. Временная сложность O (1).
• size() – возвращает длину. Временная сложность O (1).
• top() – этот метод возвращает адрес последнего элемента. Временная сложность O (1).
• push(g) – метод добавляет элемент ‘g’ в конец стека – временная сложность составляет O (1).
• pop() – удаляет самый верхний элемент. Временная сложность O (1).

Реализация

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

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

Список Python можно использовать как стек. Он использует метод append() для вставки элементов, где стек использует метод push(). В списке также есть метод pop() для удаления последнего элемента.

Но в списке есть недостаток: он становится медленнее по мере роста. Новый элемент в нем хранится рядом с другим. Если список растет и выходит за пределы блока памяти, Python выделяет некоторую память. Вот почему список становится медленным. Разберем на примере –

# initial empty stack my_stack = [] # append() function to push # element in the my_stack my_stack.append('x') my_stack.append('y') my_stack.append('z') print(my_stack) # pop() function to pop # element from my_stack in # LIFO order print('\nElements poped from my_stack:') print(my_stack.pop()) print(my_stack.pop()) print(my_stack.pop()) print('\nmy_stack after elements are poped:') print(my_stack)

['x', 'y', 'z'] Elements poped from my_stack: z y x my_stack after elements are poped: [] Traceback (most recent call last): File "C:/Users/DEVANSH SHARMA/PycharmProjects/Hello/Stack.py", line 21, in print(my_stack.pop()) IndexError: pop from empty list

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

С использованием collection.deque

Модуль коллекции предоставляет класс deque, который используется для создания стеков Python. Deque произносится как «колода», что означает «двусторонняя очередь». Двухсторонняя очередь может быть предпочтительнее списка, поскольку она выполняет операции добавления и извлечения быстрее, чем список. Временная сложность – O (1), где список занимает O (n).

from collections import deque my_stack = deque() # append() function is used to push # element in the my_stack my_stack.append('a') my_stack.append('b') my_stack.append('c') print('Initial my_stack:') print(my_stack) # pop() function is used to pop # element from my_stack in # LIFO order print('\nElements poped from my_stack:') print(my_stack.pop()) print(my_stack.pop()) print(my_stack.pop()) print('\nmy_stack after elements are poped:') print(my_stack)

Initial my_stack: deque(['a', 'b', 'c']) Elements poped from my_stack: c b a my_stack after elements are poped: deque([])

Приведенный выше код почти аналогичен предыдущему примеру. Однако единственная разница в том, что мы импортировали двухстороннюю очередь из модуля коллекции.

Сравнение Deque и список

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

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

Модуль LifeQueue

Модуль очереди имеет очередь LIFO, которая совпадает со стеком. Обычно очередь использует метод put() для добавления данных и метод () для получения данных.

Ниже приведены несколько методов, доступных в очереди.

• empty() – если очередь пуста, возвращает true; в противном случае вернется false.
• maxsize() – этот метод используется для установки максимального количества элементов, разрешенных в очереди.
• get() – возвращает и удаляет элемент из очереди. Очередь может быть пустой; он ждет, пока элемент не станет доступным.
• full() – возвращает True, если очередь заполнена. По умолчанию очередь определяется как maxsize = 0. В этом случае он не вернет True.
• put(item) – добавляет элемент в очередь; если очередь заполнена, ожидает, пока освободится место.
• put_nowait(item) – добавляет элемент в очередь без задержки.
• qsize() – возвращает размер очереди.

# Implementing stack using the queue module from queue import LifoQueue # Initializing a my_stack stack with maxsize my_stack = LifoQueue(maxsize = 5) # qsize() display the number of elements # in the my_stack print(my_stack.qsize()) # put() function is used to push # element in the my_stack my_stack.put('x') my_stack.put('y') my_stack.put('z') print("Stack is Full: ", my_stack.full()) print("Size of Stack: ", my_stack.qsize()) # To pop the element we used get() function # from my_stack in # LIFO order print('\nElements poped from the my_stack') print(my_stack.get()) print(my_stack.get()) print(my_stack.get()) print("\nStack is Empty: ", my_stack.empty())

0 0 Stack is Full: False Size of Stack: 3 Elements poped from the my_stack z y x Stack is Empty: True

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

Начальный размер массива равен нулю; мы поместили три элемента в стек с помощью метода put(). Теперь мы снова проверили, пуст ли стек и его размер. Мы имеем три элемента. Выдвинем элемент с помощью метода get(). Сначала удаляется последний добавленный элемент. После удаления всех элементов получаем пустой стек.

Стеки и потоки Python

Мы также можем использовать стек Python в многопоточной программе. Это сложная тема, но она используется не часто, поэтому вы можете пропустить этот раздел, если вас не интересует многопоточность.

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

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

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

Ответ заключается в том, что мы можем использовать LIFOqueue, и мы знаем, что LIFO означает Last In First Out. Он использует put() и gets() для добавления и удаления элемента стека.

Какую реализацию стека следует рассмотреть?

Мы упомянули три метода реализации стека в Python. Вышеупомянутые методы имеют свои преимущества или недостатки.

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

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

Заключение

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

Источник