Dvojna vrsta

Pri dvojni vrsti, ki jo predstavimo s tabelo, prav tako uporabimo način krožne predstavitve vrste, kjer elemente vstavljamo in brišemo po modulu n, kjer je n velikost tabele. V tabeli zopet lahko hranimo do največ n-1 elementov, zato da lahko ločimo med polno in prazno vrsto.

OPIS OPERACIJ pri predstavitvi dvojne vrste s tabelo:

prazna:
Kot že rečeno - vrsta je prazna, če k kaže na isto mesto kot z, se pravi, če je k enak z-ju.
Opomba: In nasprotno - vrsta je polna, če je k+1, računan po modulu n, enak z-ju.

zacetek:
Ker je z zadnje prosto mesto pred začetkom vrste, vrnemo element, ki se v tabeli t nahaja na indeksu z+1, ki ga računamo po modulu n. Pazimo na mejni primer, če je vrsta prazna. Takrat prevajalnik javi napako, saj ne more vrniti nobenega elementa.

konec:
Ker k kaže na konec vrste, vrnemo element, ki se v tabeli t nahaja na mestu z indeksom k. Podobno kot prej – pozorni smo na mejni primer, če je vrsta prazna.

vstaviZacetek:
Začetek vrste je v tabeli t mesto z indeksom (z+1) mod n. Da se izognemo prestavljanju vseh elementov v vrsti za eno mesto naprej, da bi pridobili prostor za novega na začetku, rajši vstavimo nov element kar na mesto z indeksom z, z pa zmanjšamo za ena, zato da kaže na eno mesto pred njim. Ker pa je vrsta krožno predstavljena, moramo biti pozorni, da vrsta ni že polna, saj potem z-ja ne moremo prestaviti za eno mesto nazaj. Pazimo torej, da z ni enak k+1, ki ga seveda računamo po modulu n. Tudi pri prestavljanju z-ja za eno mesto nazaj moramo biti pozorni, če je z = 0. Takrat bi lahko padli v negativno vrednost, zato ga v tem primeru prestavimo tako, da kaže na zadnje mesto v tabeli.

odstraniZacetek:
Ko odstranjujemo začetek vrste, pravzaprav samo povečamo z za ena, da pokaže na nov začetek vrste - na eno mesto naprej v tabeli, seveda po modulu n, da ne pademo ven iz tabele. Pozorni smo na mejni primer, če je vrsta prazna, ker takrat ne moremo pobrisati nobenega elementa.

vstaviKonec:
Ko vstavljamo element na konec vrste, ga v tabeli postavimo na mesto z indeksom k+1 in po vstavljanju elementa povečamo k za ena, zato da res označuje novi konec vrste. Pozorni smo na mejni primer, če je vrsta že polna. V tem primeru k+1, računan po modulu n, pred vstavljanjem elementa v vrsto ne sme biti enak z-ju. Takrat novega elementa ne moremo vstaviti.

odstraniKonec:
Ko odstranjujemo zadnji element v vrsti, samo zmanjšamo k za ena, zato da označuje kot konec vrste eno mesto prej. Mesto, kamor je prej kazal k, je tako dostopno za vstavljanje novega elementa. Pri prestavljanju k-ja za eno mesto nazaj moramo biti pozorni, če je k = 0. Takrat bi lahko padli v negativno vrednost, zato ga prestavimo tako, da kaže na zadnje mesto v tabeli. Pozorni smo tudi na mejni primer, če je vrsta prazna, ker takrat ne moremo odstraniti nobenega elementa.

velikost:
Operacijo, ki vrne število elementov v vrsti, lahko dodamo po želji. Ker je vrsta krožno predstavljena, ne moremo samo preprosto odšteti z od k-ja, da bi izračunali št. elementov vrste. Ločimo namreč med dvema primeroma: k < z ali pa k > z (glej sliko spodaj). Če je k > z, potem bi velikost vrste resda dobili s preprosto enačbo k - z. Če pa je k manjši od z, to pomeni, da se vrsta začne na nekem mestu naprej od indeksa 0 oz. nekje v tabeli naprej od začetka, konec vrste pa se nahaja nekje med indeksom 0 in nekim indeksom, ki vsaj za eno manjši od z-ja (glej sliko). Če bi v tem primeru računali velikost vrste k – z, vsekakor ne bi dobili pravega rezultata.
Računanja se lotimo takole: če je n število mest v tabeli, od njega najprej odštejemo z, in s tem odštejemo »prosta« mesta na začetku tabele. Prosta v narekovajih zato, ker tukaj še nismo upoštevali mest, kjer vrsta pravzaprav sega že čez začetek tabele. Zato številu n - z prištejemo še k, da upoštevamo še mesta, ki segajo od indeksa 0 do indeksa k. Velikost vrste torej izračunamo takole: n – z + k. Da pa si ne kompliciramo življenja z različnimi primeri, lahko to enačbo uporabimo tudi v primeru, če je k > z, vendar takrat računamo rezultat enačbe po modulu n. V nasprotnem primeru bi dobili seveda število elementov v vrsti sešteto s številom mest v tabeli. Za primer, ko je k manjši od z, pa računanje po modulu n ničesar ne spremeni, torej lahko ta enačba ostane tudi v tem primeru.
Tako lahko uporabimo isto enačbo v obeh primerih. Število elementov v vrsti je torej enako (n - z + k) mod n. Mejnega primera, če je vrsta prazna, nam ni treba posebej upoštevati, ker nam v tem primeru vrne enačba število 0.

Slika dveh variant vrst glede na vrednosti k in z

toString:
Pri zapisu operacije toString moramo biti pozorni na nastavitev začetka izpisovanja elementov vrste. Nek pomožen števec nastavimo na z (z-ja namreč ne smemo spreminjati), z zanko pregledamo vse elemente v vrsti in povečujemo števec za ena, dokler ni enak k-ju, vsak pregledani element pa dodamo k izpisu. Ko nastavljamo števec za pregledovanje, ga moramo za izpis prvega elementa najprej povečati za ena (seveda po modulu n) in šele nato dodati k izpisu. Spremenljivka z namreč označuje zadnje prosto mesto pred začetkom vrste. Tako dosežemo tudi izpis zadnjega elementa v vrsti - če bi namreč povečali z na koncu zanke po dodajanju k izpisu in šele nato zopet pregledovali pogoj ali je z že enak k-ju, se k na tak način ne bi mogel dodati k izpisu, ampak bi iz zanke izstopili en korak pred koncem. Ker nam že operacija toString izpiše vrsto oz. elemente vrste, ne potrebujemo še dodatne operacije izpis.