Pochopení implementace zásobníku v Pythonu

Datové struktury představují základní stavební kameny ve světě programování. Umožňují nám organizovat data tak, abychom s nimi mohli efektivně pracovat. Jednou z nejjednodušších, avšak klíčových datových struktur je zásobník.

Pojďme se blíže podívat na princip fungování zásobníku a jeho implementaci v jazyce Python.

Co je to zásobník?

Představte si zásobník jako hromadu knih, židlí nebo jiných předmětů, které se vrství na sebe. Zásobník se řídí pravidlem „poslední dovnitř, první ven“ (LIFO – Last-In/First-Out). Je to skutečně jednoduchá, ale mocná datová struktura. Vezměme si příklad z reálného světa.

Mějme například stoh knih, kde na sobě leží několik svazků.

Pokud bychom chtěli získat třetí knihu odshora, museli bychom nejprve odebrat první dvě knihy. Platí zde, že poslední kniha přidaná do stohu je zároveň první, kterou ze stohu můžeme odebrat. Datová struktura zásobník v programování funguje na stejném principu LIFO.

Základní operace se zásobníkem

Se zásobníkem jsou spojeny především dvě základní operace:

1. push(data)

Tato operace přidává nový prvek (data) na vrchol zásobníku.

2. pop()

Tato operace odebírá prvek z vrcholu zásobníku a vrací jeho hodnotu.

Níže naleznete ilustrativní příklady operací push a pop.

Pro lepší pochopení zásobníku si napíšeme i pomocné funkce.

Podívejme se, co umí.

peek()

Tato funkce vrací hodnotu prvku, který se nachází na vrcholu zásobníku, ale neodebírá ho.

is_empty()

Tato funkce vrací informaci, zda je zásobník prázdný či nikoliv (True/False).

Nyní, když už známe teorii, pojďme se podívat na praktickou implementaci zásobníku.

Předpokládám, že máte na svém počítači nainstalovaný Python. Pokud ne, můžete použít online kompilátor.

Implementace zásobníku v Pythonu

Implementace zásobníku patří k těm jednodušším mezi datovými strukturami. V Pythonu existuje několik způsobů, jak zásobník vytvořit.

Probereme si je jeden po druhém.

#1. Využití seznamu

Zásobník můžeme implementovat s využitím seznamu v rámci třídy. Podívejme se na to krok za krokem.

Krok 1: Vytvoříme třídu s názvem Stack.

class Stack:
	pass

Krok 2: Pro ukládání dat potřebujeme seznam. Přidejme do třídy Stack prázdný seznam s názvem elements.

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

Krok 3: Pro přidávání prvků do zásobníku potřebujeme metodu push, která přijme data jako argument a přidá je na konec seznamu elements.

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

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

Krok 4: Podobně vytvoříme metodu pop, která odstraní poslední prvek ze zásobníku. Využijeme metodu pop datového typu list.

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

Tím jsme dokončili implementaci zásobníku se základními operacemi. Nyní přidáme pomocné funkce pro získávání doplňkových informací o zásobníku.

Krok 5: K získání prvku z vrcholu zásobníku můžeme použít záporný index. Zápis [-1] vrátí poslední prvek seznamu, což je zároveň prvek z vrcholu zásobníku.

class Stack:
	## ...

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

Krok 6: Pokud je délka seznamu elements 0, znamená to, že je zásobník prázdný. Vytvoříme metodu, která zjišťuje, zda je zásobník prázdný, a vrací True/False.

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

Nyní máme plně implementovaný zásobník s použitím seznamu.

Počkat! Vytvořili jsme ho, ale ještě jsme neviděli, jak se používá. Jak s ním tedy pracovat?

Podívejme se na to. Pro jeho použití musíme vytvořit instanci (objekt) třídy Stack. Nic složitého. Pusťme se do toho.

class Stack:
    ## ...

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

Vytvořili jsme objekt zásobníku a můžeme ho začít používat. Nyní otestujeme funkčnost zásobníku pomocí následujících kroků:

• Pomocí metody is_empty ověříme, zda je zásobník prázdný. Mělo by se vrátit True.
• Pomocí metody push vložíme do zásobníku čísla 1, 2, 3, 4, 5.
• Metoda is_empty by měla nyní vrátit False. Ověříme.
• Vytiskneme prvek na vrcholu zásobníku pomocí metody peek.
• Odebereme prvek z vrcholu zásobníku pomocí metody pop.
• Opět pomocí metody peek ověříme, že prvkem na vrcholu je nyní 4.
• Nakonec odebereme všechny zbývající prvky ze zásobníku.
• Metoda is_empty by měla opět vrátit True. Ověříme.

