Clasa a XI-a · Alocare dinamică: liste, stive, coziRead in English
Stiva implementată cu un vector în C++
În engleză: Stack implemented with an array
Ideea
Stiva este o structură de tip LIFO (ultimul intrat, primul ieșit): se adaugă și se scoate doar în vârf. Cu un vector st și un indice vf (numărul de elemente): push pune elementul pe poziția vf + 1, pop scade vf, iar vârful este st[vf]. Programul execută q operații: „push x”, „pop” și „top” (afișează vârful). Dacă stiva e vidă la pop sau top, se afișează „Stiva vida”.
Descrierea în engleză
The stack is a LIFO structure (last in, first out): elements are added and removed only at the top. With an array st and an index vf (the number of elements): push places the element at position vf + 1, pop decreases vf, and the top is st[vf]. The program runs q operations: 'push x', 'pop' and 'top' (prints the top). If the stack is empty on pop or top, 'Stiva vida' (empty stack) is printed.
- Complexitate
- O(1) pentru fiecare operație
- Clasa
- Clasa a XI-a (Grade 11)
Exemple
Intrare
7 push 3 push 8 top pop top pop pop
Ieșire așteptată
8 3 Stiva vida
Codul C++
Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.
/*
* Titlu: Stiva implementată cu un vector
* Clasa: 11
* Capitol: Alocare dinamică: liste, stive, cozi
* Descriere: Stiva este o structură de tip LIFO (ultimul intrat, primul ieșit): se adaugă
* și se scoate doar în vârf. Cu un vector st și un indice vf (numărul de
* elemente): push pune elementul pe poziția vf + 1, pop scade vf, iar vârful
* este st[vf]. Programul execută q operații: „push x”, „pop” și „top” (afișează
* vârful). Dacă stiva e vidă la pop sau top, se afișează „Stiva vida”.
* Complexitate: O(1) pentru fiecare operație
*
* Exemplu
* Intrare:
* 7
* push 3
* push 8
* top
* pop
* top
* pop
* pop
* Ieșire:
* 8
* 3
* Stiva vida
*/
#include <iostream>
#include <string>
using namespace std;
int st[10005], vf = 0;
int main()
{
int q;
cin >> q;
for (int i = 1; i <= q; i++)
{
string op;
cin >> op;
if (op == "push")
{
int x;
cin >> x;
st[++vf] = x;
}
else if (vf == 0)
{
cout << "Stiva vida\n";
}
else if (op == "pop")
{
vf--;
}
else
{
cout << st[vf] << '\n';
}
}
return 0;
}
Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.