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

O(1)C++1762 de linii1 exemplu

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

Exemplul 1

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.

stiva-cu-vector.cpp
/*
 * 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.