10 2018 Lectia15
Structuri de date elementare
Stivele şi cozile sunt mulţimi dinamice în care elementul care este eliminat din mulţime de către operaţia Şterge este prespecificat. Într-o stivă, elementul şters din mulţime este elementul cel mai recent inserat: stiva implementează principiul ultimul sosit, primul servit (last-in, first-out) sau LIFO. Similar, într-o coadă, elementul şters este întotdeauna cel care a stat în mulţime cel mai mult (primul introdus): coada implementează principiul primul sosit, primul servit (first-in, first-out) sau FIFO. Există mai multe modalităţi eficiente de a implementa stivele şi cozile cu ajutorul calculatorului. Aici vom arăta cum se pot folosi tablourile simple pentru a implementa fiecare dintre aceste structuri.
Stive
Operaţia Inserează asupra stivelor este deseori denumită Pune-În-Stivă ( Push ). Operaţia Şterge, care nu cere nici un argument, este deseori numită Scoate-Din-Stivă ( Pop ). Aceste nume sunt aluzii la stivele fizice, ca de exemplu un vraf de farfurii. Ordinea în care sunt luate farfuriile din vraf este ordinea inversă în care au fost introduse în vraf, deoarece doar ultima farfurie este accesibilă. O stivă cu cel mult n elemente poate fi implementată printr-un tablou st[0..n-1]. Tabloul are un atribut vf care este indicele noii locatii in care se va insera un nou element. Stiva constă din elementele st[0..vf-1], unde st[0] este elementul de la baza stivei, iar st[vf-1] este elementul din vârful stivei, ultimul element al stivei. Când vf = 0, stiva nu conţine nici un element şi deci este vidă. Se poate testa dacă stiva este vidă prin operaţia de interogare Stivă-Vidă( empty ) . Dacă se încearcă extragerea (se apelează operaţia Scoate-Din-Stivă) unui element dintr-o stivă vidă, spunem că stiva are depăşire inferioară, care în mod normal este o eroare. Dacă vf depăşeşte valoarea n, stiva are depăşire superioară. (În implementarea noastră nu ne vom pune problema depăşirii stivei.) Fiecare dintre operaţiile stivei pot fi implementate prin doar câteva linii de cod.
int st[100], int vf;
bool Stiva_Vida( ){
if ( vf == 0 )
return true;
return false;
}
void Push ( int x ){
st[vf++] = x;
}
int Pop ( ){
if ( Stiva_Vida () ){
cout << "nu avem elem in stiva, depasire inferioara";
return -1;
}
vf --;
return st[vf];
}
Fiecare dintre cele trei operaţii asupra stivelor necesită un timp O(1).Aplicatii cu Stive
stiva
Să se scrie un program care gestionează o stivă de numere întregi. Inițial stiva este vidă. Programul va citi de la tastatură o listă de operații, care pot fi:
push X – adaugă valoarea întreagă X pe stivă; pop – elimină elementul din vârful stivei; top – afișează elementul din vârful stivei. Programul va realiza asupra stivei operațiile citite, în ordine. Afișările se fac pe ecran, câte o valoare pe linie.
#include <iostream>
#include<string.h>
using namespace std;
int main(){
int n = 0, nr, x;
int st[1001];
cin >> nr;
char op[20];
for( int i = 0; i < nr; i++ ){
cin >> op;
if( strcmp( op,"push" ) == 0 ){
cin >> x;
st[n++] = x;
}
else if( strcmp( op, "pop" ) == 0 )
if ( n > 0 )
n --;
else // if(strcmp(op,"top") == 0 )
if ( n > 0 )
cout << st[n-1] << "\n";
}
return 0;
}Scris cu functii :
//VARIANTA 2
#include <iostream>
using namespace std;
const int kMax = 1000;
int stk[kMax + 1];
int k = 0;
// Verifica daca stiva este vida
bool empty() {
if (k == 0) {
return true;
} else {
return false;
}
}
// Adauga element in stiva
void push(int x) {
stk[k] = x;
k++;
}
// Afiseaza varful stivei
void top() {
if (!empty()) {
cout << stk[k - 1] << '\n';
}
}
// Sterge varful stivei
void pop() {
if (!empty()) {
k--;
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
char s[10];
// citeste un cuvant pana la primul spatiu (sau tab sau enter)
cin >> s;
if (s[0] == 't') {
// operatia "top"
top();
} else if (s[1] == 'o') {
// operatia "pop"
pop();
} else {
// operatia "push x"
int x;
cin >> x;
push(x);
}
}
return 0;
}//VARIANTA 2
#include <iostream>
#include<string.h>
using namespace std;
void push ( int st[], int &n, int x ){ // n e nr de elem din stiva
st[n++] = x;
}
void pop( int st[], int &n ){
if ( n > 0 ) // daca avem ce sa scoatem
n --;
}
void top( int st[], int n ){
if ( n > 0 )
cout << st[n-1] << "\n";
}
int main(){
//ifstream fin("date.in");
int n = 0, nr, x;
int st[1001];
cin >> nr;
char op[20];
for( int i = 0; i < nr; i++ ){
cin >> op;
if( strcmp( op,"push") == 0 ){
cin >> x;
push( st, n, x );
}
else if( strcmp( op, "pop" ) == 0 )
pop( st, n );
else // if(strcmp(op,"top") == 0 )
top( st, n );
}
return 0;
}// CU STL - STACK
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack <int> s;
int c , x;
string op;
cin >> c;
for( int i = 1 ; i <= c ; i++ ) {
cin >> op;
if( op == "push") {
cin >> x;
s.push(x);
}
else if( op == "top" )
cout << s.top() << '\n';
else
s.pop();
}
}paranteze1
Se dau n șiruri de paranteze rotunde. Să se stabilească, despre fiecare șir, dacă este corect parantezat – adică dacă parantezele se închid corect. Un șir de paranteze S rotunde este corect parantezat dacă:
- S este șirul vid, sau
- S = (T) și T este corect parantezat, sau
- S = AB, iar A și B sunt corect parantezate.
#include <fstream>
using namespace std;
ifstream fin( "paranteze1.in" );
ofstream fout ( "paranteze1.out" );
int main(){
int n;
char st[255], c;
fin >> n;
fin.get( c );
for ( int i = 0; i < n; i ++ ) {
int k = 0;
c = fin.get( );
while ( c != '\n' && c!= EOF ) {
if ( k && st[k-1] == '(' && c == ')' )
k --;
else {
st[k++] = c;
}
c = fin.get( );
}
fout << ( k == 0 ) << '\n';
}
return 0;
}cuburi2
Gigel are un set de n cuburi. Fiecare cub este marcat cu un număr natural, de la 1 la n și i se cunoaște lungimea laturii – număr natural. Cu o parte dintre aceste cuburi Gigel va construi o stivă, astfel:
fiecare cub se analizează o singură dată, în ordinea numerelor marcate; dacă stiva nu conține niciun cub, cubul curent devine baza stivei dacă cubul curent are latura mai mică sau egală cu cubul din vârful stive, se adaugă pe stivă; dacă cubul curent are latura mai mare decât cubul din vârful stivei, se vor înlătura de pe stivă cuburi (eventual toate) până când cubul curent are latura mai mică sau egală cu cubul din vârful stivei. Să se afișeze numerele de pe cuburile existente la final în stivă, de la bază spre vârf.
#include <iostream>
using namespace std;
int st[1000], ind[1000];
int main(){
int n, a;
cin >> n;
int k = 0; // cate elem am in stiva
for( int i = 0; i < n; i++ ) {
cin >> a;
while( k > 0 && st[k-1] < a ) // st nu e vida ultima val din stiva => st[k-1]
k--;
st[k] = a;
ind[k] = i;
k++;
}
cout << k << '\n';
for( int i = 0; i < k; i++ )
cout << ind[i] + 1 << " ";
return 0;
}books
#include <iostream>
using namespace std;
int v[200000];
int f[200001];
int main (){
int n, i, nr;
cin >> n;
for ( i = 0; i < n; i++ )
cin >> v[i];
int k = -1;
for ( i = 0; i < n; i++ ) {
cin >> nr;
if ( f[nr] ) // dc nr a fost deja pus in ghiozdan
cout << "0 "; // mut 0 carti
else { // inaintez in stiva pana gasesc cartea nr
int cnt = 0;
do {
k ++;
f[v[k]] = 1; // marchez ce carti am pus deja in ghiozdan in verctor de frecventa
cnt ++;
} while ( v[k] != nr );
cout << cnt << " ";
}
}
return 0;
}paranteze1
Se dau n șiruri de paranteze rotunde. Să se stabilească, despre fiecare șir, dacă este corect parantezat.
#include <fstream>
using namespace std;
ifstream fin( "paranteze1.in" );
ofstream fout ( "paranteze1.out" );
int main(){
int n;
char st[255], c;
fin >> n;
fin.get( c );
for ( int i =0; i < n; i ++ ){
int k = 0;
c = fin.get( );
while ( c != '\n' && c!= EOF ){
if ( k && st[k-1] == '(' && c == ')' )
k --;
else {
st[k++] = c;
}
c = fin.get( );
}
fout << ( k == 0 ) << '\n';
}
return 0;
}paranteze2
Atentie !!! Citirea cu fin.get(c) nu merge. Nu se citeste EOF_ul in c, in schimb functia returneaza EOF.
#include <fstream>
using namespace std;
ifstream fin( "paranteze2.in" );
ofstream fout ( "paranteze2.out" );
int main(){
char st[255], c;
int k = 0;
int vmax = 0;
c = fin.get( );
while ( c != '\n' && c!= EOF ){
if ( c == ')' )
k --;
else {
st[k++] = c;
if ( vmax < k )
vmax = k;
}
c = fin.get( );
}
fout << vmax << '\n';
return 0;
}// CU STL -STACK
#include <fstream>
#include <stack>
using namespace std;
bool match(char a, char b) {
if (a == '(' && b == ')')
return true;
if (a == '[' && b == ']')
return true;
return false;
}
int main() {
ifstream in("paranteze3.in");
ofstream out("paranteze3.out");
int t;
bool add;
string s;
stack<char> st;
in >> t;
while (t--) {
in >> s;
while (!st.empty())
st.pop();
for (auto c : s) {
add = true;
while (!st.empty() && match(st.top(), c)) {
add = false;
st.pop();
if (!st.empty())
c = st.top();
}
if (add)
st.push(c);
}
if (st.empty())
out << "1\n";
else
out << "0\n";
}
in.close();
out.close();
return 0;
}paranteze3
Se dau n șiruri de paranteze rotunde sau pătrate. Să se stabilească, despre fiecare șir, dacă este corect parantezat.
#include <fstream>
using namespace std;
ifstream fin( "paranteze3.in" );
ofstream fout ( "paranteze3.out" );
int main(){
int n;
char st[255], c;
fin >> n;
fin.get( c );
for ( int i = 0; i < n; i ++ ) {
int k = 0;
c = fin.get();
while ( c != '\n' && c!= EOF ) {
if ( k && ( st[k-1] == '(' && c == ')' || st[k-1] == '[' && c == ']'))
k --;
else {
st[k++] = c;
}
c = fin.get();
}
fout << ( k == 0 ) << '\n';
}
return 0;
}books
Cozi
Vom numi Pune-În-Coadă ( Push ) operaţia de inserare aplicată asupra unei cozi, iar operaţia de stergere o vom numi Scoate-Din-Coadă ( Pop ); asemănător operaţiei Scoate-Din-Stivă aplicată stivei, Scoate-Din-Coadă nu necesită nici un argument. Principiul FIFO, propriu cozii, impune ca aceasta să opereze asemănător cu un rând de oameni ce aşteaptă la un ghişeu. Coada are un cap şi o coadă. Când un element este pus în coadă, ocupă locul de la sfârşitul cozii, ca şi un nou venit ce îşi ia locul la coada rândului. Elementul scos din coadă este întotdeauna cel din capul cozii, asemănător persoanei din capul rândului care a aşteptat cel mai mult. O modalitate de a implementa o coadă având cel mult n − 1 elemente, foloseste un tablou Q[0..n-1]. Coada are un atribut in, capul cozii, care conţine indicele capului ei si un atributul sf, sfarsitul cozii, ce conţine indicele noii locaţii în care se va insera în coadă elementul nou venit. Elementele din coadă se află în locaţiile cap, cap + 1, ..., coada − 1, iar indicii se parcurg circular, în sensul că locaţia 0 urmează imediat după locaţia n-1. Când cap = coada, coada este goală. Iniţial avem in = sf = 0. Când coada este vidă, o încercare de a scoate un element din coadă cauzează o depăşire inferioară în coadă. Când cap = coada + 1, coada este “plină” şi o încercare de a pune în coadă cauzează o depăşire superioară în coadă. În Pune-În-Coadă şi Scoate-Din-Coadă, verificarea erorilor de depăşire inferioară a fost omisă.
const int NMAX = 100;
int Q[NMAX], in, sf;
void Push ( int x ){
Q[sf] = x;
sf = (sf + 1 ) % NMAX;
}
int Pop () {
int x = Q[in];
in = ( int + 1 ) % NMAX;
return x;
}Exercitii
- Explicaţi cum se pot implementa două stive într-un singur tablou astfel încât nici una dintre stive să nu aibă depăşire superioară, cu excepţia cazului în care numărul total de elemente din ambele stive (împreună) este n. Operaţiile Pune-În-Stivă şi Scoate-Din-Stivă trebuie să funcţioneze într-un timp O(1).
- Rescrieţi Pune-În-Coadă şi Scoate-Din-Coadă pentru a detecta depăşirile unei cozi.
- În timp ce stiva permite inserarea şi ştergerea de elemente doar la un singur capăt, iar coada permite inserarea la un capăt şi ştergerea la celălalt capăt, o coadă completă permite
inserări şi ştergeri la ambele capete. Scrieţi patru proceduri cu timpul de execuţie O(1) pentru inserare de elemente şi ştergere de elemente la ambele capete ale unei cozi complete implementată printr-un tablou.
- Arătaţi cum se poate implementa o coadă prin două stive. Analizaţi timpul de execuţie pentru operaţiile cozii.
- Arătaţi cum se poate implementa o stivă prin două cozi. Analizaţi timpul de execuţie pentru operaţiile stivei.
Tema Stiva
Probleme Pbinfo: https://www.pbinfo.ro/probleme/870/depou ecuatie1 , Stiva , Cuburi2 , Depou , Paranteze1 , Paranteze4 , Paranteze3 , Paranteze2 , minlex , eval_exp , eval_exp2
Probleme Varena
- bile2 dată la concursul .campion 2005
- turn dată la ONI 2007 clasa a 6a
- paranteze1 dată ca temă la cercul IQ Academy 2018 clasa a 6a
- swap dată la ONI 2013 baraj gimnaziu
Probleme Infoarena
GREA
Bibliografie
- Introducere in algoritmi, Thomas Cormen
Tema Rezolvari
Probleme Varena
- bile3 dată la concursul .campion 2005
#include <stdio.h>
#include <stdlib.h>
int in[2000], st[2000];
char out[4000];
int main(){
FILE *fin = fopen( "bile2.in","r" );
FILE *fout = fopen( "bile2.out","w" );
int i, n, b, kin, kout , k;
fscanf(fin,"%d",&n);
for(i=0;i<n;i++)
fscanf(fin,"%d",&in[i]);
kin = 0; //nivel in (zona A)
k = 0; //nivel stiva (zona B)
kout = 0; //nivel sol ( in sol voi tine sirul de Intrari/Iesiri )
//citesc pe rand bilele care trebuie sa ajunga in out
//pentru fiecare bila verific, apas I cata vreme nu am in varful stifei b
//daca b a ajuns in varful stivei, apas out,
//daca nu am reusit sa scot bila b, nu are sens sa mai incerc scoarerea celorlalte bile
//daca am reusit sa scot o bila, atunci valoarea ei, a ramas pe nibelul k al stivei
b = 0; // pentru ca b == st[k] sa fie adevarata la primul pas
for( i = 0; i < n && b == st[k]; i++ ){
fscanf( fin,"%d", &b );
//cat timp mai am bile in in si nu am in varvul stivei val b
//gasit = 0;
while( ( kin < n && ( k > 0 && st[k-1] != b ) || k == 0 ) ){
out[kout++] = 'I'; //apas I
st[k++] = in[kin]; //mut bila din in in stiva
kin ++; //avensez in vectorul in
}
if( k > 0 && st[k-1] == b ){ //daca stiva nu e vida si in varv am bila potrivita
out[kout++] = 'O'; //apas o
k --;
//gasit = 1; //scad nivelul in stiva
}
}
if( kout == 2*n ) //daca in solutie am 2*n mutari ( n in-uri si n out- uri)
for( i=0; i < kout; i++ )
fputc( out[i], fout );
else
fprintf(fout,"imposibil");
fclose( fin );
fclose( fout );
return 0;
}- turn dată la ONI 2007 clasa a 6a
- paranteze1 dată ca temă la cercul IQ Academy 2018 clasa a 6a
#include <fstream>
using namespace std;
ifstream fin( "paranteze1.in" );
ofstream fout ( "paranteze1.out" );
const int NMAX = 1000000;
int main(){
int n;
char st[NMAX], c;
int k = 0; // nivelul in stiva
int kmax = 0; // gradul maxim de imbricare
c = fin.get();
while ( c != '\n' ) {
if ( k && ( st[k-1] == '(' && c == ')' || st[k-1] == '{' && c == '}'))
k --;
else {
st[k++] = c;
if ( k > kmax )
kmax = k;
}
c = fin.get();
}
if ( k )
fout << -1;
else
fout << kmax;
return 0;
}swap dată la ONI 2013 baraj gimnaziu
Pentru calcularea costului parantezarii, vom retine o stiva cu pozitiile parantezelor. Orice paranteza inchisa va inchide ultima paranteza deschisa, pentru care s-a memorat pe stiva pozitia sa i ncadrul vectorului. Pentru a optimiza parantezarea, vom incerca sa inchidem o paranteza mai devreme, daca e posibil. Orice swap efectuam va imbunatati costul doar cu 2.
#include <fstream>
using namespace std;
ifstream fin( "swap.in" );
ofstream fout ( "swap.out" );
const int NMAX = 90000;
int main(){
int n;
int st[NMAX/2];
char c1, c2;
int cost = 0; // costul imbricarii
int nrswap = 0;
fin >> n;
c1 = fin.get();
int k = 0; // nivelul in stiva
for ( int i = 0; i < n; i ++ ) {
c2 = fin.get();
if ( c2 == '(' )
st[k ++] = i;
else {
k -- ;
cost += ( i - st[k] );
if ( k > 0 && c1 == '(' ) // daca as fi putut inchide paranteza mai devreme
nrswap ++;
}
c1 = c2;
}
fout << cost << '\n';
if ( nrswap == 0 )
fout << -1 << '\n';
else
fout << cost - 2 << '\n'; // orice swap reduce costul cu 2
fout << nrswap;
return 0;
}
