Pochopení implementace zásobníku v Pythonu

Datové struktury hrají klíčovou roli ve světě programování. Pomáhají nám organizovat naše data způsobem, který lze efektivně využít. Zásobník je jednou z nejjednodušších datových struktur.

Pojďme se dozvědět o zásobníku a jeho implementaci v Pythonu.

Co je zásobník?

Stoh je podobný hromadě knih, židlí atd. v reálném životě. A řídí se principem Last-in/First-out (LIFO). Je to nejjednodušší datová struktura. Podívejme se na scénář na příkladu ze skutečného světa.

Řekněme, že máme hromadu knih následovně.

Když pak chceme třetí knihu shora, musíme odstranit první dvě knihy shora, abychom mohli vyjmout třetí knihu. Zde platí, že nejvyšší kniha jde poslední na hromádku a je první z hromádky. Zásobník datových struktur se při programování řídí stejným principem Last-in/First-out (LIFO).

Operace ve Stacku

V zásobníku jsou hlavně dvě operace

1. push (data)

Přidá nebo vloží data do zásobníku.

2. pop()

Odebere nebo vyjme nejvyšší prvek ze zásobníku.

Viz níže uvedené ilustrace operací push a pop.

Napíšeme nějaké pomocné funkce, které nám pomohou získat více informací o zásobníku.

Pojďme se na ně podívat.

nahlédnout ()

Vrátí nejvyšší prvek ze zásobníku.

je prázdný()

Vrací, zda je zásobník prázdný nebo ne.

Dost koncepčních aspektů datové struktury zásobníku. Pojďme se bez dalších okolků vrhnout na implementaci.

Předpokládám, že máte na svém PC nainstalovaný python, pokud ne, můžete také vyzkoušet online kompilátor.

Implementace zásobníku

Implementace zásobníku je ve srovnání s jinými implementacemi datových struktur nejjednodušší. V Pythonu můžeme implementovat zásobník několika způsoby.

Podívejme se na všechny jeden po druhém.

#1. Seznam

Budeme implementovat zásobník pomocí seznamu ve třídě. Podívejme se na implementaci zásobníku krok za krokem.

Krok 1: Napište třídu s názvem Stack.

class Stack:
	pass

Krok 2: Musíme udržovat data v seznamu. Přidejme prázdný seznam do třídy Stack s prvky name.

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

Krok 3: Abychom vložili prvky do zásobníku, potřebujeme metodu. Pojďme napsat metodu push, která vezme data jako argument a připojí je k seznamu prvků.

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

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

Krok 4: Podobně napišme metodu pop, která vysune nejvyšší prvek ze zásobníku. Můžeme použít metodu pop datového typu list.

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

Dokončili jsme implementaci zásobníku s požadovanými operacemi. Nyní přidejte pomocné funkce, abyste získali více informací o zásobníku.

Krok 5: Můžeme získat nejvyšší prvek ze zásobníku pomocí záporného indexu. Prvek kódu [-1] vrátí poslední ze seznamu. V našem případě je to nejvyšší prvek zásobníku.

class Stack:
	## ...

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

Krok 6: Pokud je délka seznamu prvků 0, pak je zásobník prázdný. Pojďme napsat metodu, která vrátí, zda je prvek prázdný nebo ne.

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

Dokončili jsme implementaci zásobníku pomocí datového typu seznamu.

Ach! Počkejte, právě jsme to implementovali. Ale neviděl jsem, jak to použít. Jak to potom použít?

Pojďte se podívat, jak to implementovat. Abychom ho mohli používat, musíme vytvořit objekt pro třídu Stack. O nic nejde. Udělejme to jako první.

class Stack: 
    ## ...

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

Vytvořili jsme objekt zásobníku a jsme připraveni jej použít. Provedeme níže uvedené kroky a otestujeme operace zásobníku.

• Pomocí metody is_empty zkontrolujte, zda je zásobník prázdný nebo ne. Mělo by vrátit True.
• Zatlačte čísla 1, 2, 3, 4, 5 do zásobníku pomocí metody push.
• Metoda is_empty by měla vrátit hodnotu False. Zkontroluj to.
• Vytiskněte nejvyšší prvek pomocí metody náhledu.
• Vyjměte prvek ze zásobníku pomocí metody pop.
• Zkontrolujte prvek náhledu. Měl by vrátit prvek 4.
• Nyní vyjměte všechny prvky ze zásobníku.
• Metoda is_empty by měla vrátit True. Zkontroluj to.

Naše implementace zásobníku je dokončena, pokud projde všemi výše uvedenými kroky. Zkuste napsat kód pro výše uvedené kroky.

Napsal jsi kód? Ne, nebojte se, zkontrolujte kód níže.

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

