Most Frequent Stack

Build a FreqStack class: a stack where pop takes out the most common value rather than whatever is on top.

• FreqStack() starts empty.
• push(x) puts the value x on top of the stack.
• pop() finds the values that appear most often in the stack. Of those, it picks the one with a copy nearest the top, removes that copy and returns the value. Popping an empty stack raises IndexError.

Examples

fs = FreqStack()
for x in [5, 7, 5, 7, 4, 5]:
    fs.push(x)
fs.pop()    # returns 5    (5 appears three times)
fs.pop()    # returns 7    (5 and 7 appear twice; the top 7 is above the top 5)
fs.pop()    # returns 5    (5 appears twice, 7 and 4 once)
fs.pop()    # returns 4    (all appear once; 4 is nearest the top)

Constraints

• Up to 100,000 calls; values are whole numbers or strings
• Counting the whole stack again on every pop is too slow when it holds tens of thousands of values.