STIVE SI COZI - LISTE STIVA

Stive si Cozi

1 Liste stiva

O stiva este o lista cu acces la un singur capat, numit "varful" stivei. Singurele operatii permise sunt inserare in prima pozitie si stergere din prima pozitie (eventual si citire din prima pozitie). Aceste operatii sunt denumite traditional "push" (pune pe stiva) si "pop" (scoate din stiva) si nu mai specifica pozitia din lista, care este implicita . O stiva mai este numita si lista LIFO ('Last In First Out'), deoarece ultimul element pus este primul care va fi extras din stiva.

Operatiile asociate tipului abstract 'stiva' sunt:

- initializare stiva vida (initSt)

- test stiva vida (emptySt)

- pune un obiect pe stiva (push)

- extrage obiectul din varful stivei (pop)

- obtine valoare obiect din varful stivei (top)

Operatiile cu o stiva pot fi privite ca niste cazuri particulare de operatii cu liste oarecare, dar este mai eficienta o implementare directa a operatiilor 'push' si 'pop'.

O solutie simpla este folosirea directa a unui vector, cu adaugare la sfarsit (in prima pozitie libera) pentru 'push' si extragerea ultimului element, pentru 'pop'.

Exemplu de afisare a unui numar intreg fara semn in binar, prin memorarea in stiva a resturilor impartirii prin 2, urmata de afisarea continutului stivei.

void binar (int n)

while (vs > 0)

printf ('n');

}

Varful stivei (numit si 'stack pointer') poate fi definit ca fiind pozitia primei pozitii libere din stiva sau ca pozitie a ultimului element pus in stiva. Diferenta de interpretare are efect asupra secventei de folosire si modificare a varfului stivei:

void binar (int n)

while (vs >= 0)

printf ('n');

}

Ca si pentru alte colectii de date, vom prefera definirea unor functii pentru operatii asociate structurii de stiva. Vom exemplifica cu o stiva realizata ca un vector, cu adaugare si stergere la sfarsitul vectorului.

#define M 100 // dimens maxima stiva

typedef struct Stack;

// initializare stiva

void initSt (Stack & s)

// test stiva goala

int emptySt ( Stack s)

// pune in stiva pe x

void push (Stack & s, T x)

// scoate in x din stiva

T pop (Stack & s)

T top (Stack s)

Dimensionarea vectorului stiva este dificila in general, dar putem folosi un vector extensibil dinamic (alocat si realocat dinamic). Modificarile apar numai initializarea stivei si la punere in stiva.

De asemenea, se poate folosi o lista inlantuita cu adaugare si extragere numai la inceputul listei. Exemplu:

typedef struct s nod ;

typedef nod * Stack; // tipul Stack este un tip pointer

// initializare stiva

void initSt ( Stack & s)

// test stiva goala

int emptySt (Stack s)

// pune in stiva un obiect

void push (Stack & s, T x)

// scoate din stiva un obiect

T pop (Stack & s)

// obiect din varful stivei

T top (Stack s)

Daca sunt necesare stive cu continut diferit in acelasi program sau daca in aceeasi stiva trebuie memorate date de tipuri diferite vom folosi o stiva de pointeri 'void*'.

2 Aplicatie : evaluare expresii aritmetice

Evaluarea expresiilor aritmetice este necesara intr-un program interpretor BASIC, intr-un program de calcul tabelar (pentru formulele care pot apare in celulele foii de calcul) si in alte programe care admit ca intrari expresii (formule) si care trebuie sa furnizeze rezultatul acestor expresii.

Pentru simplificare vom considera numai expresii cu operanzi numerici intregi de o singura cifra, la care rezultatele intermediare si finale sunt tot intregi de o cifra.

Problema evaluarii expresiilor este aceea ca ordinea de aplicare a operatorilor din expresie (ordinea de calcul) este diferita in general de ordinea aparitiei acestor operatori in expresie (intr-o parcurgere de la stanga la dreapta). Exemplu:

(5-6/2) * (1+3)

Evaluarea acestei expresii necesita calculele urmatoare (in aceasta ordine):

6/2=3, 5-3=2, 1+3=4, 2*4=8

