Podatkovna struktura: VRSTA

Podatkovna struktura: VRSTA

Avtor: Marko Rožič

Kako so živali dobile svoj rep?

Dolgo dolgo je že od takrat, ko so živali živele brez repov. Rep je zrasel na levu, kralju vseh kraljev. Živali pa so se brez repov kaj slabo počutile. Pozimi je še šlo, a poleti so se komaj otresale obadov in mušic. S čim naj se jih ubranijo?
Ko je kralj lev zvedel, kako trpijo njegove živali, je ukazal, naj pridejo vse živali k njemu in dobile bodo rep. Kraljevi sli so se razšli po vseh deželah in klicali živali pred kralja.
Najprej so srečali volka in ga poslali k levu, nato so povabili še osla in jazbeca, lisico in kuno in divjo svinjo in srnjaka, vse živali so vabili h kralju.
Prva je pritekla lisička brez repa in je zaklicala: »Gospod lev, kralj živali, jaz sem prva pritekla, ko si nas poklical. Zato mi dovoli, da si izberem rep, ki mi bo najbolj všeč.«
Zakaj pa ne? Kralju je bilo vseeno, kakšen rep si bo izbrala. »Kar izberi, lisica, kar izberi,« je kimal, »tistega vzemi, ki ti je najbolj všeč.«
Prebrisana lisica je pobrskala v kupu repov in nato izbrala največjega in najbolj košatega. Potem jo je brž pobrisala, da si kralj ne bi premislil. Še zahvaliti se je pozabila.
Koj za lisico je priskakljala veverica. Poiskala si je kar čeden rep, le malo manjši je bil kot lisičin. Potem je prišla še kuna in je dobro izbrala.
Za kuno je jazbec je vzel debel, širok rep.
Za jazbecem je prišel konj. Poiskal je rep s trdimi dlakami, in ko si ga je pritrdil, je udaril z njim najprej na levo, nato na desno stran. »Dobro tolče! Zdaj naj le pridejo muhe in obadi, vse bom potolkel,« je rekel in zdirjal na trato.
Nazadnje je prišel še zajček. »Kod si le hodil,« ga je vprašal kralj. »Poglej, samo tale repek je še ostal.« »Saj bo ravno pravšen zame,« je rekel zajček. »Lahko ga bom nosil in lahko bom pobegnil volku in psu.« In zajček si je zataknil repek, kamor sodi, parkrat poskočil, se zavrtel sam okoli sebe in zdirjal domov.

prirejeno po ruski pravljici
"Kdor prej pride, prej melje." - slovenski pregovor

Primeri



Zaporedni viri slik:

  1. Tobogan, 27. 12. 2012
  2. Tekoče stopnice, 27. 12. 2012


Vse slike so bile najdene s CC Search.

Definicija

Do sedaj so bili predstavljeni primeri dogodkov, ki so se ali se odvijajo po vrsten redu. Živali v pravljici so izbirale rep zase po vrstnem redu, kot so prihajale pred leva. Pri vožnji s toboganom oseba, ki prej pride na vrh tobogana, prej začne vožnjo in jo tudi prej zaključi. Med vožnjo po toboganu zaradi varnosti kopalcev ni prehitevanja. Enako velja za uporabo tekočih stopnic. Kdor prej pride na začetek tekočih stopnic, prej začne z vožnjo in prej vožnjo zakljulči.

Vsi ti primeri nakazujejo dogodke, pri katerih je vrsni red pomemben. Žival, ki je prišla zadnja pred leva, je tudi zadnja izbirala rep, pri vožnji s toboganom je potrebno počakati, da se po toboganu zapeljejo vsi tvoji predhodniki po vrstnem redu od tistega, ki je prvi prišel na začetek tobogana do tistega, ki stoji tik pred tabo. Ko se zvrstijo zaporedoma vsi pri vožnji, šele takrat se lahko po toboganu spustiš ti.

