• 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

• pripravi
• vstavi(A)
• vstavi(B)
• odstrani
• vstavi(C)
• odstrani
• odstrani
• vstavi(D)
• vstavi(E)
• odstrani
• odstrani
• vstavi(F)
• odstrani
• odstrani

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?

  • 1 2 3 4 5 6 7 (odstrani tretjega)
  • 1, 2 si zapomnimo
  • Ostane 4, 5, 6, 7

  • Ko bomo vstavljali

    • Dobimo lahko 4, 5, 6, 7, 1, 2 (kdaj?)
    • Ali pa 4, 5, 6, 7, 2, 1 (kdaj?)
  • Potrebujemo 1, 2, 4, 5, 6, 7 !!

• 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!

• Tabela

  • Problem "drsenja vrste"

• krožna tabela

  • Odpravimo problem drsenja
  • Operacije po modulu dolžine tabele
  • Kako ločiti prazno/polno vrsto?

• verižni seznam

  • Referenca na prvega
  • Referenca na prvega in zadnjega

• Kje hranimo podatke

• Različne možnosti

  • Tabela
  • Verižni (povezani) seznam
  • ...

• Elemente hranimo v tabeli

• Potrebujemo še indeks konca

  • indeks zadnjega vstavljenega elementa
  • indeks prvega prostega mesta

•  private T[] vr; 
•  private int kon; // indeks prostora za nasl. Element
• pripravi, vstavi, vstavi, vstavi, odstrani

• Prvi (začetek) je vedno na 0
• ni težav z zapisom

• problemi:

  • Počasna metoda odstrani!

    • Prelaganje elementov!
    • Začetek je vedno na 0!
  • omejena velikost

• Elemente hranimo v tabeli

• Potrebujemo indeks konca

  • indeks prvega prostega mesta

• Potrebujemo indeks začetka

  • indeks prvega (najstarejšega) vstavljenega

•  private T[] vr; 
•  private int kon; // indeks prostora za nasl. Element 
•  private int zac; // indeks najstarejšega 
• pripravi, vstavi, vstavi, vstavi, odstrani

• Dovolj hitro (vse )
• ni težav z zapisom

• problemi:

  • omejena velikost

  • Zaradi drsenja zmanjka prostora, čeprav je levo še!

    • P, V, V, V, O, V, O, O, V, V, O, V, V, V, V

Krožna vrsta

• Tabela

• verižni seznam

• Tabela s fiksnim začetkom

  • Počasna operacija odstrani, ostalo hitro
  • Omejena velikost

• Tabela z "gibljivim" začetkom

  • Operacije hitre
  • Problem "drsenja vrste"
  • Omejena velikost

• Krožna tabela

  • Odpravimo problem drsenja
  • Operacije hitre, po modulu dolžine tabele
  • Kako ločiti prazno/polno vrsto?
  • Omejena velikost

• verižni seznam

  • Hitro (če naredimo prav)
  • "neomejen" prostor