10379. Maximum frequency stack

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack. The possible commands are:

· push n – pushes an integer n onto the top of the stack;

· pop – removes and prints the most frequent element in the stack. If there is a tie for the most frequent element, the element closest to the stack’s top is removed and printed.

Input. Each line contains a single command.

Output. For each pop command print on a separate line the corresponding result.

Sample input 1	Sample output 1
push 4 push 5 push 4 push 6 push 7 pop push 5 pop pop	4 5 7
Sample input 2	Sample output 2
push 5 push 3 push 1 push 3 push 9 pop pop pop pop pop	3 9 1 3 5

SOLUTION

data structures - stack

Algorithm analysis

For each number x we’ll store the number of times freq[x] that it occurs in the stack. Let’s choose a map as a data structure for freq.

Declare an array of stacks vector<stack<int>> st. Here st[i] stores elements that occur on the stack i + 1 times (the numbering of cells in the st array starts from zero). The order in which the elements are in st[i] matches the order in which they are pushed onto the stack.

Let the number x be pushed to the stack for the k-th time. If the element st[k – 1] does not exist, then add (push_back) the element to the st array. Then push x to the top of the stack st[k – 1].

When you delete element, you must pop the item from the top of the last stack.

For example, if in the future there are only pop operations, then the elements from the stack will be removed in the following order: 4, 5, 4, 6, 5, 4.

Example

Consider the order in which elements are pushed into array of stacks for the next example.

When removed, items will be popped from the stack in the following order: 1, 5, 1, 5, 2, 6, 1, 5.

Algorithm realization

To work with the frequency stack, we declare the FreqStack class.

class FreqStack

{

public:

Declare:

· map freq, where freq[x] contains the number of times an element x occurs in the stack;

· array of stacks st;

map<int, int> freq;

vector<stack<int>> st;

The function push pushes the element x to the stack.

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);

}

The function pop pops element from the stack.

int pop()

{

int x = st.back().top();

st.back().pop();

if (st.back().empty()) st.pop_back();

freq[x]--;

return x;

}

};

The main part of the program. Read the input data. Simulate the stack.

while (cin >> str)

{

if (str == "push")

{

cin >> n;

fs.push(n);

}

else // pop

cout << fs.pop() << endl;

}