Práce se zásobníky

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software Engineer

Zásobníky

LIFO: Last-In First-Out
- Naposledy vložená položka bude první k odebrání

Obrázek zásobníku knih.

Zásobníky

LIFO: Last-In First-Out
- Naposledy vložená položka je vždy první k odebrání
Lze pouze přidávat na vrchol
- Push na zásobník

Obrázek zásobníku knih s novou knihou přidanou na vrchol zásobníku.

Zásobníky

LIFO: Last-In First-Out
- Naposledy vložená položka je vždy první k odebrání
Lze pouze přidávat na vrchol
- Push na zásobník
Lze pouze odebírat z vrcholu
- Pop ze zásobníku

Obrázek zásobníku knih s knihou odebranou z vrcholu zásobníku.

Zásobníky

LIFO: Last-In First-Out
- Naposledy vložená položka je vždy první k odebrání
Lze pouze přidávat na vrchol
- Push na zásobník
Lze pouze odebírat z vrcholu
- Pop ze zásobníku
Lze pouze číst poslední prvek
- Peek zásobníku

Obrázek zásobníku knih se šipkou ukazující na knihu na vrcholu zásobníku.

Zásobníky – reálné využití

Funkce zpět (Undo)

Zásobník s jedním prvkem.

Zásobníky – reálné využití

Funkce zpět (Undo)
- push každého stisku klávesy

Zásobník s novým prvkem přidaným na vrchol.

Zásobníky – reálné využití

Funkce zpět (Undo)
- push každého stisku klávesy

Zásobník s novým prvkem přidaným na vrchol.

Zásobníky – reálné využití

Funkce zpět (Undo)
- push každého stisku klávesy

Zásobník s novým prvkem přidaným na vrchol.

Zásobníky – reálné využití

Funkce zpět (Undo)
- push každého stisku klávesy

Zásobník s novým prvkem přidaným na vrchol.

Zásobníky – reálné využití

Funkce zpět (Undo)
- push každého stisku klávesy
- pop posledního stisku klávesy

Zásobník, ze kterého byl odebrán prvek z vrcholu.

Zásobníky – reálné využití

Kontrola symbolů: ( [ { } ] )
- push otevíracích symbolů

Zásobník s otevíracím symbolem.

Zásobníky – reálné využití

Kontrola symbolů: ( [ { } ] )
- push otevíracích symbolů

Zásobník s novým otevíracím symbolem přidaným na vrchol.

Zásobníky – reálné využití

Kontrola symbolů: ( [ { } ] )
- push otevíracích symbolů

Zásobník s novým otevíracím symbolem přidaným na vrchol.

Zásobníky – reálné využití

Kontrola symbolů: ( [ { } ] )
- push otevíracích symbolů
- kontrola zavíracího symbolu

Zásobník s otevíracími symboly a nápisem "check "}"".

Zásobníky – reálné využití

Kontrola symbolů: ( [ { } ] )
- push otevíracích symbolů
- kontrola zavíracího symbolu
- pop odpovídajícího otevíracího symbolu

Zásobník, ze kterého byl odebrán otevírací symbol z vrcholu.

Zásobníky – reálné využití

Volání funkcí
- push bloku paměti
- pop po skončení vykonávání

Zásobníky – implementace pomocí jednosměrného spojového seznamu

Zásobník reprezentovaný jako spojový seznam.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

Zásobníky – implementace pomocí jednosměrného spojového seznamu

Zásobník reprezentovaný jako spojový seznam s pojmenovanými částmi uzlů.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Zásobníky – implementace pomocí jednosměrného spojového seznamu

Zásobník reprezentovaný jako spojový seznam s nápisem "TOP" ukazujícím na vrchol zásobníku.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Zásobníky – push

Zobrazení prázdného zásobníku a zásobníku s prvky.

def push(self, data):

Zásobníky – push

Zobrazení prázdného zásobníku a zásobníku s prvky, kde bude vložen nový uzel.

def push(self, data): 
  new_node = Node(data)

  if self.top:

Zásobníky – push

Zobrazení prázdného zásobníku a zásobníku s prvky, kde je nový uzel propojen s vrchním prvkem zásobníku.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top

Zásobníky – push

Zobrazení prázdného zásobníku a zásobníku s prvky, kde byl vložen nový uzel.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node

Zásobníky – pop

def pop(self):

  if self.top is None:

    return None

  else:

Zobrazení zásobníku s nápisem "TOP" ukazujícím na uzel v jeho vrcholu.

Zásobníky – pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

Zobrazení zásobníku s nápisem "popped_node" ukazujícím na uzel v jeho vrcholu.

Zásobníky – pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

Zobrazení zásobníku s nápisem "popped_node" ukazujícím na uzel v jeho vrcholu a nápisem "TOP" ukazujícím na druhý uzel.

Zásobníky – pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

Zobrazení zásobníku s nápisem "popped_node" ukazujícím na uzel odpojený od zásobníku a nápisem "TOP" ukazujícím na uzel v jeho vrcholu.

Zásobníky – pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

Zobrazení zásobníku s nápisem "TOP" ukazujícím na uzel v jeho vrcholu.

Zásobníky – peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue v Pythonu

LifoQueue:
- Modul queue v Pythonu
- chová se jako zásobník

import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True

Lass uns üben!

Datové struktury a algoritmy v Pythonu