Kako predstavimo vrsto s tabelo
VSTAVLJANJE ELEMENTOV
Podatkovno strukturo vrsto lahko predstavimo s tabelo. Na primeru enojne vrste si bomo ogledali splošno predstavitev, ki se kasneje navezuje tudi na predstavitev dvojne vrste. Pri enojni vrsti torej na enem koncu elemente v tabelo vstavljamo, na drugem jih brišemo ven. Postopek in evidenco vstavljanja in brisanja vodimo z indeksi v tabeli. V tabelo začnemo vstavljati elemente pri indeksu 0 in nato po vrsti nadaljujemo: naslednji element postavimo na indeks 1, itd. Konec vrste oz. zadnje zasedeno mesto v tabeli si zapomnimo s pomožnim indeksom, katerega po vsakem novem vstavljanju povečamo za ena. Če želimo pogledati element na začetku vrste, preverimo, kateri element v tabeli se nahaja na indeksu 0. Podobno preverimo tudi, če je vrsta prazna - če naš pomožni indeks kaže na indeks 0.
BRISANJE ELEMENTOV
Problem se pojavi pri jemanju oz. brisanju elementov iz tabele. Elemente po definiciji vrste brišemo ven tako, kot so vanjo prihajali, se pravi prvi element, ki je bil vstavljen v tabelo, bo iz nje tudi prvi vzet. To bi bil potemtakem element z indeksom 0. V tabeli bi se v tem primeru pojavilo prosto mesto. Lahko bi seveda nadaljevali z brisanjem elementov pri indeksu 1, itd, vendar bi na tak način na začetku ostajala prazna mesta, ki pa jih ne bi mogli zapolniti, ker vstavljamo elemente na drugem koncu tabele, ki se seveda enkrat konča.
Ena od rešitev za to bi bila po brisanju elementa prestavljanje vseh preostalih elementov za enega v levo. Se pravi, da bi morali vsem preostalim elementom zmanjšati indeks za 1, kar pa bi bilo časovno preveč zahtevno. Če je n velikost tabele, bi imeli v najslabšem primeru preostalih elementov n-1 in torej n-1 prestavljanj, se pravi, da bi bila časovna odvisnost operacije odstrani v tem primeru O(n). Težimo pa seveda k temu, da bi bila časovna odvisnost operacije konstantna in neodvisna od števila elementov v tabeli.
KROŽNA PREDSTAVITEV VRSTE
Druga rešitev je v načinu vstavljanja elementov v tabelo. Elemente vstavljamo po modulu n, pri čemer je n velikost tabele. S tem spremenimo predstavitev vrste v krožno povezano vrsto. Z dvema pomožnima indeksoma z in k pa si zapomnimo začetek in konec vrste.
Pozorni pa moramo biti na mejne primere - kdaj je vrsta prazna in kdaj je vrsta polna. Če računamo po modulu n, je naslednje prosto mesto za vstavljanje v tabelo (k+1) mod n. Če to prosto mesto pokaže na začetek vrste z, ne vemo, ali je v tem primeru vrsta polna ali prazna. Zato velja dogovor, da v vrsti hranimo največ n-1 elementov, pri čemer je n velikost tabele, z pa je indeks zadnjega praznega mesta pred začetkom vrste.
Takrat velja naslednje:
vrsta je polna, če: (k+1) mod n = z
vrsta je prazna, če: k = z
Slika krožne vrste (Kozak, str. 38)