Zrozumienie implementacji stosu w Pythonie

przez

Struktury danych odgrywają kluczową rolę w świecie programowania. Pomagają nam organizować nasze dane w sposób, który można efektywnie wykorzystać. Stos jest jedną z najprostszych struktur danych.

Poznajmy stos i jego implementację w Pythonie.

Co to jest stos?

Stos jest podobny do stosu książek, krzeseł itp. w prawdziwym życiu. Działa zgodnie z zasadą „ostatnie weszło/pierwsze wyszło” (LIFO). Jest to najprostsza struktura danych. Zobaczmy scenariusz z przykładem ze świata rzeczywistego.

Powiedzmy, że mamy stos książek w następujący sposób.

Kiedy chcemy trzecią książkę od góry, musimy usunąć pierwsze dwie książki od góry, aby wyjąć trzecią książkę. Tutaj najwyższa książka trafia na stos jako ostatnia i pierwsza na stosie. Stos struktury danych jest zgodny z tą samą zasadą ostatniego wejścia/pierwszego wyjścia (LIFO) w programowaniu.

Operacje w stosie

Stos składa się głównie z dwóch operacji

1. push (dane)

Dodaje lub wypycha dane do stosu.

2. pop()

Usuwa lub zdejmuje najwyższy element ze stosu.

Zobacz poniższe ilustracje operacji push i pop.

Napiszemy kilka funkcji pomocniczych, które pomogą nam uzyskać więcej informacji o stosie.

Zobaczmy je.

zerkać()

Zwraca najwyższy element ze stosu.

jest pusty()

Zwraca informację, czy stos jest pusty, czy nie.

Wystarczająco dużo aspektów koncepcyjnych struktury danych stosu. Bez zbędnych ceregieli przejdźmy do implementacji.

Zakładam, że masz zainstalowany Python na swoim komputerze, jeśli nie, możesz także wypróbować kompilator online.

Implementacja stosu

Implementacja stosu jest najłatwiejsza w porównaniu z innymi implementacjami struktur danych. W Pythonie możemy zaimplementować stos na wiele sposobów.

Zobaczmy je wszystkie jeden po drugim.

# 1. Lista

Zamierzamy zaimplementować stos, używając listy w klasie. Zobaczmy krok po kroku implementację stosu.

Krok 1: Napisz klasę o nazwie Stack.

class Stack:
	pass

Krok 2: Musimy przechowywać dane na liście. Dodajmy pustą listę w klasie Stack z elementami name.

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

Krok 3: Aby umieścić elementy w stosie, potrzebujemy metody. Napiszmy metodę push, która pobiera dane jako argument i dołącza je do listy elementów.

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

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

Krok 4: Podobnie napiszmy metodę pop, która wyskakuje najwyższy element ze stosu. Możemy użyć metody pop typu danych list.

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

Zakończyliśmy implementację stosu z wymaganymi operacjami. Teraz dodajmy funkcje pomocnicze, aby uzyskać więcej informacji o stosie.

Krok 5: Możemy pobrać najwyższy element ze stosu za pomocą indeksu ujemnego. Kod element[-1] zwraca ostatnią z listy. W naszym przypadku jest to najwyższy element stosu.

class Stack:
	## ...

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

Krok 6: Jeśli długość listy elementów wynosi 0, to stos jest pusty. Napiszmy metodę, która zwraca, czy element jest pusty, czy nie.

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

Zakończyliśmy implementację stosu przy użyciu typu danych list.

Oh! czekaj, właśnie to wdrożyliśmy. Ale nie widziałem, jak go używać. Jak go w takim razie używać?

Przyjdź, zobaczmy, jak to wdrożyć. Musimy utworzyć obiekt, aby klasa Stack go używała. To nic wielkiego. Zróbmy to najpierw.

class Stack: 
    ## ...

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

Stworzyliśmy obiekt stosu i jesteśmy gotowi do użycia. Wykonajmy poniższe kroki, aby przetestować operacje na stosie.

  • Sprawdź, czy stos jest pusty, czy nie, używając metody is_empty. Powinien zwrócić wartość True.
  • Wepchnij liczby 1, 2, 3, 4, 5 do stosu metodą push.
  • Metoda is_empty powinna zwrócić wartość False. Sprawdź to.
  • Wydrukuj najwyższy element metodą peek.
  • Zdejmij element ze stosu za pomocą metody pop.
  • Sprawdź element podglądu. Powinien zwrócić element 4.
  • Teraz zdejmij wszystkie elementy ze stosu.
  • Metoda is_empty powinna zwrócić wartość True. Sprawdź to.

Nasza implementacja stosu jest zakończona, jeśli przejdzie wszystkie powyższe kroki. Spróbuj napisać kod dla powyższych kroków.

Napisałeś kod? Nie, nie martw się, sprawdź poniższy kod.

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())

