Розуміння реалізації стека в Python

Структури даних відіграють ключову роль у світі програмування. Вони допомагають нам упорядковувати наші дані таким чином, щоб їх можна було ефективно використовувати. Стек є однією з найпростіших структур даних.

Давайте дізнаємося про стек і його реалізацію в Python.

Що таке стек?

Стопка схожа на купу книг, стільців тощо в реальному житті. І він дотримується принципу «останній прийшов/перший вийшов» (LIFO). Це найпростіша структура даних. Давайте розглянемо сценарій на прикладі реального світу.

Скажімо, у нас є купа книжок наступним чином.

Коли нам потрібна третя книга зверху, ми повинні видалити перші дві книги зверху, щоб витягти третю книгу. Тут найвища книжка йде останньою до купи та йде першою з купи. Стек структури даних дотримується того самого принципу «Останній прийшов/перший вийшов» (LIFO) у програмуванні.

Операції в стеку

В основному в стеку є дві операції

1. push(дані)

Додає або надсилає дані в стек.

2. поп()

Видаляє або висуває верхній елемент зі стеку.

Перегляньте наведені нижче ілюстрації операцій натискання та висунення.

Ми напишемо кілька допоміжних функцій, які допоможуть нам отримати більше інформації про стек.

Давайте їх подивимось.

peek()

Повертає найвищий елемент зі стеку.

пусто()

Повертає, чи стек порожній чи ні.

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

Я припускаю, що на вашому комп’ютері встановлено 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_empty. Він повинен повернути True.
• Помістіть числа 1, 2, 3, 4, 5 у стек за допомогою методу push.
• Метод is_empty має повертати False. Перевір це.
• Надрукуйте найвищий елемент за допомогою методу peek.
• Витягніть елемент зі стеку за допомогою методу pop.
• Перевірте елемент peek. Він повинен повернути елемент 4.
• Тепер витягніть усі елементи зі стека.
• Метод is_empty має повертати значення 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

Ми можемо безпосередньо використовувати тип даних списку як стек. Наведена вище реалізація стека допоможе вам зрозуміти реалізацію стека також в інших мовах програмування.

Ви також можете переглянути ці статті, пов’язані зі списком.

Давайте подивимося на вбудований deque із вбудованого модуля колекцій, який може діяти як стек.

#2. дека з колекцій

Він реалізований як двостороння черга. Оскільки він підтримує додавання та видалення елементів з обох кінців. Тому ми можемо використовувати його як стек. Ми можемо зробити так, щоб він відповідав принципу стека LIFO.

Він реалізований за допомогою інших структур даних, які називаються двозв’язаним списком. Таким чином, продуктивність вставки та видалення елементів узгоджена. Доступ до елементів із середнього пов’язаного списку зайняв O(n) часу. Ми можемо використовувати його як стек, оскільки немає необхідності отримувати доступ до середніх елементів зі стеку.

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

• append(data) – використовується для надсилання даних у стек
• pop() – використовується для видалення самого верхнього елемента зі стеку

Не існує альтернативних методів для peek і is_empty. Ми можемо надрукувати весь стек замість методу peek. Далі ми можемо використати метод len, щоб перевірити, порожній стек чи ні.

Давайте реалізуємо стек за допомогою deque з модуля collections.

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)

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

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

Досі ми бачили два способи реалізації стека. Чи існують інші способи реалізації стека? так! Давайте розглянемо остаточний спосіб реалізації стека в цьому підручнику.

#3. LifoQueue

Сама назва LifoQueue говорить про те, що він працює за принципом LIFO. Отже, ми можемо використовувати його як стек без будь-яких сумнівів. Це з вбудованої черги модуля. LifoQueue надає кілька зручних методів, корисних у реалізації стека. Давайте їх подивимось

• put(data) – додає або надсилає дані до черги
• get() – видаляє або висуває верхній елемент із черги
• empty() – повертає, чи стек порожній чи ні
• qsize() – повертає довжину черги

Реалізуємо стек за допомогою 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 ]потім витягніть зі стека.
  • Якщо висунутий символ збігається з початковою дужкою, тоді продовження, інакше дужки не збалансовані.
• Після ітерації, якщо стек порожній, рівняння є збалансованим, інакше рівняння є незбалансованим.

Ми можемо використовувати тип даних set для перевірки відповідності дужок.

## 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")

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

Висновок

ага! Ви завершили підручник. Сподіваюся, під час створення підручник вам сподобався так само, як і мені. Ось і все для підручника.

Щасливого кодування 🙂 👨‍💻