Uvod - Enojna in dvojna vrsta
Za razumevanje strukture dvojna vrsta moramo najprej povedati nekaj besed
o enojni vrsti. Enojna vrsta je podatkovna struktura, ki se obnaša kot urejeni seznam.
V ta seznam vstavljamo podatke na enem koncu, jemljemo pa jih ven na drugem koncu
- na začetku vrste. Podatke odstranimo iz vrste v istem vrstnem redu kot so v vrsto
tudi prišli, vendar lahko iz vrste odstranimo samo tisti podatek, ki je v njej najdlje časa.
Tak način se imenuje FIFO princip (first-in first-out). Primer za to je npr.
vrsta ljudi pred blagajno - tisti, ki je prišel v vrsto prvi, bo tudi prvi vplačal
pri blagajni.
Pri dvojni vrsti pa lahko elemente vstavljamo in brišemo na obeh koncih vrste.
Na tak način so hitreje dostopni kot v enojni vrsti ali pa v skladu.
PRIMER ENOJNE VRSTE
Če v enojno vrsto vstavljam z leve elemente a, b, c, d, ki jih dobivam sproti:
... jih lahko odstranim ven iz vrste na desni strani le v enakem vrstnem redu: a, b, c, d.
PRIMER DVOJNE VRSTE
Elemente dobivam sproti. Pri vstavljanju v dvojno vrsto jih lahko vstavim vanjo z
obeh strani.
Nekaj možnih različic vstavljanja elementov v dvojno vrsto:
- vstavim najprej a z leve, nato po vrsti b, c in d z desne
- vstavim najprej a in nato b z leve, nato pa c in d z desne
- vstavim a, nato b in nato c z leve, d pa z desne
- vstavim najprej a z leve, b z desne, c z leve in d z desne
...in tako naprej.
Podobno jih lahko jemljem ven z obeh koncev vrste.