Ordinea de folosire a operatorilor este determinata de importanta lor (inmultirea si impartirea sunt mai importante ca adunarea si scaderea) si de paranteze.

Una din metodele de evaluare a expresiilor necesita doua etape si fiecare din cele doua etape utilizeaza cate o stiva :

- Transformarea expresiei in forma postfixata, folosind o stiva de operatori.

- Evaluarea expresiei postfixate, folosind o stiva de operanzi (de numere).

In forma postfixata a unei expresii nu mai exista paranteze, iar un operator (binar) apare dupa cei doi operanzi folositi de operator. Exemple de expresii postfixate:

Expresie infixata    Expresie postfixata

1+2 1 2 +

1+2+3 1 2 + 3 +

1+ 4/2 1 4 2 / +

(5-6/2)*(1+3) 5 6 2 / - 1 3 + *

Ambele etape pot folosi acelasi tip de stiva sau stive diferite ca tip de date.

Comparand cele doua forme ale unei expresii se observa ca ordinea operanzilor se pastreaza in sirul postfixat, dar operatorii sunt rearanjati in functie de importanta lor si de parantezele existente. Algoritmul de trecere la forma postfixata foloseste o stiva de operatori astfel: operatorul extras din sirul infixat este comparat cu operatorul din varful stivei si cel mai important dintre ele trece in sirul postfixat. O paranteza '(' este pusa pe stiva iar o paranteza ')' scoate din stiva toti operatorii pana la o paranteza deschisa (inclusiv). Functia urmatoare foloseste o stiva de caractere:

void topostf (char * in, char * out)

in++; // avans in sirul infixat

}

while (! empty(st) ) // scoate din stiva in sirul postfixat

*out++=pop(st);

*out=0; // ptr terminare sir rezultat

}

Functia 'pri' are ca rezultat prioritatea operatorului primit ca argument:

int pri (char op) ; // tabel de operatori

int pr[ ] =; // tabel de prioritati

for (k=0;k<nop;k++)

if (op==vop[k]) // cauta operator in tabel

return pr[k]; // prioritate operator din pozitia k

return -1; // operator negasit in tabel

}

Sunt posibile si alte variante ale functiei 'topostf': se adauga paranteze in jurul expresiei primite si se repeta ciclul principal pana la golirea stivei (ultima paranteza din sirul de intrare va scoate din stiva toti operatorii de prioritate mica ramasi).

Evaluarea expresiei postfixate parcurge expresia de la stanga la dreapta, pune pe stiva toti operanzii intalniti, iar la gasirea unui operator aplica acel operator asupra celor doi operanzi scosi din varful stivei si pune in stiva rezultatul partial obtinut.

Evolutia stivei la evaluarea expresiei postfixate 5 6 2 / - 1 3 + * va fi:

(3=6/2)

(2=5-3)

(4=1+3)

(8=2*4)

Functie de evaluare a unei expresii postfixate cu operanzi de o singura cifra:

int eval ( char * in)

in++; // avans in sirul postfixat

}

return pop(st); // rezultat final in stiva

}

Functia 'calc' calculeaza valoarea unei expresii cu numai doi operanzi:

int calc ( int x, int y, char op)

}

3 Eliminarea recursivitatii folosind o stiva

Nu exista o categorie de algoritmi recursivi ci doar posibilitatea de exprimare recursiva a unor algoritmi in care se repeta anumite operatii.

Un subprogram recursiv este un subprogram care se apeleaza pe el insusi, o data sau de mai multe ori. Orice subprogram recursiv poate fi rescris si nerecursiv, iterativ, prin repetarea explicita a operatiilor executate la fiecare apel recursiv. O functie recursiva realizeaza repetarea unor operatii fara a folosi o instructiune de ciclare.

In anumite situatii exprimarea recursiva este mai naturala si mai compacta decat forma nerecursiva. Este cazul operatiilor cu arbori binari si al altor algoritmi de tip "divide et impera" (de divizare in subprobleme).