Hurra! zrealizowaliśmy implementację stosu od podstaw z wykorzystaniem typu danych list. Zobaczysz dane wyjściowe, jak wspomniano poniżej, jeśli uruchomisz powyższy kod.

True
False
5
4
True

Możemy bezpośrednio użyć typu danych listy jako stosu. Powyższa implementacja stosu pomaga zrozumieć implementację stosu również w innych językach programowania.

Możesz także sprawdzić te artykuły związane z listą.

Zobaczmy wbudowany moduł deque z wbudowanego modułu collections, który może działać jako stos.

#2. deque z kolekcji

Jest zaimplementowany jako kolejka dwustronna. Ponieważ obsługuje dodawanie i usuwanie elementów z obu końców. Dlatego możemy użyć go jako stosu. Możemy sprawić, by był zgodny z zasadą stosu LIFO.

Jest implementowana przy użyciu innych struktur danych zwanych listą podwójnie połączoną. Tak więc wydajność wstawiania i usuwania elementów jest spójna. Dostęp do elementów ze środkowo połączonej listy zajął O(n) czasu. Możemy użyć go jako stosu, ponieważ nie ma potrzeby dostępu do środkowych elementów ze stosu.

Zanim zaimplementujemy stos, zobaczmy metody, które są używane do implementacji stosu przy użyciu kolejki.

  • append(data) – służy do wypychania danych na stos
  • pop() – służy do usuwania najwyższego elementu ze stosu

Nie ma alternatywnych metod dla peek i is_empty. Możemy wydrukować cały stos zamiast metody peek. Następnie możemy użyć metody len, aby sprawdzić, czy stos jest pusty, czy nie.

Zaimplementujmy stos za pomocą deque z modułu 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)

Otóż ​​to. Nauczyliśmy się implementować stos za pomocą deque z wbudowanego modułu collections. Otrzymasz dane wyjściowe, jak wspomniano poniżej, jeśli wykonasz powyższy program.

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

Do tej pory widzieliśmy dwa sposoby implementacji stosu. Czy są jakieś inne sposoby implementacji stosu? Tak! Zobaczmy ostateczny sposób implementacji stosu w tym samouczku.

#3. LifoQueue

Sama nazwa LifoQueue mówi, że działa zgodnie z zasadą LIFO. Dlatego bez wątpienia możemy go używać jako stosu. Pochodzi z wbudowanej kolejki modułów. LifoQueue zapewnia kilka przydatnych metod, które są przydatne w implementacji stosu. Zobaczmy je

  • put(data) – dodaje lub wypycha dane do kolejki
  • get() – usuwa lub wyskakuje najwyższy element z kolejki
  • empty() – zwraca informację, czy stos jest pusty, czy nie
  • qsize() – zwraca długość kolejki

Zaimplementujmy stos za pomocą LifoQueue z modułu kolejki.

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())

Otrzymasz dane wyjściowe wymienione poniżej, jeśli wykonasz powyższy program bez jego zmiany.

True
False
5
4
3
Size 2
2
1
True

Zastosowanie stosu

Teraz masz wystarczającą wiedzę na temat stosów, aby zastosować ją w problemach programistycznych. Zobaczmy problem i rozwiążmy go za pomocą stosu.

Biorąc pod uwagę wyrażenie, napisz program sprawdzający, czy nawiasy, nawiasy klamrowe, nawiasy klamrowe są prawidłowo zrównoważone, czy nie.

Zobaczmy kilka przykładów.

Wejście: „[{}]([])”

Wyjście: Zbalansowane

Wejście: „{[}]([])”

Wyjście: niezbalansowane

Możemy użyć stosu do rozwiązania powyższego problemu. Zobaczmy kroki, aby rozwiązać problem.

  • Utwórz stos do przechowywania postaci.
  • Jeśli długość wyrażenia jest nieparzysta, wówczas wyrażenie jest niezrównoważone
  • Iteruj przez podane wyrażenie.
    • Jeśli bieżącym znakiem jest nawias otwierający z ( lub { lub [, then push it to stack.
    • Else if the current character is a closing bracket ) or } or ]a następnie wyskocz ze stosu.
    • Jeśli wyskakujący znak pasuje do nawiasu początkowego, kontynuuj, w przeciwnym razie nawiasy nie będą zrównoważone.
  • Po iteracji, jeśli stos jest pusty, równanie jest Zrównoważone, w przeciwnym razie równanie jest Niezrównoważone.

Możemy skorzystać z ustawionego typu danych do sprawdzania dopasowania nawiasów.

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

Możemy użyć stosu do rozwiązania wielu innych problemów. Powyższy problem jest jednym z nich. Spróbuj zastosować koncepcję stosu tam, gdzie uważasz, że najlepiej Ci to odpowiada.

Wniosek

Tak! Ukończyłeś samouczek. Mam nadzieję, że samouczek podobał ci się tak samo jak mi podczas jego tworzenia. To tyle w samouczku.

Miłego kodowania 🙂 👨‍💻