• Sklad
• Operacije nad skladom
• Signatura operacij na skladu
• Aksiomi za sklad
• Osnovni hipotezi
• Implementacija
• Naloga
• Prosta implementacija sklada
• Implementacija sklada s tabelo
• Vrsta
• Operacije nad vrsto
• Signatura operacij na vrsti
• Aksiomi za vrsto 1/2
• Aksiomi za vrsto 2/2
• Implementacija vrste
• Implementacija vrste s tabelo
• Implementacija vrste s krožno tabelo

Sklad je podatkovna struktura, ki deluje po načelu LIFO (Last In First Out - zadnji noter, prvi ven). To pomeni, da podatek, ki je zadnji prišel v sklad, ga bo tudi prvi zapustil.

Parameter element nam predstavlja podatkovni tip podatkov, ki jih shranjujemo na sklad in je lahko integer, string, ...

Nad skladom imamo naslednje operacije:

• Pripravi: Sklad
• Vstavi: Sklad Element Sklad
• Odstrani: Sklad Sklad
• Vrh: Sklad Element
• JePrazen: Sklad Boolean
• StElementov*: Sklad
  

• StElementov običajno ni del signature sklada.

  

• JePrazen[Pripravi[]] := True
  
• JePrazen[Vstavvi[s_,e_]] := False
  
• Vrh[Pripravi[]] := Null
  
• Vrh[Vstavi[s,e]] := e
  
• Odstrani[Pripravi[]] := Pripravi[]
  (*Lahko bi ugotovili napako.*)
  
• Odsrani[Vstavi[s,e]] := s
  (* s Sklad, e Element*)
  

• Vsaka implementacija sklada mora zadoščati tem aksionom.
  
  
• Uporaba sklada lahko poteka zgolj preko teh opreacij. Vsako poseganje v notranjo zgradbo sklada pomeni v bistvu NOVO podatkovno strukturo!

Napiši program, ki vrne dolžino sklada (=StElementov). Pri tem uporabi samo operacije nad skladom.

• Sklad predstavimo kot sintaktično pravilni izraz tipa "Sklad".
  
• S = Vstavi[Vstavi[Pripravi[], "a"], "b"]
  
• T = Odstrani[Vstavi[Vstavi[Vstavi[Pripravi[], "a"],"b"],"c"]]
  

• Sklada S in T sta enaka!
  
• Vrh[S] "b"
  
• JePrazen[S] False
  
• Vrh[Odstrani[S]] "a"
  

• Vstavi[s,e]
  
• vrh := vrh + 1
  
• svrh := e
  
• Podobno sprogramiramo ostale opreacije.
• Pozor: Paziti moramo na prekoračitev obsega.

Vrsta je podatkovna struktura, ki deluje po načelu FIFO (Frst In First Out - prvi noter, prvi ven). To pomeni, da podatek, ki je prvi prišel v vrsto, ga bo tudi prvi zapustil.

Nad vrsto imamo naslednje operacije:

• Pripravi: Vrsta
• Vstavi: Vrsta Element Vrsta
• Odstrani: Vrsta Vrsta
• JePrazen: Vrsta Boolean
• Čelo: Vrsta Element
  
• Rep: Vrsta Element
  

• Odstrani[Pripravi[]] := Pripravi[]
  
• Odstrani[Vstavi[v,e]] := If[JePraPripzna[v],
  Pripravi[], Vstavi[Odstrani[v],e]]
  
• Čelo[Pripravi[]] := Null
  
• Čelo[Vstavi[v,e]] := If[JePrazna[v], e, Čelo[v]]
  
• Rep[Pripravi[]] := Null
  
• Rep[Vstavi[v,e]] := e
  
• JePrazna[Pripravi[]] := True
  
• JePrazna[Vstavi[v,e]] := False
  

Namesto

• Odstrani[Vstavi[v,e]] := If[JePrazna[v],
  Pripravi[], Vstavi[Odstrani[v],e]
  
  bi lahko pisali
• Odstrani[Vstavi[Pripravi[],e]] := Pripravi[]
  
• Odstrani[Vstavi[Vstavi[v,x],y]] :=
  Vstavi[Odstrani[Vstavi[v,x]],y]
  

Prosta immplementacija vrste

• Podobno kot pri skladu
  
  Implementacija s tabelo
  
• Linearna predstavitev.
  
• Dobra implementacija je zahtevnejša kot pri skladu, paziti moramo na prekoračitev obsega.

• Oba kazalca (čelo in rep) potujeta v desno
  
• Ko v vrsto dodajamo elemente, jih dodajamo na rep, ki potuje v desno.
  
• Ko elemente brišemo iz vrste, jih brišemo iz čela. Čelo potuje v desno.
  
• Slej ko prej zapolnemo tabelo (z repom pridemo skrajno v desno). Sproščeni prostor v tabeli levo od čela je neizkoriščen.
  
• Teh težav pri skladu nimamo, saj na sklad dajemo in jemljemo iz istega konca.
  

• Implementacijo lahko malo "polepšamo", če posebej obravnavamo premike indeksov v krožni tabeli in uvedemo "iteratorje":
  
• Prvi, Naslednji, Prejšnji
  
• Potem lahko pišemo
  
• i Prvi[];
  
• i Naslednji[i];
  

• i Prejšnji[i];