Za računalništvo velja vrstni red pri izvajanju programov, ki čakajo na izvajanje ali na izpis. Vrsta je najnaravnejša struktura za prenos podatkov iz pomožnega v hitri pomnilnik.

Podatkovna struktura vrsta deluje po principu FIFO (First In First Out), kar pomeni, da gre element, ki prvi v vrsto vstopi, tudi prvi ven iz nje. Vrsta je urejeni seznam, v katerega vstavljamo elemente na enem koncu (repu vrste) in elemente jemljemo z drugega konca (začetka vrste). Elementi zapuščajo vrsto v istem vrstnem redu, kot so prišli.

Osnovne operacije

Osnovne operacije nad vrsto so:

  • pripravi ... pripravi prazno vrsto,
  • vstavi ... vstavi element v vrsto,
  • začetek ... vrne prvi element v vrsti,
  • odstrani ... odstrani element iz vrste,
  • prazna ... Ali je vrsta prazna?.

Predstavitev vrste v nekem programskem jeziku ali kjer koli drugje mora biti takšna, da zadošča formalni predstavitvi vrste. Uporabljen mora biti takšen način predstavitve, da lahko na tej predstavitvi izvajamo zgoraj naštete osnovne operacije. Vstavljamo lahko samo na koncu vrste in odstranimo lahko samo trenutni začetek vrste. Predstavitev mora biti neomejena s prostorom, saj vrsta ne sme biti nikoli polna. Vsak element (razen začetka in konca) ima le enega predhodnika in enega naslednika. Začetek ima lahko le svojega predhodnika, konec le svojega naslednika.

Formalni opis podatkovne strukture vrsta

structure vrsta (podatek, Boolean);
{Struktura vrsta nad poljubno zalogo vrednosti podatek}
begin
declare
{Pripravi prazno vrsto.}
pripravi ::= 0 --> vrsta;
{Vstavi podatek v vrsto in vrne novo vrsto.}
vstavi ::= (vrsta, podatek) --> vrsta;
{Vrne podatek, ki je na začetku vrste.}
začetek ::= vrsta --> podatek;
{Izbriše prvi element vrste in vrne novo vrsto.}
odstrani ::= vrsta --> vrsta;
{Ali je vrsta prazna?}
prazna ::= vrsta --> Boolean;
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);
začetek(pripravi) ::= napaka;
začetek(vstavi(v,p)) ::=
if prazna(v) then p else začetek(v);
end

Formalna predstavitev vrste je razdeljena na declare (deklarativni) in na where del. V prvem delu navedemo (deklariramo) kaj želimo s to podatkovno strukturo delati (metode), v drugem pa navedemo pravila po katerih se morajo metode iz prvega dela ravnati.

