Понимание реализации стека в Python

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

Давайте узнаем больше о стеке и его реализации в Python.

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

Куча похожа на кучу книг, стульев и т. д. в реальной жизни. И это следует принципу «последним пришел — первым ушел» (LIFO). Это самая простая структура данных. Давайте посмотрим сценарий на реальном примере.

Допустим, у нас есть куча книг следующим образом.

Когда нам нужна третья книга сверху, мы должны удалить первые две книги сверху, чтобы получить третью книгу. Здесь самая высокая книга идет последней в стопке и идет первой из стопки. Структура данных стека следует тому же принципу LIFO (последний вошел/первым вышел) в программировании.

Операции стека

В стеке в основном две операции

1. нажать (данные)

Добавляет или помещает данные в стек.

2. поп ()

Удаляет или извлекает самый верхний элемент из стека.

См. ниже иллюстрации операций push и pop.

Мы напишем несколько вспомогательных функций, которые помогут нам получить больше информации о стеке.

Давайте посмотрим на них.

заглянуть ()

Возвращает самый верхний элемент из стека.

пустой()

Возвращает значение, является ли стек пустым или нет.

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

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

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

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

Давайте посмотрим их все один за другим.

№1. Список

Мы будем реализовывать стек, используя список в классе. Давайте посмотрим пошаговую реализацию стека.

Шаг 1: Напишите класс с именем Stack.

class Stack:
	pass

Шаг 2: Нам нужно сохранить данные в списке. Добавим в класс Stack пустой список с элементами имени.

class Stack:
	def __init__(self):
		self.elements = []

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

class Stack:
	def __init__(self):
		self.elements = []

	def push(self, data):
		self.elements.append(data)
		return data

Шаг 4: Точно так же давайте напишем метод pop, который извлекает самый верхний элемент из стека. Мы можем использовать метод pop типа данных списка.

class Stack:
	## ...
	def pop(self):
		return self.elements.pop()

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

Шаг 5: Мы можем получить самый верхний элемент из стека, используя отрицательный индекс. Элемент кода [-1] возвращает последний список. В нашем случае это самый верхний элемент стека.

class Stack:
	## ...

	def peek(self):
		return self.elements[-1]

Шаг 6: Если длина списка элементов равна 0, то стек пуст. Давайте напишем метод, который возвращает, является ли элемент пустым или нет.

class Stack:
	## ...
	def is_empty(self):
		return len(self.elements) == 0

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

Ой! подождите, мы только что реализовали это. Но я не видел, как его использовать. Как тогда его использовать?

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

class Stack: 
    ## ...

if __name__ == '__main__':
    stack = Stack()

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

• Проверьте, пуст ли стек или нет, используя метод is_empti. Он должен вернуть True.
• Столкните числа 1, 2, 3, 4, 5 в стопку, используя метод толчка.
• Метод is_empti должен возвращать False. Проверять.
• Распечатайте самый верхний элемент, используя метод peek.
• Извлеките элемент из стека с помощью метода pop.
• Проверьте заглядывающий элемент. Он должен вернуть элемент 4.
• Теперь извлеките все элементы из стека.
• Метод is_empti должен возвращать True. Проверять.

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

Вы написали код? Нет, не волнуйтесь, проверьте код ниже.

class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
    
    def pop(self): 
        return self.elements.pop() 
        
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

if __name__ == '__main__':
    stack = Stack()
    
    ## checking is_empty method -> true
    print(stack.is_empty())

    ## pushing the elements
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    ## again checking is_empty method -> false
    print(stack.is_empty())

    ## printing the topmost element of the stack -> 5
    print(stack.peek())

    ## popping the topmost element -> 5
    stack.pop()

    ## checking the topmost element using peek method -> 4
    print(stack.peek())

    ## popping all the elements
    stack.pop()
    stack.pop() 
    stack.pop() 
    stack.pop() 

    ## checking the is_empty method for the last time -> true
    print(stack.is_empty())

