Frekvencijski stek

Napisati generičku klasu frekvencijski_stek<T> koja implementira stek elemenata tipa T. Klasa treba da podržava sledeće operacije:

void push(const T& element) - dodaje element na vrh steka.
void pop() - uklanja najčešći element sa vrha steka. Ako postoji više elemenata sa istom maksimalnom frekvencijom, uklanja se onaj koji je najbliži vrhu steka.
const T& top() const - vraća referencu na najčešći element na vrhu steka bez uklanjanja. Ako postoji više elemenata sa istom maksimalnom frekvencijom, vraća se onaj koji je najbliži vrhu steka.

Obe operacije treba da budu složenosti ne veće od $O(\log n)$ ili $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 i ispisuje najčešći element sa vrha steka

Izlaz

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

Primer

`stdin`

i 1
i 2
i 2
i 1 
i 3
i 2
r
r
r
r
r
r
r

`stdout`

`stderr`

Stek je prazan

Rešenje

`main.cpp`

#include <iostream>
#include <map>
#include <stack>
#include <algorithm>

namespace matf
{
	/* Klasa za frekvencijski stek */
	template <typename T>
	class frek_stek
	{
		public:
			/* Dodaje element na vrh steka */
			void push(T& x)
			{
				int f = ++freq[x];
				max_freq = std::max(max_freq, f);
				stek[f].push(x);
			}

			/* Uklanja najcesci element sa vrha steka */
			void pop()
			{
				if (max_freq == 0) {
					throw std::out_of_range("Stek je prazan");
				}

				const T x = stek[max_freq].top();
				stek[max_freq].pop();
				freq[x]--;

				if (stek[max_freq].empty())
				{
					max_freq--;
				}
			}

			/* Vraca referencu na najcesci element na vrhu steka bez uklanjanja */
			const T& top() const
			{
				if (max_freq == 0) {
					throw std::out_of_range("Stek je prazan");
				}

				return stek.at(max_freq).top();
			}

		private:
			std::map<T, int> freq;
			std::map<int, std::stack<T>> stek;
			int max_freq = 0;
	};
};

int main(void)
{
	matf::frek_stek<int> fs;

	char op;

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

	return 0;
}