Modul 08 — Structuri avansate · Clasa a IX-a Fable

Stiva (LIFO) și coada (FIFO)

Stiva de farfurii: pui deasupra, iei tot de deasupra — ultimul intrat, primul ieșit. Coada la ghișeu: cine vine primul e servit primul.

🧪 Experimentează: adaugă și scoate elemente din ambele

x =

Stivă — LIFO

ultimul intrat = primul ieșit

▲ vârful — aici se întâmplă tot

Coadă — FIFO

primul intrat = primul ieșit

◀ fața (ies de aici) · spatele (intră aici) ▶

adaugă câteva valori în amândouă, apoi scoate — privește DIFERENȚA 👆

Implementarea cu un vector — tot ce-ți trebuie

Observă eleganța C++: stiva e doar un vector + un vârf: push = stiva[vf++] = x, pop = val = stiva[--vf]. Coada are doi indici: fața și spatele.

⚙ STL pe viu — programul se scrie singur: <stack> și <queue>

În C++ nu trebuie să-ți construiești singur structurile — biblioteca standard ți le dă gata făcute. Apasă instrucțiunile: containerele se mișcă SUS, iar programul tău se scrie singur JOS, linie cu linie, cu efectul în comentariu.

x =

stack<…> s

LIFO — totul se întâmplă la .top()

▲ s.top() — vârful

queue<…> q

FIFO — intră la spate, iese pe la .front()

◀ q.front() (iese) · spatele (intră) ▶

alege o instrucțiune 👆 — fiecare click devine o linie de program

Vectorul de frecvență

Cum numeri de câte ori apare fiecare valoare? Un vector f[] indexat după valorile posibile: la fiecare element x, faci f[x]++. O singură parcurgere!

șir =

Apasă „Pas" — fiecare element din șir își incrementează contorul. 👆

Bonusul e o comoară: dacă parcurgi f[] de la 0 la 9 și afișezi fiecare valoare de f[v] ori, obții șirul sortat — fără nicio comparație! Asta e ideea sortării cu frecvențe din Modulul 09 (counting sort).

Exerciții rezolvate

Două aplicații-far. Încearcă întâi singur!

1 · Paranteze echilibrate (stivă)

Pentru fiecare caracter citit: la „(" faci push; la „)" faci pop — stivă goală la pop = dezechilibru. La final, stiva trebuie să fie goală.

1int n, vf = 0; char c;

2bool ok = true;

3cin >> n; // câte caractere

4for (int i = 0; i < n; i++) {

5 cin >> c;

6 if (c == '(') vf++;

7 else if (c == ')') {

8 if (vf == 0) ok = false;

9 else vf--;

10 }

11}

12cout << (ok && vf == 0 ? "DA" : "NU");

Truc: aici „stiva" e doar un contor — nu ne interesează CE e în ea, doar CÂT.

2 · Valoarea cea mai frecventă (frecvențe)

Construiești f[0..99], apoi cauți maximul în f — șablonul de la Modulul 04, aplicat pe frecvențe.

1int a[] = {3,7,2,7,5,3,7,1};

2int n = 8, f[100] = {0};

3for (int i = 0; i < n; i++) f[a[i]]++;

4int maxF = 0, val = 0;

5for (int i = 0; i < 100; i++)

6 if (f[i] > maxF) { maxF = f[i]; val = i; }

7cout << val << " apare de " << maxF << " ori";

7 apare de 3 ori. La BAC: „cifra cea mai frecventă" = același cod, pe cifrele lui n.

Fișa de sinteză

Trei structuri, trei superputeri.

Stiva (LIFO): push/pop la vârf — stiva[vf++] = x · val = stiva[--vf]. Farfuriile!

STL gata făcute: stack<int> s / queue<int> q — push, pop, top/front, empty; merg și cu pair<int,int> (make_pair, .first/.second).

Coada (FIFO): enqueue la spate, dequeue din față — doi indici. Ghișeul!

Underflow: pop pe stivă goală / dequeue pe coadă goală = eroare — verifică întâi dacă mai e ceva!

Vector de frecvență: f[x]++ la fiecare element — o parcurgere, toate numărările.

Din frecvențe → șir sortat: afișezi fiecare v de f[v] ori — preview pentru counting sort (M09).

În clasa a X-a: pe vectorii SORTAȚI se construiesc căutarea binară și interclasarea — te așteaptă acolo.

Exersează pe pbinfo.ro:

#486 · ușoară

MinMax0

Valoarea minimă și maximă dintr-un șir de numere naturale.

Rezolvă pe pbinfo.ro →

#1452 · ușoară

Stergere_Element

Ștergeți elementul de pe o poziție dată și afișați șirul rezultat.

Rezolvă pe pbinfo.ro →

#264 · ușoară

MaxCif

Cifra care apare de cele mai multe ori în scrierea lui n — vector de frecvență!

Rezolvă pe pbinfo.ro →

#43 · ușoară

sumac

Suma elementelor unui șir — încălzire cu vectori înainte de sortări.

Rezolvă pe pbinfo.ro →