Teorie stivaStiva este o structură abstractă de date reprezentând un caz particular de listă în care introducerile şi extragerile se fac la un singur capăt, numit vârful stivei. Celălalt capăt are denumirea de bază a stivei. Fiind o listă, toate elementele unei stive sunt de acelaşi tip de dată. Dacă stiva nu conţine niciun element spunem că este vidă. Pe figură:

Operaţiile asociate structurii de stivă sunt: introducerea unui nou element, extragerea unui element, consultarea vârfului stivei, iniţializarea ca stivă vidă şi testul de stivă vidă. Toate aceste operaţii sunt efectuate în timp constant, de ordin de complexitate O(1). Se poate adăuga ca operaţie şi tipărirea conţinutului curent al stivei, operaţie efectuată în O(P), unde P reprezintă numărul de elemente aflate în stivă.

În alocare statică, pentru a gestiona o stivă este nevoie de un vector notat ST împreună cu un indice P număr natural, care este poziţionat pe primul element din stivă. Se consideră că elementele stivei vor fi memorate în locaţiile : ST[1], ST[2], ... , ST[P].

Atunci operaţiile cu stiva ST pot fi astfel detaliate în pseudocod:1. Iniţializarea drept stivă vidă: P0;2. Testul de stivă vidă (expresie logică): P=0;3. Introducerea în stivă a elementului A citit de la tastatură:

citeste A;PP+1;ST[P]A;

4. Extragerea din stivă şi tipărirea valorii A: ┌daca (P!=0) atunci│ AX[P];│ PP-1;│ scrie A;│ altfel │ scrie “stiva vida”└■

5. Tipărirea conţinutului curent al stivei:┌pentru I1 la P executa │ scrie ST[I];└■

Cerinţă: Să se scrie un program ce execută la cererea utilizatorului operaţiile de: adăugare a unui element în stivă (codificată cu 1), de extragere a unui element din stivă (codificată cu 2), de listare a conţinutului stivei (codificată cu 3). La apăsarea tastei 4 programul de încheie, iar la începutul programului stiva va fi vidă.

AplicatiiProblema 1. Să se citească succesiv elementele unui vector şi apoi să se tipărească acest

şir în ordine inversă. Se vor folosi numai operaţiile de lucru definite cu o stivă alocată static.

Problema 2. Fie un capăt de cale ferată la care se poate ajunge prin două linii: o linie de intrare a vagoanelor şi linia de ieşire a acestora. Se presupune că iniţial există un număr de N vagoane, numerotate în ordine de la 1 la N, pe linia de intrare. Dându-se un şir valid de 2*N operaţii de introducere (codificată cu 0) şi extragere (codificată cu valoarea 1) să se tipărească ordinea vagoanelor pe linia de ieşire. Şirul de operaţii este valid dacă el conduce la introducerea şi extragerea tuturor vagoanelor şi în niciun moment nu se cere efectuarea unei extrageri dacă în capătul de linie nu există vagoane (stivă vidă).

Exemplu: Pentru N=3 sunt trei vagoane în ordinea: 1, 2, 3. Dacă se aplică şirul de operaţii 0 0 1 1 0 1, atunci pe linia de ieşire vagoanele vor fi extrase în ordinea: 2, 1, 3.

Teorie coadaCoada este, ca şi stiva, un tip particular de listă, în care introducerile se fac la unul din

capete, numit şi baza cozii iar extragerile doar la capătul opus, numit vârful cozii. Operaţiile cu o coadă sunt: iniţializarea ca o coada vidă, introducerea unui nou element la

baza cozii, testul de coadă vidă, extragerea elementului din vârful cozii.Coada se implementează static folosind un vector C, împreună cu doi indici P şi U.

Indicele U este poziţionat pe ultimul element din coadă, iar indicele P cu o poziţie înaintea primului element din coadă. Astfel încât, atât la introducere cât şi la extragere mai întâi se modifică U respectiv P. În pseudocod:

1. Iniţializarea se rezumă la atribuirile:P0; U0;

2. Introducerea unui nou element înseamnă: citeste A; UU+1;C[U]A;

3. Pentru extragerea primului element trebuie mai întâi făcut testul de coadă vidă:┌daca (P=U) atunci │ scrie”coada vida”.STOP│ altfel │ PP+1;│ AC[P];│ scrie A;└■Toate operaţiile au ordinul de complexitate O(1).

Cerinţă: Să se scrie un program ce execută la cererea utilizatorului operaţiile de: adăugare a unui element în coadă (codificată cu 1), de extragere a unui element din coadă (codificată cu 2), de listare a conţinutului cozii (codificată cu 3). La apăsarea tastei 4 programul se încheie, iar la începutul programului coada va fi vidă.

AplicatiiProblema 1. Deoarece prin operaţiile de introducere şi extragere de elemente din coadă,

datele “migrează” către baza cozii, pentru o mai bună gestionare a memoriei este util ca vectorul ce reţine elementele cozii să fie imaginat circular, adică după ultima poziţie să urmeze din nou prima sa poziţie. Ca în figura următoare:

În această figură este reprezentată o coadă circulară ce conţine trei elemente, în ordine: 3, 7, 5. Operaţiile de introducere şi extragere se modifică corespunzător în cazul în care P sau U depăşesc numărul maxim N de poziţii ale vectorului.

Testul de coadă vidă rămâne P=U, iar pentru a distinge cazurile de coadă vidă şi coadă plină se vor folosi efectiv doar maxim N-1 poziţii din vector. Testul care arată “umplerea” tuturor poziţilor (coadă plină) este: (U+1)%N=P. Iată în pseudocod introducerea şi extragerea dintr-o coadă circulară:citeste A;UU+1;┌daca (U>N) atunci│ U1;└■┌daca (P=U) atunci │ scrie”coada plina”.STOP│ altfel │ C[P]A;└■

┌daca (P=U) atunci │ scrie”coada vida”.STOP│ altfel │ PP+1;│ ┌daca (P>N) atunci│ │ P1;│ └■│ AC[P];│ scrie A;└■

Cerinţă: Să se scrie un program ce execută la cererea utilizatorului operaţiile de: adăugare a unui element într-o coadă circulară (codificata cu 1), de extragere a unui element din coada circulară (codificată cu 2). La apăsarea tastei 3 programul de încheie, iar la începutul programului coada va fi vidă.

Problema 2. Fie o linie bifurcată de cale ferată ca în figura de mai jos:

Un număr de N vagoane se află pe linia de intrare in ordinea: 1, 2, ... , N. Se poate executa succesiv câte una din următoarele mişcări:

1: in_coada: vagonul curent intră pe linia de aşteptare.2: out_coada: un vagon iese de pe linia de aşteptare.3: trece: vagonul curent trece la ieşire folosind linia directă.Fiind dat un şir corect de mişcări, să se afişeze ordinea la ieşire a celor N vagoane.Exemplu: N=4 şirul de mişcări S=(1, 3, 1, 3, 2, 2) Atunci ordinea vagoanelor pe linia de

ieşire este: 2, 4, 1, 3.