Download - Stiva
1
Stiva
Stiva este un caz particular de listă liniară, adică o înşiruire de valori. De cele mai multe
ori stiva se implementează static, folosind vectori.
Definiţia listei liniare: O listă liniară este o secvenţă de elemente având acelaşi tip de
dată, în care fiecare element, cu excepţia ultimului, are un succesor direct şi fiecare element,
în afară de primul, are un predecesor direct. Operaţiile cele mai importante cu listele sunt
adăugarea şi extragerea unor elemente în sau din listă.
Definiţia stivei: O stivă este o listă în care adăugările şi extragerile de elemente se
efectuează la un singur capăt al listei, numit vârful stivei. Principiul de funcţionare al stivei
este “ultimul intrat, primul ieşit” sau LIFO (Last In, First Out).
Pentru a ne imagina o stivă, să ne gândim la mai multe farfurii aşezate una peste alta.
Când dorim să adăugăm o farfurie, o aşezăm peste celelalte, iar când luăm o farfurie, o luăm
pe cea aflată deasupra. Procedând în acest mod, evităm să spargem farfuriile!
Operaţiile caracteristice stivei sunt:
a) Crearea unei stive vide
b) Inserarea unui element în vârful stivei (operaţia PUSH)
c) Extragerea unui element din vârful stivei (operaţia POP)
d) Accesarea elementului din vârf, fără a modifica valoarea acestuia (operaţia TOP)
Rolul stivelor în informatică este unul fundamental. Pentru realizarea apelului funcţiilor şi
a recursivităţii este necesară structura de stivă. O altă aplicaţie a stivelor este evaluarea
expresiilor matematice şi compilarea programelor scrise într-un limbaj de programare. Prin
modul de funcţionare stiva are proprietatea de a extrage elementele introduse în stivă în
ordine inversă faţă de adăugărea lor.
Implementarea Stivei
Stiva, ca structură abstractă de date, poate fi implementată în diferite moduri. De exemplu,
putem implementa stiva ca un vector în care să reţinem elementele stivei. Pentru ca acest
vector să funcţioneze ca o stivă, singurele operaţii permise sunt operaţiile caracteristice stivei.
În continuare presupunem că dorim ca în stivă să se afle cel mult 100 de elemente.
Definirea unei stive într-un program C++ se poate scrie după cum urmează:
const int DMax=100; //numărul maxim de elemente
int S[DMax+1]; //stiva (vectorul) S
int k,x; //vârful stivei (egal cu numărul elementelor din listă)
// x elementul din vârf
a) Crearea unei stive vide:
k=0; // stiva nu are elemente
k=0
2
b) Inserarea unui element x în vârful stivei, operaţia PUSH(x):
if (k==DMax) //stiva este plină
cout<<”Eroare: stiva plină!”;
else //inserăm x în vârful stivei S S[++k] = x;
Modificările stivei prin operaţiile PUSH(7), PUSH(2), PUSH(5) sunt reprezentate în
figura următoare:
c) Extragerea unui element x din vârful stivei, operaţia POP(x):
if (k==0) //stiva este vidă
cout<<”Eroare: stiva vidă!”;
else //inserăm x în stiva S x = S[k--];
Prin extragerea elementului din vârful stivei, de pe nivelul k=3, aceasta revine la nivelul
anterior, k=2. Se consideră că elementul de pe nivelul 3 (fostul vârf al stivei) nu mai aparţine
stivei.
d) Operaţia TOP este o operaţie de informare, care permite consultarea valorii
elementului din vârful stivei, fără a modifica valoarea acestuia.
x = S[k];
k=0
k=1
k=2 2
7
k=3
2
7
5
7 2
k=3
2
7
2
7
k=2
5
3
Aplicaţie: Verificarea parantezelor
1. O aplicaţie utilă a structurei de tip stivă este algoritmul prin care se verifică dacă o
expresie ce conţine paranteze este bine formată. O expresie cu paranteze este un şir de
paranteze deschise ‘(‘ şi închise ‘)‘. Expresia este bine formată dacă:
-începe cu o paranteză deschisă (
-fiecare paranteză deschisă ( are o paranteză închisă corespunzătoare )
De exemplu, expresia ( ( ) ( ) ) este bine formată, iar expresia ( ( ) ( ) este incorectă.
Algoritmul pentru verificarea corectitudinii unei expresii cu paranteze foloseşte o stivă de
caractere, în care se memorează doar parantezele deschise (. Paşii algoritmului sunt:
- la citirea unei paranteze deschise, aceasta se adaugă în stivă cu PUSH (
- la citirea unei paranteze închise, verificăm dacă stiva conţine o paranteză deschisă ) şi o
scoatem din stivă cu POP; dacă apare eroare la operaţia POP atunci expresia este
incorectă (avem o paranteză închisă fără corespondent)
- la sfârşitul şirului, stiva trebuie să fie vidă, k=0, dacă expresia este bine formată
În continuare o să urmărim aplicarea algoritmului pentru şirul bine format ( ( ) ( ) ):
La început, stiva este vidă:
Şirul citit este “( ( ) ( ) )”
Primul character din şir ( este adăugat în stivă
( ( ) ( ) )
Al doilea caracter este tot o paranteză deschisă (
( ( ) ( ) )
k=0
k=1 (
k=2
(
(
4
Al treilea caracter citit este paranteza închisă pereche a ultimei paranteze adăugate,
care va fi extrasă din stivă:
( ( ) ( ) )
Urmează al patrulea caracter o nouă paranteză deschisă:
( ( ) ( ) )
Al cincilea caracter este paranteza închisă pereche a ultimei paranteze deschise:
( ( ) ( ) )
Ultimul caracter este paranteza închisă corespunzătoare primului caracter citit:
( ( ) ( ) )
În final, stiva este vidă, ceea ce înseamnă că expresia este corect construită!
2. Algoritmul de mai sus poate fi adaptat pentru expresii formate cu toate tipurile de
paranteze folosite la matematică paranteze mici, paranteze drepte şi acolade. Condiţiile de
funcţionare a algoritmului sunt aceleaşi, în plus mai trebuie să testăm ca o paranteză închisă
să aibă ca pereche în stivă o paranteză de acelaşi tip. Parantezele nu au voie să se
intersecteze, de exemplu şirul ( [ ) ] este incorect format. Spre deosebire de regulile de la
matematică într-o expresie cu mai multe tipuri de paranteze este permis ca parantezele drepte
sau acoladele să fie incluse între paranteze mici, adică ([]{}) este o expresie corectă.
k=2
(
(
k=1 (
k=2
(
(
k=2
(
(
k=1 (
k=0
k=1 (
5
În acest caz, paşii algoritmului sunt:
- la citirea oricărui tip de paranteză deschisă, aceasta se adaugă în stivă cu PUSH
- orice alt caractere care nu este o paranteză deschisă sau închisă se ignoră
- la citirea unei paranteze închise, verificăm dacă stiva conţine o paranteză deschisă de
acelaşi tip şi o scoatem din stivă cu POP; dacă apare eroare la operaţia POP atunci
expresia este incorectă (avem o paranteză închisă fără corespondent)
- la sfârşitul şirului, stiva trebuie să fie vidă, k=0, dacă expresia este bine formată
De exemplu, expresia (x{x[]}x)este evaluată aşa cum apare în imaginea următoare:
6
Fişierul intrare/ieşire:
paranteze.in, paranteze.out
Sursă Tiberiu Popoviciu 2011,
Clasa a 9-a
Autor Cosmin-Mihai Tutunaru Adăugată de
Cosmin-Mihai Tutunaru
•stocarul
Timp execuţie pe test
0.1 sec Limită de memorie
32768 kbytes
Scorul tău în arhivă N/A Dificultate N/A
Paranteze
Ţirbi tocmai a învăţat la un curs de Silverlight despre paranteze rotunde "(, )", drepte "[, ]" şi
acolade "{, }". Un şir este parantezat corect dacă este construit conform regulilor:
<şir parantezat corect> = <şirul vid>
<şir parantezat corect> = "(" + <şir parantezat
corect> + ")"
<şir parantezat corect> = "[" + <şir parantezat
corect> + "]"
<şir parantezat corect> = "{" + <şir parantezat
corect> + "}"
<şir parantezat corect> = <şir parantezat corect>
+ <şir parantezat corect>
Cerinţă
Ca la orice curs, se dau teme de casă, iar Ţirbi a primit următoarea problemă: Având un şir cu N
paranteze, să se afle lungimea maximă a unei secvenţe parantezată corect.
Date de intrare
Fişierul de intrare paranteze.in conţine pe prima linie numărul natural N, iar pe următoarea linie
un şir cu N paranteze.
Date de ieşire
Fişierul de ieşire paranteze.out conţine lungimea maximă a unei secvenţe corect parantezată.
Restricţii
1 ≤ N ≤ 1 000 000
Pentru 50% din teste N ≤ 1 000
Exemplu
paranteze.in paranteze.out
13
{)([({})]([{}
6
Explicaţie
Secvenţa parantezată corect este îngroşată. {)( [({})] ([{}
7
Fişierul intrare/ieşire:
paranteze2.in, paranteze2.out
Sursă Infoarena Monthly 2012,
Runda 1
Autor Andrei Cristian Lambru Adăugată de Mr. Noname •cezar305
Timp execuţie pe test
0.05 sec Limită de memorie
16384 kbytes
Scorul tău în arhivă N/A Dificultate N/A
Paranteze2
Se da un sir de caractere S, de lungime N, ce poate contine caracterele '(' si ')' . Sa se calculeze
si sa se afiseze cate subsecvente ale lui S reprezinta parantezari corecte.
Se numeste o parantezare corecta un sir T de paranteze daca se poate forma astfel:
T = '()'
sau
T = '(' + t + ')' , unde t este o parantezare corecta
sau
T = t1+ t2 +...+tn , unde t1, t2, ..., tn sunt parantezari corecte.
Date de intrare
Fişierul de intrare paranteze2.in va contine pe prima si unica sa linie sirul S.
Date de ieşire
În fişierul de ieşire paranteze2.out se va scrie numarul subsecventelor ce constituie parantezari
corecte.
Restricţii
1 ≤ N ≤ 1.000.000
se intelege subsecventa a sirului S un interval compact de forma [i..j] cu 1 ≤ i ≤ j ≤ N
Exemplu
paranteze2.in paranteze2.out
()(()) 4
Explicaţie
Cele 4 subsecvente sunt 1-2, 3-6, 4-5 si 1-6