Hurá! dokončili jsme implementaci zásobníku od začátku pomocí datového typu seznamu. Pokud spustíte výše uvedený kód, uvidíte výstup, jak je uvedeno níže.

True
False
5
4
True

Datový typ seznamu můžeme přímo použít jako zásobník. Výše uvedená implementace zásobníku vám pomůže pochopit implementaci zásobníku také v jiných programovacích jazycích.

Můžete se také podívat na tento seznam souvisejících článků.

Podívejme se na vestavěný deque z vestavěného modulu sbírek, který může fungovat jako zásobník.

#2. deque ze sbírek

Je implementován jako dvojitá fronta. Protože podporuje přidávání a odebírání prvků z obou konců. Můžeme jej tedy použít jako zásobník. Můžeme to udělat podle principu LIFO zásobníku.

Je implementován pomocí jiných datových struktur nazývaných dvojitě propojený seznam. Výkon vkládání a mazání prvků je tedy konzistentní. Přístup k prvkům z prostředního propojeného seznamu trval O(n) čas. Můžeme jej použít jako zásobník, protože není potřeba přistupovat k prostředním prvkům ze zásobníku.

Před implementací zásobníku se podívejme na metody, které se používají k implementaci zásobníku pomocí fronty.

• append(data) – používá se k odeslání dat do zásobníku
• pop() – používá se k odstranění nejvyššího prvku ze zásobníku

Neexistují žádné alternativní metody pro nahlédnutí a is_empty. Můžeme vytisknout celý stoh namísto metody peek. Dále můžeme pomocí metody len zkontrolovat, zda je zásobník prázdný nebo ne.

Pojďme implementovat zásobník pomocí deque z modulu 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)

A je to. Naučili jsme se implementovat stack pomocí deque z vestavěného modulu collections. Pokud spustíte výše uvedený program, získáte výstup, jak je uvedeno níže.

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

Doposud jsme viděli dva způsoby implementace zásobníku. Existují nějaké jiné způsoby, jak implementovat zásobník? To jo! Podívejme se v tomto tutoriálu na konečný způsob implementace zásobníku.

#3. LifoQueue

Samotný název LifoQueue říká, že se řídí principem LIFO. Můžeme jej tedy bez jakýchkoli pochyb použít jako zásobník. Je z fronty vestavěných modulů. LifoQueue poskytuje několik užitečných metod, které jsou užitečné při implementaci zásobníku. Pojďme se na ně podívat

• put(data) – přidá nebo přesune data do fronty
• get() – odebere nebo vyjme nejvyšší prvek z fronty
• empty() – vrátí, zda je zásobník prázdný nebo ne
• qsize() – vrátí délku fronty

Pojďme implementovat zásobník pomocí LifoQueue z modulu fronty.

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

Níže uvedený výstup získáte, pokud spustíte výše uvedený program bez jeho změny.

True
False
5
4
3
Size 2
2
1
True

Aplikace Stack

Nyní máte dostatečné znalosti o zásobníkech, abyste je mohli použít v programovacích problémech. Podívejme se na problém a vyřešme jej pomocí zásobníku.

Zadaný výraz napište program, který zkontroluje, zda jsou závorky, složené závorky a složené závorky správně vyváženy nebo ne.

Podívejme se na několik příkladů.

Vstup: „[{}]([])”

Výstup: Vyvážený

Vstup: „{[}]([])”

Výstup: Nevyvážený

K vyřešení výše uvedeného problému můžeme použít zásobník. Podívejme se na kroky k vyřešení problému.

• Vytvořte hromádku pro uložení postav.
• Pokud je délka výrazu lichá, pak je výraz Nevyvážený
• Iterujte daný výraz.
  • Pokud je aktuální znak počáteční závorkou od ( nebo { nebo [, then push it to stack.
  • Else if the current character is a closing bracket ) or } or ]pak vytáhněte ze zásobníku.
  • Pokud se vyskakovaný znak shoduje s počáteční závorkou, pokračujte, jinak závorky nejsou vyvážené.
• Pokud je po iteraci zásobník prázdný, pak je rovnice Vyvážená, jinak je rovnice Nevyvážená.

Nastavený datový typ můžeme využít pro kontrolu shody závorek.

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

Zásobník můžeme použít k vyřešení mnoha dalších problémů. Výše uvedený problém je jedním z nich. Pokuste se aplikovat koncept zásobníku všude tam, kde si myslíte, že vám nejlépe vyhovuje.

Závěr

Jo! Dokončili jste výukový program. Doufám, že se vám návod líbil stejně jako mě při jeho tvorbě. To je pro tutoriál vše.

Veselé kódování 🙂 👨‍💻