Максимальний частотний стек (Розбір)

Для кожного числа $x$ будемо зберігати кількість його входжень у стеку freq[x]. Як структуру даних для зберігання $freq$ оберемо map.

Оголосимо масив стеків vector<stack<int>> st, де $st[i]$ містить елементи, які зустрічаються у стеку рівно i + 1 раз (нумерація елементів масиву $st$ починається з нуля). Порядок елементів у $st[i]$ відповідає порядку їх додавання у стек.

Нехай число $x$ додається у стек $k$-ий раз. Якщо стек st[k - 1] ще не створений, додамо його за допомогою push_back. Потім покладемо $x$ на вершину стеку st[k - 1].

При видаленні елемента треба дістати верхній елемент з найостаннішого непорожнього стеку.

Наприклад, якщо далі буде виконуватись лише операція pop, то елементи будуть видалятися з стеку в наступному порядку: 4, 5, 4, 6, 5, 4.

Приклад

Розглянемо порядок додавання елементів у масив стеків на наступному прикладі.

При видаленні елементи будуть витягуватися в наступному порядку: 1, 5, 1, 5, 2, 6, 1, 5.

Реалізація алгоритму

Для роботи з частотним стеком оголосимо клас FreqStack.

class FreqStack
{
public:

Оголосимо:

• відображення $freq$, де freq[x] зберігає кількість входжень елемента $x$ у стеку;

• масив стеків $st$;

  map<int, int> freq;
  vector<stack<int>> st;

Функція push додає у стек елемент $x$.

  void push(int x)
  {
    int f = freq[x];
    freq[x] = f + 1;
    if (f == st.size()) st.push_back(stack<int>());
    st[f].push(x);
  }

Функція pop витягує елемент з стеку.

  int pop()
  {
    int x = st.back().top();
    st.back().pop();
    if (st.back().empty()) st.pop_back();
    freq[x]--;
    return x;
  }
};

Основна частина програми. Читаємо вхідні дані. Моделюємо роботу стеку.

while (cin >> str)
{
  if (str == "push")
  {
    cin >> n;
    fs.push(n);
  }
  else // pop
    cout << fs.pop() << endl;
}