Разбор

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

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

Пусть на стек подается число $xk$-ый раз. Если элемент $st[k–1]$ не существует, то добавляем (push_back) элемент в массив $st$. Далее на вершину стека $st[k–1]$ кладем $x$.

При удалении следует извлечь элемент с верхушки самого последнего стека.

Например, если в дальнейшем будут только операции 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;
}