In alte cazuri, exprimarea iterativa este mai naturala si mai eficienta ca timp si ca memorie folosita, fiind aproape exclusiv folosita: calcule de sume sau de produse, operatii de cautare, operatii cu liste inlantuite, etc. In plus, functiile recursive cu mai multi parametri pot fi inutilizabile pentru un numar mare de apeluri recursive, acolo unde marimea stivei implicite (folosita de compilator) este limitata.

Cele mai simple functii recursive corespund unor relatii de recurenta de forma f(n)= r(f(n-1)) unde n este un parametru al functiei recursive. La fiecare nou apel valoarea parametrului n se diminueaza, pana cand n ajunge 0 (sau 1), iar valoarea f(0) se calculeaza direct si simplu.

Un alt mod de a interpreta relatia de recurenta anterioara este acela ca se reduce (succesiv) rezolvarea unei probleme de dimensiune n la rezolvarea unei probleme de dimensiune n-1, pana cand reducerea dimensiunii problemei nu mai este posibila.

Functiile recursive au cel putin un argument, a carui valoare se modifica de la un apel la altul si care este verificat pentru oprirea procesului recursiv.

Exemple de probleme rezolvabile prin relatii de recurenta :

- Calcul factorial: fact(n) = n * fact(n-1) ptr. n > 0

- Calcul suma: suma(n) = n + suma(n-1) ptr. n > 0

- Calcul putere: put (x,n) = x * put(x,n-1) ptr. n > 0

- Determinare cmmdc: cmmdc(a,b) = cmmdc (b,a%b) ptr b > 0

- Calcul combinari: comb(n,k) = comb (n,k-1) * k /(n-k+1)

- Cautare intr-un vector sau intr-o lista inlantuita

- Afisarea unui vector sau unei liste inlantuite

Orice subprogram recursiv trebuie sa contina o instructiune 'if' (chiar la inceput ), care sa verifice conditia de oprire a procesului recursiv. In caz contrar se ajunge la un proces recursiv ce tinde la infinit si se opreste numai prin umplerea stivei.

Eliminarea recursivitatii este justificata atunci cand dimensiunea maxima a stivei utilizate de compilator limiteaza dimensiunea problemei care trebuie rezolvata prin algoritmul recursiv. In stiva implicita se pun automat toti parametrii formali, toate variabilele locale si adresa de revenire din functie.

Functiilele cu un singur apel recursiv ca ultima instructiune (cu recursivitate finala) pot fi rescrise iterativ fara a folosi o stiva, numai inlocuind instructiunea 'if' cu o instructiune 'while'.

Functiile cu un apel recursiv urmat de alte operatii sau cu mai multe apeluri recursive nu pot fi rescrise iterativ fara a utiliza o stiva.

In exemplul urmator se afiseaza un numar intreg n intr-o baza data b (intre 2 si 16) dupa urmatorul rationament ilustrat pentru b=2: sirul de cifre pentru n este format din sirul de cifre pentru (n/2) urmat de o cifra 0 sau 1 care se obtine ca n%2. De exemplu

numarul n= 22 se afiseaza in binar ca 10110 (16+4+2)

10110 este sirul binar pentru 22 ( 22 = 11*2 +0)

1011 este sirul binar pentru 11 (11 = 5*2 + 1)

10 1 este sirul binar pentru 5 ( 5 = 2*2 +1)

10 este sirul binar pentru 2 ( 2 = 1*2 +0)

1 este sirul binar pentru 1 ( 1 = 0*2 +1)

Exemplul urmator arata cum se poate folosi o stiva pentru rescrierea iterativa a unei functii recursive de afisare in binar.

void binar (int n)

while (! emptySt(st))

printf ('n');

}

Un alt exemplu de utilizare a unei stive este o functie nerecursiva pentru afisarea valorilor din nodurile unui arbore binar; stiva se foloseste pentru memorarea adreselor nodurilor prin care s-a trecut dar care nu au fost afisate, urmand ca la revenirea prin aceste noduri sa se afiseze valorile lor.

In acest exemplu exista o situatie mai rar intalnita la utilizarea unei stive: stiva se poate goli pe parcursul algoritmului, iar golirea stivei nu se poate folosi ca o conditie de terminare a algoritmului de vizitare. Solutia este introducerea in stiva a unei adrese oarecare, diferita de NULL si de orice adresa de nod din arbore; algoritmul se opreste la scoaterea din stiva a acestei adrese.

