Stivă cu minim

Vom crea o stivă mai specială. Pe lângă operațiile clasice, stiva noastră va fi capabilă și să precizeze care este valoarea minimă a elementelor din stivă. Cum facem?

Așadar, stiva noastră ne va permite să efectuăm următoarele operații:

  • verificarea faptului dacă stiva este vidă (isEmpty)
  • adăugarea unui element (push)
  • eliminarea unui element (pop)
  • obținerea valorii elementului din vârful stivei (peek)
  • obținerea valorii minime a elementelor din stivă (min)

Pentru ultima operație vom returna o valoare specială dacă stiva este vidă.

Presupunem că avem la dispoziție o implementare a unei stive obișnuite. În cadrul acestui articol vom folosi limbajul Java și vom utiliza clasa Stack.

Spre deosebire de stiva "clasică", a noastră trebuie să conțină elemente comparabile pentru a putea avea un minim. Pentru primele operații nu avem nicio problemă, dar pentru ultima e puțin mai dificil.

Am putea, de exemplu, să extragem toate elementele stivei, să determinăm minimul și apoi să le punem înapoi în stivă. Am avea nevoie de o stivă ajutătoare pentru a păstra elementele extrase.

O primă implementare ar putea fi:

Putem scrie și o mică secvență care să verifice dacă stiva noastră funcționează corect. Vom genera aleator 100 de operații, fiecare fiind o adăugare sau o eliminare. Vom adăuga numere aleatoare cuprinse între 1 și 100. După fiecare operație vom afișa numărul extras sau adăugat, precum și valoarea minimului. Codul pentru testare ar putea fi următorul:

Am putea înlocui liniile 7 și 8 cu o construcție mai scurtă care folosește doar push, dar atunci testul nu mai folosește și metoda peek. De data aceasta nu este foarte important fiindcă implementarea e simplă, dar de obicei dorim să testăm cât mai multe dintre metodele implementate.

Dacă rulăm testul, obținem ceva de genul:

Totuși, operațiile cu stive se efectuează în timp constant. Pentru operația pe care am adăugat-o parcurgem întreaga stivă (de două ori chiar), deci timpul devine liniar. Putem obține timp constant și pentru această operație?

Dacă ne uităm la rezultatele testului, observăm că minimul se actualizează fie dacă introducem o valoare mai mică decât minimul anterior, fie dacă extragem minimul. În alte situații, minimul rămâne același.

Am putea crea o stivă cu minimele acestea. De fiecare dată când adăugăm un element în stiva "principală", verificăm dacă acesta este mai mic decât minimul curent (vârful stivei de minime) și, dacă este cazul, îl adăugăm în stiva de minime. Dacă nu, în stiva de minime adăugăm din nou minimul curent. Astfel, cele două stive au același număr de elemente, ceea ce ne ajută în momentul efectuării extragerilor (vom extrage din ambele stive). Dacă dorim să determinăm valoare minimă, trebuie doar să furnizăm valoarea din vârful stivei de minime.

Implementarea este foarte simplă:

Putem folosi același cod pentru a testa noua implementare.

 

 

Te-ar putea interesa și: