Numim coada cu dubla prioritate
(dequeue) o structura de date care
suporta
urmatoarele operatii:
- inserare
element la sfaristul cozii
- inserare
element la inceputul cozii
- extragere
element de la sfarsitul cozii
- extragere
element de la inceputul cozii
- accesarea
elementului de la inceputul cozii
- accesarea
elementului de la sfarsitul cozii.
Vom utiliza
doua cozi cu dubla prioritate:
1. Coada a
cu elemente de tip caracter in care inseram
succesiv caracterele
din sirul
initial si ulterior cele specificate in operatiile
din fisierul de intrare.
2. Coada b
cu elemente de tip intreg;
b[i]=lungimea secventei
regulate care incepe cu pozitia i;
Implementam
cozile a si b ca doi vectori.
Pentru a
putea realiza operatii si la inceputul si la
sfarsitul vectorilor,
am dublat
spatiul de memorie necesar pentru fiecare dintre
cei doi vectori
si am
inceput inserarea elementelor de la mijloc.
Initial
inseram in ordine toate caracterele sirului citit
in coada a.
Pentru a
pastra ordinea, fiecare noua caracter va fi
inserat la sfarsitul cozii
Cand la
inseram o paranteza deschisa la sfarsitul cozii,
iar pe ultima pozitie
in coada
este paranteza deschisa corespunzatoare, deducem
ca se formeaza
o secventa
regulata cu lungimea 2 mai mare decat cea deja
existenta pe aceasta pozitie.
Prin urmare
retinem in vectorul b aceasta lungime si eliminam
din coada a cele doua paranteze
(practic
fiecare secventa regulata formata este eliminata
din a, dar in b retinem lungimile secventelor
formate).
Cand inseram
la inceputul cozii a o paranteza deschisa iar la
inceputul cozii a era paranteza inchisa
corespunzatoare,
se formeaza
o secventa regulata cu 2 mai mare si executam
aceleasi operatii ca in cazul precedent.
Pentru
evaluare au fost utilizate 10 teste (numerotate de
la 0 la 9) si s-au acordat 10 puncte pentru
fiecare test. |