Razlaga dela WHERE

  1. prazna(pripravi) ::= true;
    Če izvajamo operacijo prazna nad vrsto v, ki je nastala z operacijo pripravi, vemo, da v tej vrsti še ni nobenega podatka in je zato zagotovo prazna. Takrat je rezultat operacije prazna logična vrednost true.

  2. prazna(vstavi(v,p)) ::= false;
    Če izvajamo operacijo pripravi nad poljubno vrsto, v katero smo prej vstavili podatek, potem zagotovo vemo, da je v tej vrsti v vsaj en podatek. Takrat je rezultat operacije prazna logična vrednost false.

  3. odstrani(pripravi) ::= napaka;
    Če operacijo odstrani izvajamo nad vrsto v, ki je nastala z operacijo pripravi, potem zagotovo vemo, da je ta vrsta prazna in da v njej ni nobenega podatka. Če želimo iz te vrste odstraniti podatek, prevajalnik javi napako.

  4. odstrani(vstavi(v,p)) ::=
    if prazna(v) then pripravi else vstavi(odstrani(v),p);
    Če je bila vrsta v pred vstavljanjem podatka p prazna, potem odstranimo edini podatek v vrsti in operacija vrne vrsto, kot bi nastala z operacijo pripravi. Če pa vrsta pred vstavljanjem podatka ni bila prazna, si zadnji podatek p katerega smo na zadnja vstavili zapomnimo. Nato na enak način pogledamo del vrste v (sedaj brez podatka p) in si zapomnimo predzadnji podatek, ki smo ga v vrsto vstavili. Nadaljujemo s pregledom - si zapomnimo podatek, ki smo ga kot predpredzadnjega vstavili v vrsto in tako naprej vse do dela prvotne tabele, v katerem je samo še en podatek. Ta podatek odstranimo. Potem pripravimo prazno vrsto in podatke, ki smo jih prej posamično zapomnili, v nasprotnem vrsten redu vstavljamo v vrsto. Dobimo vrsto s podatki brez podatka, ki smo ga prvega vstavili v prvotno vrsto (začetek vrste) - dobimo vrsto brez začetka, kar je točno to, kar na operacija odstrani naredi.

  5. začetek(pripravi) ::= napaka;
    Če je bila vrta v ustvarjena z operacijo pripravi in nato na tej vrsti izvedemo operacijo začetek, prevajalnik vrne napako. Ker v vrsti v ni nobenega podatka, operacija začetek tudi ne more vrniti začetka vrste v.

  6. začetek(vstavi(v,p)) ::=
    if prazna(v) then p else začetek(v);
    Če je bila vrsta v pred vstavljanjem podatka p prazna, potem operacija začetek vrne edini element v v vrsti - element p. Če pa vrsta pred vstavljanjem podatka p ni bila prazna, potem operacija vrne del tabele brez na zadnje vstavljenega podatka p. Operacija nadaljujemo z rekurzivnim vračanjem tabele: vrne del tabele brez predzadnje vstavljenega podatka in nato del tabele brez predpredzadnje vstavljenega podatka in tako naprej vse do dela tabele, v katerem je samo še en podatek. Tabela je bila pred vstavljanjem tega podatka prazna, zato operacija vrne ta podatek. To pa je ravno podatek, ki je bil prvi vstavljen v vrsto in je bil najdalj časa v vrsti. Ta podatek je zečetek vrste in je podatek, za katerega si želimo, da je rezultat te operacije.

Primer uporabe podatkovne sktrukture 1

Čakalna vrsta

Pri zdravniku so naročeni pacienti v čakalni vrsti. V čakalni vrsti imajo pacienti vsak svojo zaporedno številko. Ker velja načelo, da je zadnji naročeni pacient tudi zadnji na vrsti pri zdravniku, je podatkovna struktura vrsta primerna za hrambo naročenih pacientov.
Naj spodnja vrsta v predstavlja čakajoče paciente v vrsti. Pacienta, ki je bil prvi naročen pri zdravniku, predstavlja najmanjše število in tako naprej.

Za pacienta z zaporedno številko in je prišlo nekaj nujnega vmes in morata zaradi teh razlogov žal izstopiti iz čakalne vrste. Z operacijami nad podatkovno strukturo vrsta izpeljimo algoritem, ki iz vrste odstrani kandidata pod omenjenima zaporednima številkama. Ostali kandidati ostanejo pri tem nepreštevilčeni.


izloci(v):
vstavi(v, "A") #V vrsto vstavimo dodaten znak, da bomo vedeli,
kdaj smo pregledali celotno vrsto.

while (začetek(v) != "A"):
if (začetek(v) == 3 ali začetek(v) == 7):
odstrani(v) # Če je začetek vrste enak številu 3 ali 7, ga odstranimo.
else:
vstavi(v, začetek(v)) # Sicer začetek vrste vstavimo ponovno v vrsto in
odstranimo začetek vrste. S takšnim načinom prestavljanja
ne spremenimo ostalega vrstnega reda števil v vrsti.

odstrani(v)
odstrani(v) # Ko pridemo do vrinjenega znaka "A", še tega odstranimo.
return(v) #Metoda vrne popravljeno vrsto.

Na koncu dobimo vrsto, brez števil, kateri predstavljata osebi, ki sta iz čakalne vrste iztopili:


