Śledzenie Maksimum Stosu

Zadanie

Napisz program, który pozwoli odczytać w dowolnym momencie maksymalną wartość ze stosu. Zakładamy, że maksimum jest sprawdzane po każdym położeniu / zdjęciu elementu ze stos, a więc operacja musi być optymalnie zaimplementowana.

Przykład

Oto przykładowe operacje na stosie:

Rozwiązanie

Najprotszy sposób, który pozwoli na uzyskanie maksimum stosu polega na napisaniu funkcji, która przejrzy wszystkie jego elementy, a następnie zwróci wynik. Jednak taka metoda nie jest optymalna, ponieważ wymaga bardzo dużej ilości operacji przenoszenia elementów oraz porównywania. Optymalny sposób polega na utworzeniu bufora do którego będzie zapisywane aktualne maksimum, którego zostanie wybrane jako większa wartość z wierzchu bufora oraz wstawianej wartości. Podczas zdejmowania elementu należy zdjąć wartość z stosu głównego oraz maksimum.

Tego typu metoda pozwala na odczytanie maksimum stosu w stałym czasie O(1), ale wymaga drugie tyle pamięci (dla każdego wstawianej wartości musimy zapamiętać jeszcze jedną wartość tj. maksimum).

Implementacja

Implementacja polega na naapisaniu klasy MaxStos, która pozwoli na dozwolone operacje stosu. Poniższy kod nie uwzględnia obsługi wszystkich błędów jakie mogą wystąpić.

Część prywatna

Użytkownik korzystając z klasy MaxStos nie powinien mieć dostepu, ani do stosu głównego, ani bufora maksimum, ponieważ niesynchronizowana operacja pomiędzy stosami doprowadzi do niepoprawnego działania klasy.

1. template<typename T>
2. class MaxStos
3. {
4. private:
5.   stack<T> glowny;
6.   stack<T> maksimum;

W celu zachowania synchronizacja pomiędzy stosami należy zdefiniować własne metody do sprawdzania wierzchu stosu Podejrzyj(), dodawania elementu Dodaj(), zdejmowania elementu ze stosu Zdejmij oraz Maksimum(), aby sprawdzić aktualnie największą wartość położoną na stosie.

1. public:
2.   void Poloz(T wartosc) {
3.     glowny.push(wartosc);
4.     if (maksimum.size() == 0) {
5.       maksimum.push(wartosc);
6.     } else {
7.       maksimum.push(max(wartosc, Maksimum()));
8.     }
9.   }
11.   T Podejrzyj() {
12.     return glowny.top();
13.   }
15.   T Zdejmij() {
16.     T wartosc = Podejrzyj();
17.     glowny.pop();
18.     maksimum.pop();
19.     return wartosc;
20.   }
22.   T Maksimum() {
23.     if (maksimum.size() == 0)
24.       throw exception("Pusty stos!");
25.     return maksimum.top();
26.   }
27. };

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programu, który dodaje na stos n elementów, ale dwa ostatnie ustawia na 0 i 1, a następnie zdejmuje wszystkie elementy.

1. int main() {
2.   MaxStos<int> stos;
3.   int n = 5;
4.   for (int i = 0; i < n; i++) {
5.     int a = i % (n - 2);
6.     stos.Poloz(a);
7.     cout << "Polozono: " << a;
8.     cout << ", maks.: " << stos.Maksimum() << endl;
9.   }
10.   for (int i = 0; i < n; i++) {
11.     try
12.     {
13.       int a = stos.Zdejmij();
14.       cout << "Zdjeto: " << a << ", maks.: ";
15.       cout << stos.Maksimum() << endl;
16.     }
17.     catch (const std::exception& ex)
18.     {
19.       cout << ex.what() << endl;
20.     }
21.   }
22.   system("pause");
23.   return 0;
24. }

• Kod źródłowy Implementacja