void infix (tnod * r) else

}

}

printf ('n');

}

Evolutia stivei la afisarea infixata a arborelui binar: 5(2(1,4(3,)),8(6(,7),))

Operatie Stiva Afisare

initSt -

push (&5) &5

push (&2) &5,&2

push (&1) &5,&2,&1

pop &5,&2 1

pop &5 2

push(&4) &5,&4

push(&3) &5,&4,&3

pop &5,&4 3

pop &5 4

pop - 5

push (&8) &8

push (&6) &8,&6

pop &8 6

push (&7) &8,&7

pop &8 7

pop - 8

4 Recursivitate indirecta

In cazul a doua sau mai multor functii care se apeleaza reciproc pot apare secvente de apeluri de forma A->B->A sau A->B->C->A care conduc la o recursivitate indirecta pentru functia A. Un exemplu sunt functiile care transpun urmatoarele reguli de formare a unor expresii aritmetice:

expr ::= termen | expr + termen | expr - termen

termen ::= factor | termen * factor | termen / factor

factor ::= cifra | ( expr )

Functiile urmatoare realizeaza analiza unor expresii aritmetice corecte sintactic, cu afisarea sirului postfixat. Expresiile pot contine numai operanzi de o singura cifra, paranteze si operatorii '+', '-','*, '/'. Fiecare functie inainteaza in expresia analizata iar rezultatul lor este adresa din sirul infixat de unde continua analiza expresiei.

Desi se bazeaza pe definitii recursive, functiile de analiza a subexpresiilor nu sunt direct recursive, folosind o rescriere iterativa a definitiilor dupa cum urmeaza:

opad ::= + |-

expr ::= termen | termen opad termen [opad termen]

Functia 'expr' este apelata o singura data in programul principal si poate apela de mai multe ori functiile 'term' si 'fact', pentru analiza subexpresiilor continute de expresie

Exemplu de implementare:

// expresie

char * expr ( char * exp )

return p;

// termen

char * term (char *exp)

return p;

// factor

char * fact (char *exp)

else if ( ch=='(')

else return 0; // eroare : factor gresit

Functiile 'expr' si 'term' se bazeaza pe definitii gramaticale recursive dar nu sunt direct recursive. Regulile gramaticale prezentate sunt recursive la stanga, deci au forma generala: <a> ::= <b> | <a> <c> si sunt greu de transpus in functii recursive, deoarece ambele alternative posibile incep cu simbolul <b> si nu se poate decide care dintre ele se aplica pentru o anumita expresie. O definitie recursiva la stanga se poate rescrie ca definitie recursiva la dreapta. Exemple pentru expresii aritmetice:

<expr> ::= <term> <restexp>

<restexp> ::= nimic | + <term><restexp> | - <term><restexp>

<term> ::= <factor> <restterm>

<restterm> ::= nimic | * <factor><restterm> | / <factor><restterm>

Trecerea expresiilor aritmetice la forma postfixata se poate face si nerecursiv, cu o stiva. Majoritatea aplicatiilor cu stive pot fi privite si ca alternative la solutii cu functii recursive pentru aceleasi aplicatii.

Un alt exemplu este evaluarea formei postfixate (prefixate) a expresiilor aritmetice prezentata de obicei ca aplicatie pentru stive. Ideea formei recursive a functiei de evaluare este aceea ca orice operator se aplica asupra rezultatelor unor subexpresii, deci se poate aplica definitia recursiva urmatoare:

<pf> ::= <val> | <pf><pf><op>

unde: <pf> este o expresie prefixata, <val> este o valoare (un operand numeric) si <op> este un operator aritmetic.

Urmeaza o functie recursiva pentru evaluarea unei expresii postfixate care contine numai cifre zecimale si operatori binari.

// evaluare expr postfixata

int eval ( char *& p )

5 Liste coada

