Stack Whose Pop Removes the Most Frequent Value, Ties Broken by Recency

A frequency stack holds integers and supports two operations:

• push x: place x on top of the stack.
• pop: remove and return the value that occurs most often in the stack right now. If several values tie for the highest count, choose the one that has an occurrence closest to the top of the stack. Only that value's topmost occurrence is removed.

Given a sequence of operations, return the values returned by the pop operations, in order.

Function Signature

def frequency_stack(operations: list[tuple[str, int]]) -> list[int]:

Each operation is ("push", x) or ("pop", 0). The integer in a pop operation is always 0 and is ignored.

Rules

• The count of a value is the number of its occurrences currently in the stack. Occurrences already removed by earlier pops do not count.
• Among the values tied for the highest count, pick the one whose topmost occurrence is nearest the top of the stack, then remove exactly that occurrence. All other elements keep their order.
• A pop is issued only when the stack is not empty.
• If there are no pop operations, return an empty list.

Constraints

• 1 <= len(operations) <= 10^5
• -10^9 <= x <= 10^9 for every pushed value
• Every pop is applied to a non-empty stack.

Examples

Example 1

Input: operations = [("push", 3), ("push", 8), ("push", 3), ("push", 8), ("push", 1), ("push", 3),
 ("pop", 0), ("pop", 0), ("pop", 0), ("pop", 0)]
Output: [3, 8, 3, 1]

The stack, bottom to top, is 3, 8, 3, 8, 1, 3. The first pop returns 3, which occurs three times, and leaves 3, 8, 3, 8, 1. Now 3 and 8 both occur twice, and the topmost 8 is above the topmost 3, so 8 is returned, leaving 3, 8, 3, 1. Next 3 is the only value that occurs twice, leaving 3, 8, 1. Finally 3, 8 and 1 each occur once, and 1 is on top.

Example 2

Input: operations = [("push", 2), ("push", 2), ("push", 9), ("pop", 0), ("push", 9),
 ("pop", 0), ("pop", 0), ("pop", 0)]
Output: [2, 9, 9, 2]

After three pushes the stack is 2, 2, 9. The first pop returns 2 and leaves 2, 9. Pushing 9 gives 2, 9, 9, so 9 now occurs most often and is returned, leaving 2, 9. Then 2 and 9 each occur once, and 9 is on top. The last pop returns 2.

Example 3

Input: operations = [("push", -1), ("pop", 0), ("push", -1), ("push", 6), ("push", 6),
 ("push", -1), ("pop", 0)]
Output: [-1, -1]

The first pop empties the stack. Afterwards the stack is -1, 6, 6, -1: both values occur twice, and the topmost -1 is above the topmost 6.