Vrsta in sklad

Tipične operacije za vrsto so izdelava, dodajanje elementa, odvzemanje elementa in preverjanje praznosti. Operacije bomo zapisali kar kot pythonove funkcije, saj jih bomo z njimi tudi implementirali:

Ustvari(): Vrne prazno vrsto.
Dodaj(vrsta, element): Doda podani element v vrsto.
Odvzemi(vrsta): Odstrani element iz vrste in vrne odstranjeni element.
JePrazna(vrsta): Vrne True, če je vrsta prazna, sicer pa vrne False.

Sklad ima povsem enakovreden nabor operacij.

Ker sta vrsta in sklad posebna primera zaporedja, ju lahko implementiramo s tabelo elementov ali pa s povezanim seznamom. Če vrsto implementiramo s tabelo, bo dodajanje učinkovito, odvzemanje pa ne. (Zakaj?) Zato vrsto raje implementiramo s povezanim seznamom. Pri skladu pa elemente tako dodajamo kot odvzemamo samo na koncu. Za ti dve operaciji sta obe implementaciji učinkoviti, zaradi enostavnosti pa se raje odločimo za tabelo.

Funkcije za obdelavo vrste in sklada bomo zapisali v modula vrsta.py in sklad.py. Ker vrsto implementiramo s povezanim seznamom, v modulu vrsta.py uvozimo modul povezaniSeznam.py. Če si razdelek o povezanem seznamu preskočil(-a), nič hudega. Za razumevanje funkcij v modulu ti ni treba poznati podrobnosti zgradbe in operacij povezanega seznama.

Datoteki vrsta.py in sklad.py sta videti takole:

Simulacija

S pomočjo interaktivne simulacije razišči vrsto (ang. queue), ki je implementirana s povezanim seznamom (ang. linked list). V vrsto lahko elemente dodajaš ali pa jih iz vrste odstranjuješ.

Modul `vrsta.py`

# Ta modul vsebuje osnovne operacije za delo # z vrsto. Vrsta je implementirana kot povezani # seznam. import povezaniSeznam as sez # Ustvari in vrne prazno vrsto. def Ustvari(): return sez.Ustvari() # Doda element v vrsto. def Dodaj(vrsta, element): sez.DodajNaKonec(vrsta, element) # Odvzame element iz vrste in vrne odvzeti # element. def Odvzemi(vrsta): indeks = sez.IndeksZacetnega(vrsta) element = sez.Element(vrsta, indeks) sez.IzlociZacetnega(vrsta) return element # Vrne True natanko v primeru, če je vrsta # prazna. def JePrazna(vrsta): return (sez.SteviloElementov(vrsta) == 0) # Pomožna funkcija za izpis elementov vrste. def Izpisi(vrsta): print(sez.Zaporedje(vrsta)) # Ta funkcija se izvede, če datoteko zaženemo # kot samostojen program. def main(): vrsta = Ustvari() print('Dodamo A v vrsto ...') Dodaj(vrsta, 'A') Izpisi(vrsta) print('Dodamo B v vrsto ...') Dodaj(vrsta, 'B') Izpisi(vrsta) print('Dodamo C v vrsto ...') Dodaj(vrsta, 'C') Izpisi(vrsta) if JePrazna(vrsta): print('Vrsta je prazna.') else: print('Vrsta ni prazna.') print('') print('Odvzamemo element iz vrste ...') Odvzemi(vrsta) Izpisi(vrsta) print('Odvzamemo element iz vrste ...') Odvzemi(vrsta) Izpisi(vrsta) print('Odvzamemo element iz vrste ...') Odvzemi(vrsta) Izpisi(vrsta) if JePrazna(vrsta): print('Vrsta je prazna.') else: print('Vrsta ni prazna.') if __name__ == '__main__': main()

Izvedi Počisti

Vrsta in sklad

Simulacija

Modul vrsta.py

Modul `vrsta.py`