A zásobník je lineární datová struktura, která ukládá položky v a Last-In/First-Out (LIFO) nebo First-In/Last-Out (FILO) způsobem. V zásobníku je nový prvek přidán na jeden konec a prvek je odstraněn pouze z tohoto konce. Operace vložení a odstranění se často nazývají push a pop.

Funkce spojené se zásobníkem jsou:

• prázdný() – Vrací, zda je zásobník prázdný – Časová složitost: O(1)
• velikost() – Vrátí velikost zásobníku – Časová složitost: O(1)
• top() / peek() – Vrátí odkaz na nejvyšší prvek zásobníku – Časová složitost: O(1)
• tlačit (a) – Vloží prvek „a“ do horní části zásobníku – Časová složitost: O(1)
• pop() – Odstraní nejvyšší prvek zásobníku – Časová složitost: O(1)

Implementace:

Existují různé způsoby, jak lze zásobník implementovat v Pythonu. Tento článek popisuje implementaci zásobníku pomocí datových struktur a modulů z knihovny Python.
Stack v Pythonu lze implementovat pomocí následujících způsobů:

• seznam
• Collections.deque
• fronta.LifoQueue

Implementace pomocí seznamu:

Vestavěný seznam datových struktur Pythonu lze použít jako zásobník. Místo push() se append() používá k přidávání prvků na vrchol zásobníku, zatímco pop() odstraňuje prvek v pořadí LIFO.
Bohužel seznam má pár nedostatků. Největším problémem je, že může narazit na problémy s rychlostí, jak roste. Položky v seznamu jsou uloženy vedle sebe v paměti, pokud zásobník naroste větší než blok paměti, který jej aktuálně drží, pak Python potřebuje provést nějaké přidělení paměti. To může vést k tomu, že některá volání append() budou trvat mnohem déle než jiná.

# 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: []>

Implementace pomocí collections.deque:

Zásobník Pythonu lze implementovat pomocí třídy deque z modulu collections. Deque je preferováno před seznamem v případech, kdy potřebujeme rychlejší operace připojení a pop z obou konců kontejneru, protože deque poskytuje časovou složitost O(1) pro operace připojení a pop ve srovnání se seznamem, který poskytuje O(n) časovou složitost.

Na deque se používají stejné metody, jaké jsou uvedeny v seznamu, 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([])>

Implementace pomocí modulu front

Queue modul má také LIFO Queue, což je v podstatě Stack. Data se vkládají do fronty pomocí funkce put() a get() odebírá data z fronty.

V tomto modulu jsou k dispozici různé funkce:

• maximální velikost – Počet povolených položek ve frontě.
• prázdný() – Vraťte True, pokud je fronta prázdná, False v opačném případě.
• plný() – Vraťte True, pokud existují maximální velikost položky ve frontě. Pokud byla fronta inicializována s maxsize=0 (výchozí), pak full() nikdy nevrátí True.
• dostat() – Odebrat a vrátit položku z fronty. Pokud je fronta prázdná, počkejte, až bude položka k dispozici.
• get_nowait() – Vraťte položku, pokud je okamžitě k dispozici, v opačném případě zvyšte QueueEmpty.
• dát (položka) – Zařaďte položku do fronty. Pokud je fronta plná, před přidáním položky počkejte, dokud nebude k dispozici volné místo.
• put_nowait(položka) – Vložte položku do fronty bez blokování. Pokud není okamžitě k dispozici žádný volný slot, zvyšte QueueFull.
• qsize() – Vraťte počet položek ve frontě.

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

Implementace pomocí jednoduše propojeného seznamu:

Propojený seznam má dvě metody addHead(item) a removeHead(), které běží v konstantním čase. Tyto dvě metody jsou vhodné pro implementaci zásobníku.

• getSize() – Získejte počet položek v zásobníku.
• je prázdný() – Vraťte True, pokud je zásobník prázdný, False v opačném případě.
• nahlédnout () – Vraťte vrchní položku ze stohu. Pokud je zásobník prázdný, aktivujte výjimku.
• push (hodnota) – Vložte hodnotu do horní části zásobníku.
• pop() – Odeberte a vraťte hodnotu v záhlaví zásobníku. Pokud je zásobník prázdný, aktivujte výjimku.

Níže je uvedena implementace výše uvedeného pří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ískejte aktuální velikost zásobníku def getSize(self): return self.size # Zkontrolujte, zda je zásobník prázdný def isEmpty(self): return self.size = = 0 # Získejte horní položku zásobníku def peek(self): # Sanitární kontrola, zda # nenahlížíme do prázdného zásobníku. if self.isEmpty(): return None return self.head.next.value # Vloží hodnotu do zásobníku. def push(self, value): node = Node(value) node.next = self.head.next # Udělejte nový uzel tak, aby ukazoval na aktuální hlavu self.head.next = node #!!! # Aktualizujte hlavičku na nový uzel self.size += 1 # Odeberte hodnotu ze zásobníku a vraťte se. def pop(self): if self.isEmpty(): raise Exception('Vyskakování z prázdného zásobníku') remove = self.head.next self.head.next = remove.next #!!! změněno 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}') pro _ v rozsahu(1, 6): top_value = zásobník.pop() print(f'Pop: {top_value}') # název proměnné změněn print(f'Zásobník: { stack}')>

Výstup

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 jsou jednoduché datové struktury s dobře definovanou sadou operací, díky čemuž jsou snadno pochopitelné a použitelné.
• Zásobníky jsou efektivní pro přidávání a odebírání prvků, protože tyto operace mají časovou složitost O(1).
• Abychom obrátili pořadí prvků, používáme datovou strukturu zásobníku.
• Zásobníky lze použít k implementaci funkcí zpět/znovu v aplikacích.

Nevýhody Stack:

• Omezení velikosti v zásobníku je nevýhodou a pokud jsou plné, nemůžete do zásobníku přidat žádné další prvky.
• Zásobníky neposkytují rychlý přístup k jiným prvkům než k hornímu prvku.
• Zásobníky nepodporují efektivní vyhledávání, protože prvky musíte vyskakovat jeden po druhém, dokud nenajdete prvek, který hledáte.