Разбиране на имплементацията на стека в Python

от

Структурите от данни играят ключова роля в света на програмирането. Те ни помагат да организираме нашите данни по начин, който може да се използва ефективно. Стекът е една от най-простите структури от данни.

Нека научим за стека и неговата реализация в Python.

Какво е стек?

Купчината е подобна на купчина книги, столове и т.н. в реалния живот. И следва принципа Последен влязъл/Пръв излязъл (LIFO). Това е най-простата структура от данни. Нека видим сценария с пример от реалния свят.

Да кажем, че имаме купчина книги, както следва.

Когато искаме третата книга отгоре тогава, трябва да премахнем първите две книги отгоре, за да извадим третата книга. Тук най-горната книга отива последна в купчината и е първа от купчината. Стекът на структурата на данните следва същия принцип Last-in/First-out (LIFO) в програмирането.

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

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

1. натискане (данни)

Добавя или избутва данните в стека.

2. поп()

Премахва или изважда най-горния елемент от стека.

Вижте илюстрациите по-долу на операции за натискане и изскачане.

Ще напишем някои помощни функции, които ни помагат да получим повече информация за стека.

Да ги видим.

надниквам()

Връща най-горния елемент от стека.

празно е()

Връща дали стекът е празен или не.

Достатъчно концептуални аспекти на структурата на данните на стека. Нека преминем към изпълнението без повече шум.

Предполагам, че имате инсталиран 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()

Завършихме внедряването на стека с необходимите операции. Сега нека добавим помощните функции, за да получим повече информация за стека.

  Създайте структура на разбивка на работата с тези 10 инструмента

Стъпка 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 в стека, като използвате метода на натискане.
  • Методът is_empty трябва да върне False. Провери го.
  • Отпечатайте най-горния елемент, като използвате метода на надникване.
  • Извадете елемента от стека, като използвате метода за изваждане.
  • Проверете елемента 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

Можем директно да използваме типа данни списък като стек. Горната реализация на стека ви помага да разберете реализацията на стека и в други езици за програмиране.

  Кое да изберете през 2022 г.?

Можете също да разгледате тези статии, свързани със списъка.

Нека видим вградения deque от вградения модул за колекции, който може да действа като стек.

#2. deque от колекции

Реализира се като двустранна опашка. Тъй като поддържа добавянето и премахването на елементи от двата края. Следователно можем да го използваме като стек. Можем да го накараме да следва LIFO принципа на стека.

Реализира се с помощта на други структури от данни, наречени двойно свързан списък. Така че изпълнението на вмъкването и изтриването на елементи е последователно. Достъпът до елементи от средния свързан списък отне O(n) време. Можем да го използваме като стек, тъй като няма нужда от достъп до средните елементи от стека.

Преди да внедрим стека, нека видим методите, които се използват за внедряване на стека с помощта на опашката.

  • append(data) – използва се за изпращане на данните към стека
  • pop() – използва се за премахване на най-горния елемент от стека

Няма алтернативни методи за peek и is_empty. Можем да отпечатаме целия стек вместо метода peek. След това можем да използваме метода len, за да проверим дали стекът е празен или не.

Нека внедрим стека с помощта на deque от модула за колекции.

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 от вградения модул за колекции. Ще получите резултата, както е споменато по-долу, ако изпълните горната програма.

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

Досега сме виждали два начина за внедряване на стека. Има ли други начини за внедряване на стек? да! Нека видим окончателния начин за внедряване на стек в този урок.

#3. LifoQueue

Самото име LifoQueue казва, че следва принципа LIFO. Следователно можем да го използваме като стек без никакво съмнение. Той е от вградената модулна опашка. LifoQueue предоставя някои удобни методи, които са полезни при внедряването на стека. Да ги видим

  • put(data) – добавя или избутва данните към опашката
  • get() – премахва или изважда най-горния елемент от опашката
  • празен() – връща дали стекът е празен или не
  • 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

Приложение на Stack

Сега имате достатъчно познания за стековете, за да ги приложите в проблеми с програмирането. Нека да видим проблем и да го разрешим с помощта на стек.

  Как да продадете своя Mac

Даден е израз, напишете програма, за да проверите дали скобите, скобите и фигурните скоби са балансирани правилно или не.

Нека да видим някои примери.

Вход: „[{}]([])”

Изход: балансиран

Вход: „{[}]([])”

Изход: Небалансиран

Можем да използваме стека, за да разрешим горния проблем. Нека да видим стъпките за решаване на проблема.

  • Създайте стек за съхраняване на знаците.
  • Ако дължината на израза е нечетна, тогава изразът не е балансиран
  • Итерация през дадения израз.
    • Ако текущият знак е отварящата скоба от ( или { или [, 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")

Можем да използваме стека за решаване на много повече проблеми. Горният проблем е един от тях. Опитайте се да приложите концепцията за стека навсякъде, където смятате, че е най-подходящо за вас.

Заключение

ах! Завършихте урока. Надявам се урокът да ви е харесал толкова, колкото и аз, докато го правех. Това е всичко за урока.

Приятно кодиране 🙂 👨‍💻