Naloga:
Sestavite zaporedje stavkov, s katerim bi najprej iz zgornje vrste odstranili število 1 in nato dodali število 3?

odstrani število 1
vstavi število 3
odstrani(v)
vstavi(v,3)
vstavi(3)
začetek(odstrani(v))

Preveri

Pravilno

Pravilno ste rešili nalogo.

Naprej

Narobe

Vsaj ena povezava je napačna. Poskusite ponovno.

Ponovno

Primer uporabe podatkovne strukture 2

Šolska malica

Na šoli je preveč dijakov, da bi lahko vsi malicali v enem terminu. Zato je potrebno dijake razdeliti v dev skupini. Ravnatelj je odločil, da bo malica za dijake prvih in drugih letnikov skupaj ter za dijake tretjih in četrtih letnikov skupaj.
Da bi vedeli, kolikšno število malic je potrebno pripraviti za posamezen termin, je potrebno dijake prešteti. Dijaki so v vrsti v razdeljeni po letnikih. Dijaka prvega letnika označuje število 1, drugega število 2, tretjega število 3 in četrtega število 4. Sestavimo algoritem, ki prejme vrsto v:

in kot rezultat vrne število dijakov, ki bodo malicali v prvi skupini in število dijakov, ki bodo malicali v drugi skupini. Vrte ni potrebno ohraniti.


prestej(v):
pd=0 #Indeksa za štetje dijakov za malico v prvi in drugi skupini.
tč=0
while (prazna(v) == False): #Pregledamo celotno vrsto.
if (začetek(v) == 1 ali začetek(v) == 2):
pd=pd+1 #Če je začetek vrste enak številu 1 ali 2, potem povečamo
števec za dijake prvih in drugih letnikov.

else:
tč=tč+1 #Sicer povečamo števec za dijake tretjih in četrtih letnikov.
odstrani(v) #V vsakem primeru odstranimo podatek iz vrste.
return (pd, tč) #Metoda vrne skupno število dijakov prvega in drugega letnika ter
skupno število dijakov tretjega in četrtega letnika.


Izpis je na primer oblike:
V prvi skupini bo malicalo št. dijakov: 13
V drugi skupini bo malicalo št. dijakov: 11

Predstavitev vrste z verižnim seznamom

Vrsto si lahko predstavljamo kot verigo vozlov. Vozle sestavljata dva dela. V enem delu je podatek (element tabele), v drugem delu pa je shranjeno, kje se naslednik vozla nahaja (naslov, kazalec na naslednji vozel). Glede na osnovne operacije nad vrsto je pomembno, da imamo pri vrsti kazalec na prvi in zadnji vozel. Tako lahko neodvisno od števila podatkov v vrsti (števila vozlov) vedno z enako časovno zahtevnostjo dodajamo elemente v vrsto, izpišemo podatek na začetku vrste ali odstranimo element iz vrste (odstranimo začetek vrste). Verižni seznam je lahko enojno povezani linearni seznam (vozel vsebuje kazalec le na naslednji vozel) ali dvojno povezani linearni seznam (vozel vsebuje povezavo tako na naslednji kot tudi na predhodnji vozel v zaporedju).

