Maksimalni stek

Napisati generičku klasu max_stek<T> koja implementira stek elemenata tipa T. Pored standardnih operacija steka, klasa treba da podržava i operaciju vraćanja maksimalnog elementa u steku:

void push(const T& element) - dodaje element na vrh steka.
void pop() - uklanja element sa vrha steka.
const T& top() const - vraća element sa vrha steka.
const T& max() const - vraća maksimalni element u steku.

Sve operacije treba da budu složenosti ne veće od $O(1)$.

Ulaz

Sa standardnog ulaza, sve do kraja ulaza, učitavaju se naredbe u formatu:

i x - dodaje element x na vrh steka
r - uklanja element sa vrha steka
t - ispisuje element sa vrha steka
m - ispisuje maksimalni element u steku

Izlaz

Na standardni izlaz ispisati rezultate izvršavanja naredbi m. Ako je stek prazan, ispisati poruku izuzetka na standardni izlaz za greške.

Primer

`stdin`

i 1
i 3
i 2
m
r
i 4
m
r
m
r
m
r
m

`stdout`

`stderr`

Stek je prazan

Rešenje

`main.cpp`

#include <iostream>
#include <stack>

namespace matf
{
	/* Klasa za stek sa maksimalnim elementom */
	template <typename T>
	class max_stek
	{
		public:
			/* Dodaje element na vrh steka */
			void push(const T& x)
			{
				stek.push(x);
				if (max_stek.empty() || x >= max_stek.top()) {
					max_stek.push(x);
				} else {
					max_stek.push(max_stek.top());
				}
			}

			/* Uklanja element sa vrha steka */
			void pop()
			{
				if (stek.empty()) {
					throw std::out_of_range("Stek je prazan");
				}

				stek.pop();
				max_stek.pop();
			}

			const T& top() const
			{
				if (stek.empty()) {
					throw std::out_of_range("Stek je prazan");
				}

				return stek.top();
			}

			/* Vraca maksimalni element u steku */
			const T& max() const
			{
				if (max_stek.empty()) {
					throw std::out_of_range("Stek je prazan");
				}

				return max_stek.top();
			}

		private:
			std::stack<T> stek;
			std::stack<T> max_stek;
	};
};

int main(void)
{
	matf::max_stek<int> ms;

	char op;
	
	while (std::cin >> op) {
		if (op == 'i') {
			int x; std::cin >> x;
			ms.push(x);
		} else if (op == 'r') {
			try {
				ms.pop();
			} catch (const std::out_of_range& e) {
				std::cerr << e.what() << std::endl;
			}
		} else if (op == 't') {
			try {
				int x = ms.top();
				std::cout << x << std::endl;
			} catch (const std::out_of_range& e) {
				std::cerr << e.what() << std::endl;
			}
		} else if (op == 'm') {
			try {
				int x = ms.max();
				std::cout << x << std::endl;
			} catch (const std::out_of_range& e) {
				std::cerr << e.what() << std::endl;
			}
		}
	}

	return 0;
}