O coada ('Queue'), numita si lista FIFO ('First In First Out') este o lista la care adaugarea se face pe la un capat (de obicei la sfarsitul cozii), iar extragerea se face de la celalalt capat (de la inceputul cozii). Ordinea de extragere din coada este aceeasi cu ordinea de introducere in coada, ceea ce face utila o coada in aplicatiile unde ordinea de servire este aceeasi cu ordinea de sosire: procese de tip 'vanzator - client' sau 'producator - consumator'. In astfel de situatii coada de asteptare este necesara pentru a acoperi o diferenta temporara intre ritmul de servire si ritmul de sosire, deci pentru a memora temporar cereri de servire (mesaje) care nu pot fi inca prelucrate.

Operatiile cu tipul abstract 'coada' sunt:

- initializare coada (initQ)

- test coada goala (emptyQ)

- adauga un obiect la coada (addQ, insQ, enqueue)

- scoate un obiect din coada (delQ, dequeue)

Ca si alte liste abstracte, cozile pot fi realizate ca vectori sau ca liste inlantuite.

O coada inlantuita poate fi definita prin :

- Adresa de inceput a cozii, iar pentru adaugare sa se parcurga toata coada pentru a gasi ultimul element;

- Adresele primului si ultimului element, pentru a elimina timpul de parcurgere a listei la adaugare;

- Adresa ultimului element, care contine adresa primului element (coada circulara).

Programul urmator foloseste cea de a doua solutie.

// definire tipuri de date folosite

typedef struct nod Nod;

typedef struct Queue;

// initializare coada

void initQ (Queue & q)

// test coada goala

int emptyQ (Queue q)

// adaugare obiect x la o coada

void addQ (Queue & q, T x)

}

// scoate primul element din coada

T delQ (Queue & q)

Implementarea unei cozi printr-un vector circular (numit si buffer circular) limiteaza numarul maxim de valori ce pot fi memorate temporar in coada. Caracterul circular permite reutilizarea locatiilor eliberate prin extragerea unor valori din coada.

Campul 'ultim' contine indicele din vector unde se va adauga un nou element, iar 'prim' este indicele primului (celui mai vechi) element din coada. Deoarece "prim" si "ultim" sunt egale si cand coada e goala si cand coada e plina, vom memora si numarul de elemente din coada.

// coada realizata ca vector circular

#define M 100 // capacitate vector coada

typedef struct Queue ;

// operatii cu coada vector

void initQ (Queue & q)

int fullQ (Queue q)

int emptyQ (Queue q)

void addQ (Queue & q, T x )

T delQ (Queue & q)

Pentru a intelege utilizarea acestui tip de coada vom descrie o secventa de operatii cu o coada de numai 3 elemente :

Operatie x prim ultim nel elem fullQ emptyQ

initial 1 0 0 0 0 0 0 T

addQ 1 0 1 1 1 0 0

addQ 2 0 2 2 1 2 0

addQ 3 0 0 3 1 2 3 T

delQ 1 1 0 2 0 2 3

addQ 4 1 1 3 4 2 3 T

delQ 2 2 1 2 4 0 3

addQ 5 2 2 3 4 5 3 T

delQ 3 0 2 2 4 5 0

delQ 4 1 2 1 0 5 0

addQ 6 1 0 2 0 5 6

delQ 5 2 0 1 0 0 6

delQ 6 0 0 0 0 0 0 T

Urmeaza o aplicatie clasica pentru o coada.

Explorarea unui arbore sau unui graf in latime (pe niveluri succesive) necesita memorarea succesorilor (fiilor) unui nod. Dupa vizitarea nodului de plecare (radacina in cazul unui arbore) se pun in coada toti succesorii lui, care vor fi apoi extrasi in ordinea in care au fost pusi. Dupa ce se extrage un nod se adauga la sfarsitul cozii succesorii lui. In felul acesta, fii unui nod sunt prelucrati dupa fratii nodului respectiv.

Exemplu de evolutie a cozii de pointeri la noduri pentru arborele binar urmator:

5 ( 3 ( 2 , 4 ) , 7 ( 6 , 8 ) )

(scrie 5)

(scrie 3)

(scrie 7)

4 6 8 (scrie 2)

(scrie 4)

(scrie 6)

(scrie 8)

// vizitare arbore binar nivel cu nivel folosind o coada

int vizitAB ( Nod * r, int v[ ])

