MyCodeSchool

Pasul 1 din 5

C++

Pasul 1 din 5 · Ce construiești

  • C++
  • Avansat
  • 12 minute

Stive și cozi în C++

Scrii programul care verifică dacă parantezele dintr-o expresie se închid corect: fiecare ), ] sau } trebuie să închidă ultima paranteză rămasă deschisă.

paranteze.cpp, în consolă
{[()()]}
DA
([)]
NU

Partea a doua din trei despre structuri de date. „Ultima deschisă se închide prima” e exact regula unei stive, ca un teanc de farfurii.

Pasul 2 din 5

Rulează-l linie cu linie

Trei elemente intră în stivă, unul iese. Panoul arată și conținutul stivei, de la bază la vârf.

stiva.cpp
#include <iostream>using namespace std;int main() {    int st[10], vf = 0;    st[++vf] = 4;    st[++vf] = 7;    st[++vf] = 1;    vf--;    cout << st[vf] << ' ' << vf;    return 0;}

Variabile

Ce apare pe ecran


      

  1. Linia 5. Vectorul ține elementele, vf ține poziția vârfului. 0 înseamnă stivă goală; elementele stau pe pozițiile 1, 2, 3…
  2. Linia 6. ++vf crește întâi vârful la 1, apoi pune 4 pe poziția 1. Operația se numește push.
  3. Linia 7. 7 se pune deasupra, pe poziția 2.
  4. Linia 8. 1 ajunge în vârf, pe poziția 3.
  5. Linia 9. Pop: scoți vârful doar scăzând vf. Valoarea 1 rămâne în memorie, dar nu mai face parte din stivă.
  6. Linia 10. Vârful e acum 7, pe poziția 2.
  7. Linia 11. main se încheie.
  8. Gata. Ultimul intrat, 1, a fost primul ieșit. Asta înseamnă LIFO: last in, first out.

Prezice ieșirea

Repeți vf--; încă o dată înainte de afișare. Ce apare?

Răspuns: „4 1”.

Două scoateri lasă în stivă doar elementul de la bază, 4, pe poziția 1.

Pasul 3 din 5

Stiva, coada și biblioteca standard

Fragmentele 1–3 stau în main. Cardul 4 e un program complet.

Stiva golită: ordinea inversă

lifo.cpp
int st[100], vf = 0;for (int x = 1; x <= 4; x++)    st[++vf] = x * 10;while (vf > 0) {    cout << st[vf] << ' ';    vf--;}

Ce apare pe ecran

40 30 20 10 

Intră 10, 20, 30, 40 și ies invers. De aceea stiva servește la „anulează” într-un editor, la apelurile de funcții și la orice problemă în care ultimul lucru început se termină primul.

Coada: primul venit, primul servit

coada.cpp
int c[100], prim = 1, ultim = 0;for (int x = 1; x <= 4; x++)    c[++ultim] = x * 10;prim++;c[++ultim] = 50;while (prim <= ultim) {    cout << c[prim] << ' ';    prim++;}

Ce apare pe ecran

20 30 40 50 

Elementele intră la ultim și ies de la prim. prim++ a scos 10, primul intrat. Coada e goală când prim > ultim. E regula FIFO: first in, first out.

Paranteze rotunde, fără vector

paranteze.cpp
char s[] = "(()())";int vf = 0;bool ok = true;for (int k = 0; s[k] != 0; k++)    if (s[k] == '(')        vf++;    else if (vf > 0)        vf--;    else        ok = false;cout << (ok && vf == 0);

Ce apare pe ecran

1

Cu un singur fel de paranteză, stiva poate fi doar un contor: vf numără parantezele deschise. Expresia e corectă dacă nicio închidere nu vine pe stivă goală și dacă la final nu rămâne nimic deschis.

stack și queue din STL

stl.cpp
#include <iostream>#include <stack>#include <queue>using namespace std;int main() {    stack<int> st;    queue<int> q;    for (int x = 1; x <= 3; x++) {        st.push(x);        q.push(x);    }    cout << st.top() << ' ';    cout << q.front() << '\n';    st.pop();    q.pop();    cout << st.size() << ' ';    cout << q.front();    return 0;}

Ce apare pe ecran

3 1
2 2

Biblioteca standard le are gata: push adaugă, pop scoate, top și front arată elementul următor. La bac se cere de obicei implementarea cu vector; în proiecte, folosește STL.