(http://www2.nauk.si/files/348/Vrsta1_0.jpg)
Predstavitev vrste z verižnim seznamom.

Ker vsak vozel vsebuje podatek, kje se nahaja njegov naslednjik, lahko na primer iz prvega vozla seznama pridemo do vsakega vozla v verižnem seznamu in s tem do vsakega podatka v vrsti. Zato obstaja več možnosti:

  1. Imamo kazalec le na vozel, v katerem je podatek, ki je v vrsti najdalj časa, podatki pa so urejeni tako, da vsak kaže na svojega predhodnika (na podatek, ki je prišel v vrsto za njim). Pri tem je problematična je operacija vstavi, ker je potrebno od prvega podatka priti do zadnjega preko vseh ostalih, da lahko vstavimo nov podatek v vrsto. Časovna odvisnost je za operacijo vstavi odvisna od števila podatkov v vrsti.
  2. Imamo kazalec le na vozel, v katerem je podatek, ki je v vrsti najmanj časa (je bil v vsrto zadnji vstavljen), podatki pa so urejeni tako, da vsak kaže na podatek, ki je bil v vrsto vstavljen pred njim. Pri tem sta problematični operaciji začetek in odstrani, saj moramo, če ju želimo izvesti, od podatka na katerega kaže kazalec, preko vseh ostalih podatkov priti po seznamu do podatka, ki je v vrsti najdalj časa. ta podatek vrne operacija začetek ali pa ga operacija odstrani odstrani iz vrste. Časovni odvisnosti za obe operaciji sta odvisni od števila podatkov v vrsti.
  3. Imamo kazalec na vozel na začetku in na koncu vrste, podatki pa so urejeni tako, da vsak kaže na podatek, ki je bil kasneje vstavljen v vrsto (kazalci med vozli kažejo od začetka proti koncu vrste - slika zgoraj). Iz vrste odstranjujemo elemente tako, da se s kazalcem na prvi vozel pomikamo za en vozel naprej (podatek na začetku vrste je podatek v vozlu, na katerega kače kazalec začetka vrste). Za dodajanje elementov na konec vrste pa za zadnjim vozlom ustvarimo nov vozel, v katerega shranimo podatek, ki je nazadnje vstavljen v vrsto. Kazalec zadnjega vozla v vrsti nastavimo na nov vozel, v katerem je v vrsto zadnji vstavljeni podatek. Tudi kazalec, ki je pred dodajanjem novega podatka v vrsto kazal na konec vrte, pomaknemo za en vozel naprej.

Predstavitev vrste s tabelo

Podatkovno strukturo vrsta lahko predstavimo tudi v tabeli. Biti prej vstavljen v vrsto naj pomeni biti levi sosed v tabeli. Pri tej predstavitvi vrste nastane problem drsenja vrste. Ko iz vrste vzamemo element povečamo začetek za ena, ko dodamo nov element, povečamo konec za ena. Po večkratnem vstavljanju in odstranjevanju podatkov imamo skoraj prazno vrsto, v katero ne moremo več shraniti podatkov, ker smo s kazalcem prišli do konca tabele. Zato tabela ni najustreznejši način predstavitve vrste, saj vrsta ne more biti nikoli polna.

Predstavitev vrste s tabelo lahko izvedemo na več načinov:

  1. Predstavitev napravimo tako, da je na indeksu 0 tabele zadnji element v vrsti (to je podatek, ki je najmanj časa v vrsti, podatek, ki je bil v vrsto zadnji vstavljen). Problem pri tej predstavitvi je pri vstavljanju podatkov v vrsto. Če želimo vstaviti nov podatek, je potrebno vse podatke v tabeli prestaviti za eno mesto naprej. Poveča se časovno zahtevnost operacije, želimo pa si, da bi bile operacije časovno neodvisne od števila podatkov v vrsti in načina predstavitve vrste.
  2. Predstavitev napravimo tako, da je na indeksu 0 tabele prvi element v vrsti (to je podatek, ki je bil v vrto najprej vstavljen, podatek, ki je najdalj časa v vrsti). Pri tej predstavitvi pride do problema drsenja vrste. Ko odstranimo podatek, je mesto z indeksom 0 prosto. Če želimo to mesto zapolniti, je potrebno vsem podatkom v tabeli zmanjšati indeks za 1. Sicer je pri takšni predstavitvi zelo enostavno izpisati podatek na začetku vrste – to je kar podatek z indeksom 0 v tabeli.
  3. Predstavitev vrste s tabelo lahko naprevimo tako, da vodimo indeks prvega in zadnjega elementa vrste. Ko pripravimo tabelo za predstavitev vrste, ima ta končno mnogo prostora. Če vodimo indeks za prvi podatek v tabeli (podatek, ki je v vrsti najdalj časa), potem zelo enostavno poiščemo podatek, ki je na začetku vrte ali pa odstranimo podatek iz vrste. Če vodimo indeks za zadnji podatek v vrsti, potem lahko zelo enostavno dodajamo podatke v tabelo. S tem se v splošnem pomikamo po indeksih tabele proti njenemu koncu ali začetku. Torej slej ko prej lahko pridemo do trenutka, ko bodisi ni mogoče več vstavljati podatkov v vrsto ali pa odstranjevati podatkov iz tabele. Zato bi bilo potrebno prestavljati podatke v vrsti v eno ali drugo smer za en indeks bodisi pri vstavljanju podatkov v tabelo ali pa pri odstranjevanju.

Predstavitev vrste s krožno tabelo

Ker se tabela, s katero predstavljamo vrsto, v splošnem na enem koncu polni, na drugem pa prazni, je potrebno predstavitev zasnovati tako, da sproščeni prostor na začetku vrste spet lahko uporabimo za vstavljanje. Zato vodimo tabelo kot krožno po modulu velikosti tabele n.
Naj bo vrsta (i=0, 1, ..., n-1) tabela, v kateri vodimo vrsto. Vse indekse računamo po modulu n, z in k pa označujeta začetek in konec vrste. Ločimo dva mejna primera: vrsta je polna in vrsta je prazna. Vrsta je polna, ko velja

V vrsti je en sam element, ko je

Če ga brišemo, postaneta z in k takšnih vrednosti, kot pri polni vrsti. Moramo vedeti, za katerega od primerov gre (ali je vrsta prazna ali polna). Na preprost način to dosežemo tako, da se odrečemo enemu mestu v tabeli. Naj bo zato z indeks zadnjega praznega mesta pred začetkom vrste. Vzemimo primer na spodnji sliki:

(http://www2.nauk.si/files/348/Vrsta4.jpg)
Krožno predstavljena vrsta.


Vrsto na sliki tvorijo elementi:


Vrsta je prazna, če je in polna pri

Kviz

1. Naloga:
V katerih primerih gre za podatkovno strukturo VRSTA?

Preveri

Pravilno

Odgovor je popolnoma pravilen.

Next

Napačno ali delno napačno

Odgovor je delno ali popolnoma napačen.

Ponovno reševanje

Kviz 2

2. Naloga:
Recimo, da imamo vrsto: zacetek: 1, 2, 3, 2 :konec
Kako izgleda vrsta po vsakem izvedenem koraku?

odstrani(vrsta)
prazna(vrsta)
odstrani(vrsta)
vstavi(vrsta, 8)
odstrani(vrsta)
zacetek(vrsta)
odstrani(vrsta)
prazna(vrsta)
odstrani(vrsta)
prazna(vrsta)
zacetek: 1, 2, 3 :konec
False
zacetek: 1, 2 :konec
zacetek: 8, 1, 2 :konec
zacetek: 8, 1, :konec
8
zacetek: 8 :konec
zacetek: :konec
True
zacetek: 2, 3, 2 :konec
zacetek: 1, 2, 8 :konec
1

Preveri

Pravilno

Vse je pravilno.

Naprej

Narobe

Vsi odgovori niso pravilni. Poskusi z reševanjem ponovno.

Ponovno

Kviz 3

3. Naloga:

Naj bo in , pri čemer je indeks, ki kaže na mesto pred prvim elementom v tabeli, indeks, ki kaže na zadnji element v tabeli in število mest v tabeli.

a.) Ali je tabela polna?

b.) Ali je tabela prazna?

Preveri

Prav

Odlično.

Naprej

Delno pravilno

Na drugo vprašanje nisi prav odgovoril/a. Tabela je prazna, ko velja: .

Naprej

Delno pravilno

Na prvo vprašanje nisi prav odgovoril/a. Tabela je polna, ko velja: .

Naprej

Wrong

Ugibaj ponovno.

Ponovno reševanje

Rezultati kviza

Uporabljena literatura

0%
0%