10379. Максимальный частотный стек

Разработайте структуру данных, аналогичную стеку, которая позволяет добавлять элементы и извлекать из стека наиболее часто встречающийся элемент.

Возможны следующие команды:

· push n – добавить в стек число n;

· pop – удалить и вывести наиболее часто встречающееся в стеке число. Если таких чисел несколько, необходимо удалить и вывести то из них, которое находится ближе к вершине стека.

Вход. Состоит из команд, по одной в каждой строке.

Выход. Для каждой операции pop выведите результат в отдельной строке.

Пример входа 1	Пример выхода 1
push 4 push 5 push 4 push 6 push 7 pop push 5 pop pop	4 5 7
Пример входа 2	Пример выхода 2
push 5 push 3 push 1 push 3 push 9 pop pop pop pop pop	3 9 1 3 5

РЕШЕНИЕ

структуры данных - стек

Анализ алгоритма

Для каждого числа 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;

}