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

Modul vrsta.py

 
1
# Ta modul vsebuje osnovne operacije za delo
2
# z vrsto. Vrsta je implementirana kot povezani
3
# seznam.
4
​
5
import povezaniSeznam as sez
6
​
7
# Ustvari in vrne prazno vrsto.
8
def Ustvari():
9
  return sez.Ustvari()
10
​
11
# Doda element v vrsto.
12
def Dodaj(vrsta, element):
13
  sez.DodajNaKonec(vrsta, element)
14
​
15
# Odvzame element iz vrste in vrne odvzeti
16
# element.
17
def Odvzemi(vrsta):
18
  indeks = sez.IndeksZacetnega(vrsta)
19
  element = sez.Element(vrsta, indeks)
20
  sez.IzlociZacetnega(vrsta)
21
  return element
22
​
23
# Vrne True natanko v primeru, če je vrsta
24
# prazna.
25
def JePrazna(vrsta):
26
  return (sez.SteviloElementov(vrsta) == 0)
27
​
28
# Pomožna funkcija za izpis elementov vrste.
29
def Izpisi(vrsta):
30
  print(sez.Zaporedje(vrsta))
31
​
32
# Ta funkcija se izvede, če datoteko zaženemo
33
# kot samostojen program.
34
def main():
35
  vrsta = Ustvari()
36
​
37
  print('Dodamo A v vrsto ...')
38
  Dodaj(vrsta, 'A')
39
  Izpisi(vrsta)
40
​
41
  print('Dodamo B v vrsto ...')
42
  Dodaj(vrsta, 'B')
43
  Izpisi(vrsta)
44
​
45
  print('Dodamo C v vrsto ...')
46
  Dodaj(vrsta, 'C')
47
  Izpisi(vrsta)
48
​
49
  if JePrazna(vrsta):

Izvedi Počisti