Capcană: uiți verificarea de la final

Algoritmul verifică doar închiderile. În „(()” nicio închidere nu e greșită, dar o paranteză rămâne deschisă:

final.cpp
#include <iostream>using namespace std;int main() {    char s[] = "(()";    int vf = 0;    bool ok = true;    for (int k = 0; s[k] != 0; k++)        if (s[k] == '(')            vf++;        else if (vf > 0)            vf--;        else            ok = false;    if (ok)        cout << "DA";    else        cout << "NU";    return 0;}

Ce apare pe ecran

DA

Repară cu if (ok && vf == 0): la final, stiva trebuie să fie goală.

Capcană: coada care „se umple” goală

Fiecare element intră și iese imediat, deci coada e mereu goală. Totuși ultim doar crește și ajunge la capătul vectorului:

plina.cpp
#include <iostream>using namespace std;int main() {    int c[6], prim = 1, ultim = 0;    for (int x = 1; x <= 6; x++) {        if (ultim == 5) {            cout << "plină: " << x;            return 0;        }        c[++ultim] = x;        prim++;    }    return 0;}

Ce apare pe ecran

plină: 6

Locurile de la început, eliberate de prim++, nu se mai folosesc. Repară cu o coadă circulară, în care indicii trec de la capăt înapoi la 1, sau cu queue din STL.

Pasul 4 din 5

Verifică-te

Cinci întrebări noi. După fiecare răspuns vezi imediat de ce e așa.

1 din 5 · Prezice ieșirea

Ce afișează programul?

stiva.cpp
#include <iostream>using namespace std;int main() {    int st[10], vf = 0;    for (int x = 1; x <= 3; x++)        st[++vf] = x;    vf--;    st[++vf] = 4;    cout << st[vf] << st[vf - 1];    return 0;}

Răspuns: „42”.

Stiva e 1, 2, 3. Scoaterea lasă 1, 2, apoi intră 4: 1, 2, 4. Vârful e 4, iar sub el e 2.

2 din 5 · Alege varianta

Documentele trimise la o imprimantă se tipăresc în ordinea în care au sosit. Ce structură folosești?

Răspuns: coadă.

Primul document trimis trebuie tipărit primul: FIFO. O stivă l-ar tipări întâi pe ultimul sosit.

3 din 5 · Prezice ieșirea

Ce afișează programul?

coada.cpp
#include <iostream>using namespace std;int main() {    int c[10], prim = 1, ultim = 0;    for (int x = 1; x <= 3; x++)        c[++ultim] = x;    prim++;    c[++ultim] = 4;    cout << c[prim] << c[ultim];    return 0;}

Răspuns: „24”.

Coada e 1, 2, 3. prim++ îl scoate pe 1, primul intrat. Apoi 4 intră la coadă. Primul e acum 2, ultimul 4.

4 din 5 · Alege varianta

Ce răspunde programul complet pentru „{(})”?

Răspuns: NU.

După „{(” vârful stivei e „(”. Vine „}”, care ar trebui să închidă „{”, nu „(”. Contează și ordinea închiderilor, nu doar numărul lor.

5 din 5 · Alege varianta

Într-o stivă cu vector, cum arată operația push a lui x, dacă elementele stau de la poziția 1?

Răspuns: st[++vf] = x;

++vf crește vârful înainte de scriere, așa că primul element ajunge pe poziția 1. vf++ ar scrie pe poziția 0 și ar lăsa vf cu unu după vârf.

Pasul 5 din 5

Ce ai învățat

Programul complet

Trei feluri de paranteze, deci stiva ține caracterele deschise. strchr verifică dacă un caracter e unul dintre „([{”, iar pereche spune ce trebuie să fie în vârf.

paranteze.cpp
#include <iostream>#include <cstring>using namespace std;char pereche(char c) {    if (c == ')') return '(';    if (c == ']') return '[';    return '{';}int main() {    char s[101], st[101];    int vf = 0;    bool ok = true;    cin >> s;    int k = 0;    while (s[k] != 0 && ok) {        char c = s[k++];        if (strchr("([{", c))            st[++vf] = c;        else if (vf == 0)            ok = false;        else {            char t = st[vf--];            ok = t == pereche(c);        }    }    if (ok && vf == 0)        cout << "DA";    else        cout << "NU";    return 0;}

Cu {[()()]}

DA

Cu ([)]

NU

Continuă cu