Formalna predstavitev (enojne) vrste
Operacije, ki se izvajajo nad vrsto, morajo ustrezati pogojem, ki opisujejo obnašanje vrste in podatkov v njej. Operacije nam morajo dati torej možnost vstaviti element na konec vrste, odstraniti element z začetka, preveriti, kateri element se nahaja na začetku vrste in preveriti, če je vrsta prazna.
Dve osnovni operaciji, s katerima opišemo še ostale operacije in za kateri ne obstaja noben aksiom, saj opisujeta tudi sami sebe, sta: pripravi in vstavi. Ostale operacije pa so še: prazna, zacetek in odstrani.
(Kozak, str. 34)
structure VRSTAPODROBNEJŠA RAZLAGA DELA where - opis operacij prazna, odstrani, zacetek:
- PRAZNA
prazna(pripravi) ::= true;
prazna(vstavi(v,p)) ::= false;Operacijo prazna, ki vrne rezultat true ali false opišemo na dveh primerih: če jo izvajamo nad vrsto v, ki je nastala z operacijo pripravi, potem vemo, da je ta vrsta zagotovo prazna in da v njej ni nobenega podatka. Takrat je rezultat operacije prazna - true. Če pa jo izvajamo nad poljubno vrsto, v katero smo pred tem vstavili podatek, potem zagotovo vemo, da je v tej skupni vrsti v vsaj en podatek. Takrat je rezultat operacije prazna - false.
- ODSTRANI
odstrani(pripravi) ::= NAPAKA;
odstrani(vstavi(v,p)) ::=
if (prazna(v)) then pripravi;else vstavi(odstrani(v),p);Zopet opazujemo dva primera: če operacijo odstrani izvajamo nad vrsto, ki je nastala z operacijo pripravi, potem zagotovo vemo, da je ta vrsta prazna in da v njej ni nobenega podatka. Iz vrste torej ne moremo odstraniti nobenega podatka in prevajalnik javi napako. V nasprotnem primeru, kjer operacijo odstrani izvajamo nad vrsto, ki je nastala tako, da smo v poljubno vrsto v vstavili podatek p, pa zagotovo vemo, da je v tej skupni vrsti vsaj en podatek.
Takrat ločimo dva primera: če je bila vrsta v pred vstavljanjem podatka p prazna, potem operacija odstrani odstrani edini podatek (podatek p) iz nje in vrne vrsto, ki je enaka vrsti, kot bi sicer nastala z operacijo pripravi. Če pa vrsta v pred vstavljanjem podatka ni bila prazna, potem operacija poteka na tak način (glej sliko):
pogledamo, kako je nastala skupna vrsta, si zapomnimo podatek p (zadnji podatek, ki smo ga vstavili vanjo), nato na enak način pogledamo vrsto v, ki je del skupne vrste, vendar brez podatka p - kateri je bil drugi zadnji podatek, ki je bil vstavljen vanjo, in tako naprej, dokler ne pridemo do vrste, v kateri je le še en podatek. Prej smo že rekli, da v tem primeru edini podatek odstranimo, pripravimo prazno vrsto in podatke, ki smo jih prej posamezno izluščili enega po enega, v obratnem vrstnem redu postopoma vstavljamo v vrsto. Na koncu dobimo enako vrsto kot prej, vendar brez začetka - brez prvega elementa, kar pa je ravno to, kar naj bi operacija odstrani naredila. - ZACETEK
zacetek(pripravi) ::= NAPAKA;
zacetek(vstavi(v,p)) ::=
if (prazna(v)) then p;else zacetek(v);Če operacijo zacetek izvajamo nad vrsto, ki je nastala z operacijo pripravi, potem zagotovo vemo, da je ta vrsta prazna in da v njej ni nobenega podatka. Začetek vrste torej ne obstaja in prevajalnik javi napako. V nasprotnem primeru, kjer operacijo zacetek izvajamo nad vrsto, ki je nastala tako, da smo v poljubno vrsto v vstavili podatek p, pa zagotovo vemo, da je v tej skupni vrsti vsaj en podatek.
Takrat ločimo dva primera: če je bila vrsta v pred vstavljanjem podatka p prazna, potem nam operacija zacetek vrne podatek p, ki smo ga vstavili vanjo. Če pa vrsta ni bila prazna, potem operacija zacetek vrne začetek vrste na rekurziven način klicanja sama sebe - se pravi, vrne vrsto brez zadnjega podatka, ki je bil vanjo vstavljen, nato na tej vrsti zopet vrne novo vrsto brez naslednjega zadnjega podatka, ki je bil vanjo vstavljen, in tako naprej, dokler ne pride do vrste z le še enim podatkom. Pred vstavljanjem tega podatka vanjo je bila vrsta prazna in v tem primeru vrnemo podatek, ki je bil vanjo vstavljen. To pa je ravno podatek, ki ga iščemo.