return k; // dimensiune vector v (nr de noduri)

}

In varianta prezentata am considerat r !=NULL si nu s-au mai pus in coada si pointerii egali cu NULL, dar este posibila si varianta urmatoare:

void printAB ( Nod * r)

}

printf ('n');

}

Uneori se defineste o coada cu posibilitati de adaugare si de extragere de la ambele capete ale cozii, numita 'deque' ('double ended queue'), care are drept cazuri particulare stiva si coada, asa cum au fost definite aici. Operatiile caracteristice se numesc 'pushfront', 'pushback', 'popfront', 'popback' (in biblioteca STL).

6 Tipul 'coada cu prioritati'

O coada cu prioritati ('Priority Queue") este un container din care se extrage mereu elementul cu prioritate maxima (sau minima). Prioritatea este data de valoarea elementelor memorate sau de o cheie numerica asociata elementelor memorate in coada. Daca exista mai multe elemente cu aceeasi prioritate, atunci ordinea de extragere este aceeasi cu ordinea de introducere .

Algoritmii de tip 'greedy' folosesc in general o coada cu prioritati pentru listele de candidati; la fiecare pas se extrage candidatul optim din lista.

O coada cu prioritati este o structura dinamica, la care au loc alternativ introduceri si extrageri din coada. Daca nu se mai fac inserari in coada, atunci putem folosi un simplu vector, ordonat la inceput si apoi parcurs succesiv de la un cap la altul.

Operatiile specifice cozii cu prioritati sunt:

- Adaugare element cu valoarea x la coada q : addPQ ( q ,x)

- Extrage in x si sterge din coada q elementul cu cheia maxima (minima): delPQ(q)

- Citire (fara extragere) valoare minima sau maxima: minPQ(q)

- Initializare coada: initPQ (q).

- Test coada vida: emptyPQ (q)

Sunt posibile diverse implementari pentru o coada cu prioritati (vector ordonat, lista ordonata, arbore binar ordonat), dar cele mai bune performante le are un vector 'heap', din care se extrage mereu primul element, dar se face o rearanjare partiala dupa fiecare extragere sau insertie.

O aplicatie simpla pentru o coada cu prioritati este un algoritm greedy pentru interclasarea mai multor vectori ordonati cu numar minim de operatii (sau pentru reuniunea mai multor multimi cu numar minim de operatii).

Interclasarea a doi vectori cu n1 si respectiv n2 elemente necesita n1+n2 operatii. Fie vectorii 1,2,3,4,5,6 cu dimensiunile urmatoare: 10,10,20,20,30,30.

Daca ordinea de interclasare este ordinea crescatoare a vectorilor, atunci numarul de operatii la fiecare interclasare va fi:

Numarul total de operatii va fi 20+40+60+90+120=330

Numarul total de operatii depinde de ordinea de interclasare a vectorilor si are valoarea minima 300.

Ordinea de interclasare poate fi reprezentata printr-un arbore binar sau printr-o expresie cu paranteze. Modul de grupare care conduce la numarul minim de operatii este ( ( (1+2) +3) +6) + (4+5) deoarece la fiecare pas se executa operatiile:

Algoritmul de interclasare optima poate fi descris astfel:

creare coada ordonata crescator cu lungimile vectorilor

repeta

scoate valori minime din coada in n1 si n2

n=n1+n2

daca coada e goala

scrie n si stop

altfel

pune n in coada

Evolutia cozii cu prioritati pentru exemplul anterior cu 6 vectori va fi:

Urmeaza aplicatia de interclasare vectori cu numar minim de operatii, folosind o coada de numere intregi reprezentand lungimile vectorilor.

void main () ; // dimensiuni vectori

initpq (pq,n); // creare coada cu datele initiale

for (i=0;i<n;i++)

addpq (pq, &x[i]); // adauga adrese la coada

do

addpq(pq,s); // adauga suma la coada

} while (1);

printf ('n');

}

Programul anterior nu permite afisarea modului de grupare optima a vectorilor si nici operatia de interclasare propriu-zisa, deoarece nu se memoreaza in coada adresele vectorilor, dar se poate extinde cu memorarea numerelor (adreselor) vectorilor.