• Podatkovna struktura

  • Skladišče podatkov

• Osnovni operaciji

  • Vstavi v strukturo
  • Vzemi iz strukture

• Različne PS

  • Glede na obnašanje osnovnih operacij

  • Sklad:

    • Iz strukture dobimo vedno tistega, ki je NAJMANJ časa (med tistimi podatki, ki so v strukturi) v skladu

• Prvi noter, prvi ven – FIFO
• Iz strukture želimo dobiti tistega, ki čaka najdlje (torej tistega, ki je med obstoječimi elementi najdlje v strukturi)
• povsod, kjer se moramo držati vrstnega reda prihoda
• simulacije, tiskanje, …

• različice: vrsta s prednostjo, ...

• vstavljamo na enem koncu, jemljemo iz drugega

• operacije

  • pripravi vrsto
  • vstavi element v vrsto
  • element na začetku vrste
  • odstrani
  • prazna

structure VRSTA
declare
pripravi: 0 vrsta;
vstavi: (vrsta, podatek) vrsta;
zacetek: vrsta podatek;
odstrani: vrsta vrsta;
prazna: vrsta {true, false};
where
prazna(pripravi) ::= true;
prazna(vstavi(v,p)) ::= false;
odstrani(pripravi) ::= NAPAKA;
odstrani(vstavi(v,p)) ::=
if (prazna(v)) then pripravi
else vstavi(odstrani(v),p);
zacetek(pripravi) ::= NAPAKA;
zacetek(vstavi(v,p)) ::=
if (prazna(v)) then p
else zacetek(v);
end;

• Naloge:

  • S pomočjo osnovnih operacij nad vrsto sestavi operacijo n-ti, ki vrne podatek o n-tem elementu v vrsti, če ta obstaja
  • Odstrani n-ti element iz vrste
  • Obrni vrstni red elementov v vrsti
  • Iz dveh urejenih vrst naredi urejeno vrsto

• Denimo, da vrste potem ne potrebujemo več
• N-1 x odstranimo element
• Vrnemo začetek

• n-1 x odstrani in shrani
• Odstrani n-ti
• Ponovno vstavi shranjene

• Bo v redu?

  • (odstrani tretjega)
  • , si zapomnimo
  • Ostane , , ,

  • Ko bomo vstavljali

    • Dobimo lahko , , , , , (kdaj?)
    • Ali pa , , , , , (kdaj?)
  • Potrebujemo , , , , , !!

• Preložiti potrebno celotno vrsto, le n-tega spustimo!
• n-1 x odstrani in shrani v vrsto
• Odstrani n-ti
• Odstrani še preostale in shranjuj v vrsto
• Rezultat – nova vrsta!

• Pregledamo vrsto – shranjujemo v sklad
• Iz sklad preložimo nazaj
• Sklad je obrnil vrstni red elementov!

Uporaba vrste