Stiva
Cerință
Se dă un șir de N numere întregi asupra căruia se fac următoarele operații: eliminarea ultimului element din șir (pop) și adăugarea unui element X la finalul șirului (push X). Să se afișeze șirul după aplicarea operațiilor date.
Structura de date introdusă mai sus, asupra căreia se pot executa doar operații de tip push X și pop, se numește stivă. Stiva este o structură de date des utilizată în informatică și se spune că are tipul last in, first out datorită felului în care accesăm date salvate în ea. Aceasta este folosită atât la implementarea recursivității în limbajele de programare, cât și ca structură auxiliară la traversarea unor structuri de date mai complicate, cum sunt arborii și grafurile.
Date de intrare
Se citește numărul natural N, reprezentând numărul de elemente ale șirului inițial și N numere întregi, reprezentând elementele șirului. Apoi se citesc M valori de k unde k poate avea valoarea 1 sau 2. Dacă k are valoarea 1, se va citi imediat după acesta un număr întreg X şi se va efectua operaţia push X. Dacă kare valoarea 2 se va efectua operaţia pop.
Date de ieșire
Se va afișa pe ecran șirul de numere obținut în urma aplicării operațiilor date asupra șirului inițial. Pe prima linie se va afișa numărul T, reprezentând numărul de elemente ale noului șir, iar pe cea de a doua linie se vor afișa cele T elementele ale șirului, separate prin spații.
Restricții şi precizări
N și M sunt numere naturale cuprinse în intervalul [1, 10.000].
Fiecare element din șir este cuprins în intervalul [-2.000.000.000, +2.000.000.000].
k va avea întotdeauna valoarea 1 sau 2.
X are valori cuprinse în intervalul [-2.000.000.000, +2.000.000.000].
Nu vor fi operatii de tipul 2 cand stiva e goala.
Exemplu
Date de intrare Date de ieșire
7
5 -4 0 -7 7 7 2
5
2
1 100
2
1 0
1 3 8
5 -4 0 -7 7 7 0 3
Răspunsuri la întrebare
Explicație:
#include <iostream>
#define max 20000000000
#define min -20000000000
using namespace std;
struct NOD
{
int info;
NOD* next;
};
typedef NOD* STIVA;
void push(STIVA &vf, int ninfo)
{
STIVA nou = new (nothrow) NOD;
if (nou == NULL)
{
cout << "spatiul nu este suficient" << endl;
exit(1);
}
nou->info = ninfo;
nou->next = vf;
vf = nou;
}
void pop(STIVA &vf)
{
STIVA p;
if (vf == NULL)
cout << "stiva este vida" << endl;
p = vf;
vf = vf->next;
delete p;
}
STIVA creare_stiva()
{
STIVA vf = NULL;
int N;
do
{
cout << "numarul de elemente este ";
cin >> N;
} while (N < 0 || N>10000);
int *sir = new (nothrow) int[N];
if (sir == NULL)
{
cout << "eroare la alocare" << endl;
exit(1);
}
for (int i = 0; i < N; i++)
{
cout << "componenta " << i + 1 << " este ";
cin >> *(sir + i);
push(vf, *(sir + i));
}
int M;
do
{
cout << "numarul de valori este ";
cin >> M;
} while (M < 0 || M>10000);
int k, X;
for (int i = 0; i < M; i++)
{
cout << "k[" << i + 1 << "] este ";
cin >> k;
if (k == 1)
{
do
{
cout << "X este ";
cin >> X;
} while (X<min || X>max);
push(vf, X);
}
else
if (k == 2 && vf != NULL)
pop(vf);
}
return vf;
}
int main()
{
STIVA vf1 = creare_stiva();
int T = 0;
int info;
STIVA vf2 = NULL;
while (vf1 != NULL)
{
info = vf1->info;
push(vf2, info);
T++;
vf1 = vf1->next;
}
cout << "stiva are " << T << " componente";
cout << endl;
while (vf2 != NULL)
{
cout << vf2->info << " ";
vf2 = vf2->next;
}
system("pause");
return 0;
}