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) элемент в массив 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;

}