Ура! мы завершили реализацию стека с нуля, используя тип данных списка. Вы увидите вывод, как показано ниже, если вы запустите приведенный выше код.

True
False
5
4
True

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

Вы также можете проверить эти статьи, связанные со списком.

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

№ 2. одеяло из коллекций

Он реализован как двусторонний ряд. Поскольку он поддерживает добавление и удаление элементов с обоих концов. Поэтому мы можем использовать его как стек. Мы можем заставить его следовать принципу стека LIFO.

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

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

• append(data) — используется для помещения данных в стек
• pop() — используется для удаления самого верхнего элемента из стека.

Альтернативных методов для peek и is_empti нет. Мы можем напечатать весь стек вместо метода просмотра. Затем мы можем использовать метод len, чтобы проверить, пуст стек или нет.

Давайте реализуем стек, используя приманку из модуля коллекции.

from collections import deque

## creating deque object
stack = deque()

## checking whether stack is empty or not -> true
print(len(stack) == 0)

## pushing the elements
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## again checking whether stack is empty or not -> false
print(len(stack) == 0)

## printing the stack
print(stack)

## popping the topmost element -> 5
stack.pop()

## printing the stack
print(stack)

## popping all the elements
stack.pop()
stack.pop() 
stack.pop() 
stack.pop() 

## checking the whether stack is empty or not for the last time -> true
print(len(stack) == 0)

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

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

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

№3. LifoQueue

Само название LifoQueue говорит о том, что он следует принципу LIFO. Поэтому мы можем использовать его как стек без всяких сомнений. Это из заказа встроенного модуля. LifoQueue предоставляет несколько удобных методов, полезных при реализации стека. Давайте посмотрим на них

• put(data) – добавляет или помещает данные в очередь
• get() — удаляет или извлекает самый верхний элемент из очереди
• empty() — возвращает, пуст стек или нет
• xize() — возвращает длину строки

Реализуем стек с помощью LifoQueue из модуля очереди.

from queue import LifoQueue

## creating LifoQueue object
stack = LifoQueue()

## checking whether stack is empty or not -> true
print(stack.empty())

## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## again checking whether stack is empty or not -> false
print(stack.empty())

## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())

## checking the stack size
print("Size", stack.qsize())

print(stack.get())
print(stack.get())

## checking the whether stack is empty or not for the last time -> true
print(stack.empty())

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

True
False
5
4
3
Size 2
2
1
True

Применение стека

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

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

Давайте посмотрим на некоторые примеры.

Вход: «[{}]([])»

Выход: сбалансированный

Вход: «{[}]([])»

Выход: не сбалансированный

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

• Создайте стек для хранения символов.
• Если длина выражения нечетная, то выражение не сбалансировано
• Пройди заданное выражение.
  • Если текущий символ является открывающей скобкой из ( или { или [, then push it to stack.
  • Else if the current character is a closing bracket ) or } or ]а потом выпрыгнуть из толпы.
  • Если выдвинутый символ соответствует открывающей скобке, продолжайте, иначе скобки не сбалансированы.
• После итерации, если стек пуст, уравнение уравновешивается, в противном случае уравнение не уравновешивается.

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

## stack
class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
        
    def pop(self): 
        return self.elements.pop() 
    
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

def balance_check(expression):
    ## checking the length of the expression
    if len(expression) % 2 != 0:
        ## not balanced if the length is odd
        return False
    
    ## for checking
    opening_brackets = set('([{') 
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## stack initialization
    stack = Stack()
    
    ## iterating through the given expression
    for bracket in expression:

        ## checking whether the current bracket is opened or not        
        if bracket in opening_brackets:
            ## adding to the stack 
            stack.push(bracket)
        else:
            ## popping out the last bracket from the stack
            popped_bracket = stack.pop()
        
            ## checking whether popped and current bracket pair
            if (popped_bracket, bracket) not in pairs:
                return False
    
    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")
    
    if balance_check('{[}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

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

Заключение

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

Удачного кодирования ? ?‍?