A stoh je lineárna dátová štruktúra, ktorá ukladá položky do a Last-In/First-Out (LIFO) alebo First-In/Last-Out (FILO). V zásobníku sa nový prvok pridá na jeden koniec a prvok sa odstráni iba z tohto konca. Operácie vloženia a vymazania sa často nazývajú push a pop.

Funkcie spojené so zásobníkom sú:

• prázdne () – Vráti, či je zásobník prázdny – Časová zložitosť: O(1)
• veľkosť () – Vráti veľkosť zásobníka – Časová zložitosť: O(1)
• top() / peek() – Vráti odkaz na najvyšší prvok zásobníka – Časová zložitosť: O(1)
• tlačiť (a) – Vloží prvok „a“ na vrch zásobníka – Časová zložitosť: O(1)
• pop() – Odstráni najvyšší prvok zásobníka – Časová zložitosť: O(1)

Implementácia:

V Pythone je možné implementovať zásobník rôznymi spôsobmi. Tento článok popisuje implementáciu zásobníka pomocou dátových štruktúr a modulov z knižnice Python.
Stack v Pythone je možné implementovať nasledujúcimi spôsobmi:

• zoznam
• Collections.deque
• fronta.LifoQueue

Implementácia pomocou zoznamu:

Zoznam vstavaných dátových štruktúr Pythonu možno použiť ako zásobník. Namiesto push() sa append() používa na pridávanie prvkov do hornej časti zásobníka, zatiaľ čo pop() odstraňuje prvok v poradí LIFO.
Bohužiaľ, zoznam má niekoľko nedostatkov. Najväčším problémom je, že pri raste môže naraziť na problémy s rýchlosťou. Položky v zozname sú uložené vedľa seba v pamäti, ak sa zásobník zväčší ako blok pamäte, ktorý ho momentálne drží, potom Python potrebuje vykonať nejaké pridelenie pamäte. To môže viesť k tomu, že niektoré volania append() budú trvať oveľa dlhšie ako iné.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Implementácia pomocou collections.deque:

Zásobník Pythonu je možné implementovať pomocou triedy deque z modulu kolekcií. Deque sa uprednostňuje pred zoznamom v prípadoch, keď potrebujeme rýchlejšie operácie pripojenia a pop z oboch koncov kontajnera, pretože deque poskytuje časovú zložitosť O(1) pre operácie pripojenia a pop v porovnaní so zoznamom, ktorý poskytuje O(n) časová zložitosť.

Používajú sa rovnaké metódy na deque, aké sú uvedené v zozname, append() a pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Implementácia pomocou queue modulu

Queue modul má tiež LIFO Queue, čo je v podstate zásobník. Údaje sa vkladajú do frontu pomocou funkcie put() a get() vyberá údaje z frontu.

V tomto module sú k dispozícii rôzne funkcie:

• maxsize – Počet povolených položiek vo fronte.
• prázdne () – Ak je front prázdny, vráťte hodnotu True, inak hodnotu False.
• plný() – Vráťte True, ak existujú maxsize položky v poradí. Ak bol front inicializovaný s maxsize=0 (predvolená hodnota), full() nikdy nevráti True.
• dostať () – Odstráňte a vráťte položku z frontu. Ak je front prázdny, počkajte, kým bude položka k dispozícii.
• get_nowait() – Vráťte položku, ak je okamžite dostupná, inak zvýšte QueueEmpty.
• vložiť (položka) – Zaraďte položku do frontu. Ak je front plný, pred pridaním položky počkajte, kým sa neuvoľní voľné miesto.
• put_nowait(položka) – Zaraďte položku do frontu bez blokovania. Ak nie je okamžite k dispozícii žiadny voľný slot, zvýšte QueueFull.
• qsize() – Vráti počet položiek vo fronte.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Implementácia pomocou jedného prepojeného zoznamu:

Prepojený zoznam má dve metódy addHead(item) a removeHead(), ktoré bežia v konštantnom čase. Tieto dve metódy sú vhodné na implementáciu zásobníka.

• getSize() - Získajte počet položiek v zásobníku.
• je prázdny() – Ak je zásobník prázdny, vráti hodnotu True, v opačnom prípade vráti hodnotu False.
• nahliadnuť () – Vráťte vrchnú položku v stohu. Ak je zásobník prázdny, vyvolajte výnimku.
• push (hodnota) – Vložte hodnotu do hlavy zásobníka.
• pop() – Odstráňte a vráťte hodnotu v záhlaví zásobníka. Ak je zásobník prázdny, vyvolajte výnimku.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Získajte aktuálnu veľkosť zásobníka def getSize(self): return self.size # Skontrolujte, či je zásobník prázdny def isEmpty(self): return self.size = = 0 # Získajte vrchnú položku zásobníka def peek(self): # Sanitárna kontrola, či # nepozeráme na prázdny zásobník. if self.isEmpty(): return None return self.head.next.value # Vloží hodnotu do zásobníka. def push(self, value): node = Node(value) node.next = self.head.next # Aby nový uzol ukazoval na aktuálnu hlavu self.head.next = node #!!! # Aktualizujte hlavu tak, aby bola novým uzlom self.size += 1 # Odstráňte hodnotu zo zásobníka a vráťte sa späť. def pop(self): if self.isEmpty(): raise Exception('Vyskakovanie z prázdneho zásobníka') remove = self.head.next self.head.next = remove.next #!!! zmenená self.size -= 1 return remove.value # Driver Code if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Zásobník: {zásobník}') pre _ v rozsahu(1, 6): top_value = zásobník.pop() print(f'Pop: {top_value}') # názov premennej zmenený print(f'Zásobník: { stack}')>

Výkon

Stack: 10->9->8->7->6->5->4->3->2->1 Pop: 10 Pop: 9 Pop: 8 Pop: 7 Pop: 6 Stoh: 5->4->3->2->1>

Výhody Stack:

• Zásobníky sú jednoduché dátové štruktúry s dobre definovanou sadou operácií, vďaka čomu sú ľahko pochopiteľné a použiteľné.
• Zásobníky sú efektívne na pridávanie a odstraňovanie prvkov, keďže tieto operácie majú časovú zložitosť O(1).
• Aby sme obrátili poradie prvkov, používame dátovú štruktúru zásobníka.
• Zásobníky možno použiť na implementáciu funkcií späť/znova v aplikáciách.

Nevýhody zásobníka:

• Obmedzenie veľkosti v zásobníku je nevýhodou a ak sú plné, nemôžete do zásobníka pridať žiadne ďalšie prvky.
• Stohy neposkytujú rýchly prístup k iným prvkom ako k hornému prvku.
• Hromady nepodporujú efektívne vyhľadávanie, pretože musíte vyskakovať prvky jeden po druhom, kým nenájdete prvok, ktorý hľadáte.