9. Abstraktní datový typ, zásobník, fronta

LIFO - Last In First Out

Obrázek převzat z https://commons.wikimedia.org/wiki/File:Lifo_stack.svg

class Zasobnik:
    def __init__(self,data=[]):
        self.data = data
 
    def push(self,item):
        self.data += [item]
 
    def pop(self):
        if self.data: # true pokud self.data != [], alternativa len(self.data)
            return self.data.pop(-1)
        else:  # pokud self.data == []
            return None
 
    def is_empty(self):  # zjisti, jestli je zasobnik prazdny
        return self.data == []  # alternativa return len(self.data)
 

s = Zasobnik()
 
N = 4
for i in range(N):
    print("zapisuji do zasobniku cislo: {}".format(i))
    s.push(i)  #
 
for i in range(N+1):
    print("vycitam ze zasobniku cislo: {}".format(s.pop()))

* Písmeno znamená *push* znaku (toho písmena) do zásobníku
* Hvězdička znamená *pop* znaku ze zásobníku na výstup
* Pokud je znak malé písmeno, před vložením do zásobníku jej převeďte na velké písmeno
* Jiné znaky se ignorují

• Dekódujte vstup TE*A*QYS***SEU****ni*O**

zprava = 'TE*A*QYS***SEU****ni*O**'
 
s = Zasobnik()
 
# <vas kod>

s = Zasobnik()
 
vyraz = 'asdfdasfdsa)()'
 
# <vas kod>

Pomocí zásobníku realizujte funkci, která převede dekadické číslo do zvolené číselné soustavy

# <vas kod>

• Ze škol známá infixová notace je například: (4 - 1) x 5
• V přednáškách máte příklad na postfixovou notaci
• Prefixovou notací bychom stejný příklad zapsali jako: x - 4 1 5
• Nejrpve se počítá 4 - 1 a výsledek se zapíše místo trojice znaků - 4 1, čímž dostaneme: x 3 5
• Nakonec se spočítá 3 x 5 a výsledek je 15
• K implementaci je možné využít zásobník a postupně procházet sekvenci argumentů od zadu
• Pokud argument je číslo, vkládáme jej do zásobníku
• Pokud argument je operátor, vyjmeme dvě naposled vložená čísla ze zásobníku a provedeme matematickou operaci, jejíž výsledek vložíme do zásobníku
• Po projití všech argumentů zbyde v zásobníku výsledek

# <vas kod>

FIFO - First In First Out

Obrázek převzat z https://cs.m.wikipedia.org/wiki/Soubor:Data_Queue.svg

class Fronta:
    def __init__(self,data=[]):
        self.data = data
 
    def enque(self,item):
        self.data += [item]
 
    def deque(self):
        if self.data: # true pokud self.data != [], alternativa len(self.data)
            return self.data.pop(0)
        else:  # pokud self.data == []
            return None
 
    def is_empty(self):  # zjisti, jestli je zasobnik prazdny
        return self.data == []  # alternativa return len(self.data)
 

s = Fronta()
 
N = 4
for i in range(N):
    print("zapisuji do fronty cislo: {}".format(i))
    s.enque(i)  #
 
for i in range(N+1):
    print("vycitam z fronty cislo: {}".format(s.deque()))