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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import java.util.Stack; public class MinStack<T extends Comparable> { private Stack<T> stack = new Stack<T>(); public boolean isEmpty() { return stack.isEmpty(); } public T push(T item) { return stack.push(item); } public T pop() { return stack.pop(); } public T peek() { return stack.peek(); } public T min() { if (stack.isEmpty()) { return null; } Stack<T> tmp = new Stack<T>(); T item = stack.pop(); T min = item; tmp.push(item); while (!stack.isEmpty()) { item = stack.pop(); tmp.push(item); if (min.compareTo(item) > 0) { min = item; } } while (!tmp.isEmpty()) { stack.push(tmp.pop()); } return min; } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public static void main(String[] args) { MinStack<Integer> minStack = new MinStack<Integer>(); Random random = new Random(); for (int i = 0; i < 100; i++) { if (random.nextBoolean() || minStack.isEmpty()) { minStack.push(random.nextInt(100) + 1); System.out.println("PUSH\t" + minStack.peek() + "\tMIN: " + minStack.min()); } else { System.out.println("POP \t" + minStack.pop() + "\tMIN: " + minStack.min()); } } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
PUSH 58 MIN: 58 POP 58 MIN: null PUSH 23 MIN: 23 POP 23 MIN: null PUSH 81 MIN: 81 PUSH 77 MIN: 77 POP 77 MIN: 81 POP 81 MIN: null PUSH 60 MIN: 60 POP 60 MIN: null PUSH 74 MIN: 74 POP 74 MIN: null PUSH 99 MIN: 99 PUSH 74 MIN: 74 POP 74 MIN: 99 PUSH 17 MIN: 17 POP 17 MIN: 99 PUSH 57 MIN: 57 PUSH 97 MIN: 57 POP 97 MIN: 57 PUSH 39 MIN: 39 POP 39 MIN: 57 PUSH 60 MIN: 57 PUSH 70 MIN: 57 POP 70 MIN: 57 PUSH 42 MIN: 42 POP 42 MIN: 57 PUSH 50 MIN: 50 POP 50 MIN: 57 PUSH 99 MIN: 57 PUSH 4 MIN: 4 POP 4 MIN: 57 PUSH 66 MIN: 57 POP 66 MIN: 57 PUSH 56 MIN: 56 POP 56 MIN: 57 POP 99 MIN: 57 POP 60 MIN: 57 POP 57 MIN: 99 PUSH 100 MIN: 99 PUSH 82 MIN: 82 PUSH 41 MIN: 41 PUSH 31 MIN: 31 PUSH 26 MIN: 26 POP 26 MIN: 31 PUSH 92 MIN: 31 PUSH 18 MIN: 18 PUSH 46 MIN: 18 PUSH 44 MIN: 18 PUSH 65 MIN: 18 POP 65 MIN: 18 PUSH 24 MIN: 18 PUSH 4 MIN: 4 PUSH 59 MIN: 4 PUSH 42 MIN: 4 POP 42 MIN: 4 POP 59 MIN: 4 PUSH 52 MIN: 4 PUSH 53 MIN: 4 POP 53 MIN: 4 PUSH 65 MIN: 4 POP 65 MIN: 4 PUSH 40 MIN: 4 POP 40 MIN: 4 PUSH 66 MIN: 4 PUSH 9 MIN: 4 POP 9 MIN: 4 POP 66 MIN: 4 POP 52 MIN: 4 POP 4 MIN: 18 PUSH 51 MIN: 18 PUSH 91 MIN: 18 PUSH 84 MIN: 18 POP 84 MIN: 18 POP 91 MIN: 18 PUSH 86 MIN: 18 POP 86 MIN: 18 PUSH 19 MIN: 18 PUSH 74 MIN: 18 PUSH 57 MIN: 18 POP 57 MIN: 18 PUSH 6 MIN: 6 PUSH 73 MIN: 6 PUSH 62 MIN: 6 PUSH 74 MIN: 6 POP 74 MIN: 6 PUSH 85 MIN: 6 PUSH 17 MIN: 6 PUSH 73 MIN: 6 POP 73 MIN: 6 PUSH 18 MIN: 6 POP 18 MIN: 6 PUSH 90 MIN: 6 PUSH 99 MIN: 6 PUSH 29 MIN: 6 POP 29 MIN: 6 POP 99 MIN: 6 POP 90 MIN: 6 PUSH 19 MIN: 6 POP 19 MIN: 6 |
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ă:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
import java.util.Stack; public class MinStack<T extends Comparable> { private Stack<T> stack = new Stack<T>(); private Stack<T> min = new Stack<T>(); public boolean isEmpty() { return stack.isEmpty(); } public T push(T item) { if (min.isEmpty() || min.peek().compareTo(item) > 0) { min.push(item); } else { min.push(min.peek()); } return stack.push(item); } public T pop() { min.pop(); return stack.pop(); } public T peek() { return stack.peek(); } public T min() { if (!min.isEmpty()) { return min.peek(); } else { return null; } } } |
Putem folosi același cod pentru a testa noua implementare.
