Frequency Stack

Frequency Stack

Design a stack whose pop removes the most frequently pushed element, breaking ties in favor of the element pushed most recently.

Requirements

• pop removes and returns the element with the highest current frequency in the stack.
• When several elements share the highest frequency, pop returns the one that was pushed most recently.
• pop is only called when the stack is non-empty — focus on the design, not empty-stack validation.
• Both operations should run in O(1) amortized time.

API to implement

Implement the class FreqStack. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | push <val> | — | Push val onto the stack. | | pop | int | Remove and return the most frequent element; on a tie, the one pushed most recently. Never called on an empty stack. |

Input format

The first line contains Q, the number of operations. Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

10
push 5
push 7
push 5
push 7
push 4
push 5
pop
pop
pop
pop

5
7
5
4

8
push 1
push 1
push 2
push 2
pop
pop
pop
pop

2
1
2
1