|
|
| (One intermediate revision by the same user not shown) |
| Line 1: |
Line 1: |
| = 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) prescurtat 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.
| |
|
| |
|
| <syntaxhighlight>
| |
| 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).
| |
|
| |
| </syntaxhighlight>
| |
|
| |
| == Aplicatii cu Stive ==
| |
| ===[https://www.pbinfo.ro/probleme/875/stiva stiva] ===
| |
| <syntaxhighlight>
| |
| #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;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| ===[https://www.pbinfo.ro/probleme/848/paranteze1 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.
| |
|
| |
| <syntaxhighlight>
| |
| #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;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| == 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ă.
| |
| <syntaxhighlight>
| |
| 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;
| |
| }
| |
| </syntaxhighlight>
| |
| == 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 din runda:
| |
| ecuatie1 , Stiva , Cuburi2 , Depou , Paranteze1 , Paranteze4 , Paranteze3 , Paranteze2 , minlex , eval_exp , eval_exp2
| |
|
| |
| Probleme Varena
| |
| * [http://varena.ro/problema/bile2 bile2] dată la concursul .campion 2005
| |
| * [http://varena.ro/problema/turn turn] dată la ONI 2007 clasa a 6<sup>a</sup>
| |
| * [http://varena.ro/problema/paranteze1 paranteze1] dată ca temă la cercul IQ Academy 2018 clasa a 6<sup>a</sup>
| |
| * [http://varena.ro/problema/swap swap] dată la ONI 2013 baraj gimnaziu
| |
|
| |
| Probleme Infoarena
| |
| * [http://infoarena.ro/problema/editor editor]
| |
| * [http://infoarena.ro/problema/trompeta trompeta]
| |
| GREA
| |
| * [http://infoarena.ro/problema/identice identice]
| |
|
| |
| = Bibliografie =
| |
| * Introducere in algoritmi, Thomas Cormen
| |