Pokud naše implementace zásobníku projde všemi kroky, je vše v pořádku. Zkuste napsat kód pro výše uvedené kroky.

Napsali jste kód? Pokud ne, nevadí, podívejte se na řešení 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())

Skvělé! Úspěšně jsme implementovali zásobník od základů s pomocí datového typu seznam. Pokud spustíte kód výše, získáte následující výstup.

True
False
5
4
True

Seznam můžeme používat přímo jako zásobník. Výše uvedená implementace vám pomůže pochopit princip zásobníků i v jiných programovacích jazycích.

Podívejte se i na další související články.

Nyní se podívejme na vestavěný deque z modulu collections, který se také dá používat jako zásobník.

#2. deque z collections

deque (double-ended queue) je implementována jako oboustranná fronta. Podporuje tedy přidávání a odebírání prvků z obou konců, a proto ji můžeme používat i jako zásobník. Můžeme se řídit principem LIFO.

deque je interně implementována pomocí datové struktury zvané obousměrně vázaný seznam. Proto je časová náročnost přidávání a mazání prvků konzistentní. Přístup k prvkům uprostřed vázaného seznamu má časovou náročnost O(n). Vzhledem k tomu, že při práci se zásobníkem nepotřebujeme přistupovat k prostředním prvkům, je deque vhodnou alternativou pro implementaci zásobníku.

Před vlastní implementací si probereme metody, které se používají při implementaci zásobníku s využitím deque:

• append(data) – slouží pro přidání prvku (dat) na konec deque (vrchol zásobníku).
• pop() – slouží pro odstranění prvku z konce deque (vrchol zásobníku).

Pro operace peek a is_empty nemáme přímé metody. Namísto peek můžeme vypsat celý obsah zásobníku. Pro zjištění, zda je zásobník prázdný, můžeme použít funkci len.

Pojďme tedy implementovat zásobník s použitím 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 zásobník s pomocí deque z modulu collections. Po spuštění výše uvedeného kódu získáte následující výstup:

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

Zatím jsme si ukázali dva způsoby implementace zásobníku. Existují ještě další? Ano, pojďme se podívat na třetí možnost.

#3. LifoQueue

Samotný název LifoQueue nám napovídá, že tato struktura se řídí principem LIFO, a tedy ji můžeme používat jako zásobník. Je součástí modulu queue. LifoQueue poskytuje několik užitečných metod:

• put(data) – přidá (vloží) data do fronty (zásobníku).
• get() – odebere (vyjme) prvek z vrcholu fronty (zásobníku).
• empty() – vrací, zda je zásobník prázdný (True/False).
• qsize() – vrací aktuální velikost fronty (zásobníku).

Pojďme implementovat zásobník s pomocí LifoQueue z modulu queue:

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

Pokud spustíte výše uvedený kód, získáte následující výstup:

True
False
5
4
3
Size 2
2
1
True

Praktické využití zásobníku

Nyní už máte dostatečné znalosti o zásobnících, a můžeme je tedy využít k řešení problémů. Ukážeme si jeden příklad.

Zadán je výraz obsahující závorky (kulaté, hranaté a složené). Napište program, který zkontroluje, zda jsou závorky správně vyvážené.

Příklad:

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

Výstup: Vyvážený

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

Výstup: Nevyvážený

Pro řešení tohoto problému můžeme využít zásobník. Postup řešení je následující:

• Vytvoříme zásobník, do kterého budeme ukládat znaky.
• Pokud je délka výrazu lichá, je výraz nevyvážený.
• Projdeme výraz znak po znaku.
  • Pokud je aktuální znak otevírací závorkou ( ( nebo { nebo [ ), vložíme jej do zásobníku.
  • Pokud je aktuální znak uzavírací závorkou ( ) nebo } nebo ] ), odebereme prvek z vrcholu zásobníku.
  • Pokud se odebraný znak neshoduje s příslušnou otevírací závorkou, je výraz nevyvážený.
• Pokud je po průchodu celým výrazem zásobník prázdný, je výraz vyvážený, jinak je nevyvážený.

Pro kontrolu odpovídajících závorek můžeme využít datový typ 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")

Zásobníky lze využít i k řešení mnoha dalších problémů. Tento příklad je jedním z mnoha. Zkuste aplikovat koncept zásobníku i v dalších situacích, kde se to zdá vhodné.

Závěr

Gratuluji! Úspěšně jste prošli tutoriálem o zásobnících. Doufám, že se vám líbil stejně jako mně při jeho tvorbě. To je pro tento tutoriál vše.

Šťastné kódování 🙂 👨‍💻