1class FreqStack {
2    // Map to track the frequency count of each element
3    private Map<Integer, Integer> frequencyMap = new HashMap<>();
4  
5    // Priority queue to maintain elements based on frequency and insertion order
6    // Each array contains: [frequency, timestamp, value]
7    // Ordering: higher frequency first, then more recent timestamp first
8    private PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> {
9        if (a[0] == b[0]) {
10            // Same frequency: compare by timestamp (larger timestamp = more recent)
11            return b[1] - a[1];
12        }
13        // Different frequency: higher frequency comes first
14        return b[0] - a[0];
15    });
16  
17    // Timestamp counter to track insertion order
18    private int timestamp;
19
20    /**
21     * Constructor to initialize the FreqStack
22     */
23    public FreqStack() {
24    }
25
26    /**
27     * Pushes an element onto the stack
28     * @param val the value to be pushed
29     */
30    public void push(int val) {
31        // Update the frequency count for this value
32        frequencyMap.put(val, frequencyMap.getOrDefault(val, 0) + 1);
33      
34        // Add to priority queue with current frequency, timestamp, and value
35        priorityQueue.offer(new int[] {frequencyMap.get(val), ++timestamp, val});
36    }
37
38    /**
39     * Removes and returns the most frequent element from the stack
40     * If there is a tie for most frequent element, the most recently pushed element is removed
41     * @return the popped value
42     */
43    public int pop() {
44        // Remove the element with highest priority (highest frequency, most recent)
45        int value = priorityQueue.poll()[2];
46      
47        // Decrease the frequency count for this value
48        frequencyMap.put(value, frequencyMap.get(value) - 1);
49      
50        return value;
51    }
52}
53
54/**
55 * Your FreqStack object will be instantiated and called as such:
56 * FreqStack obj = new FreqStack();
57 * obj.push(val);
58 * int param_2 = obj.pop();
59 */
60

1class FreqStack {
2public:
3    FreqStack() {
4        // Constructor - no initialization needed as member variables are already initialized
5    }
6
7    void push(int val) {
8        // Increment the frequency count for this value
9        ++frequency[val];
10      
11        // Push a tuple to the priority queue containing:
12        // 1. frequency[val]: current frequency of the value (higher frequency = higher priority)
13        // 2. ++timestamp: incrementing timestamp (later pushed = higher priority for same frequency)
14        // 3. val: the actual value
15        maxHeap.emplace(frequency[val], ++timestamp, val);
16    }
17
18    int pop() {
19        // Get the top element from the priority queue (most frequent, most recent)
20        auto [freq, time, value] = maxHeap.top();
21        maxHeap.pop();
22      
23        // Decrement the frequency count for this value
24        --frequency[value];
25      
26        return value;
27    }
28
29private:
30    // Maps each value to its current frequency in the stack
31    unordered_map<int, int> frequency;
32  
33    // Max heap that stores tuples of (frequency, timestamp, value)
34    // Elements are ordered by frequency first, then by timestamp
35    priority_queue<tuple<int, int, int>> maxHeap;
36  
37    // Global timestamp counter to track insertion order
38    int timestamp = 0;
39};
40
41/**
42 * Your FreqStack object will be instantiated and called as such:
43 * FreqStack* obj = new FreqStack();
44 * obj->push(val);
45 * int param_2 = obj->pop();
46 */
47

1// Maps each value to its current frequency in the stack
2const frequency: Map<number, number> = new Map();
3
4// Array of tuples storing [frequency, timestamp, value]
5// We'll manually maintain this as a max heap
6const maxHeap: Array<[number, number, number]> = [];
7
8// Global timestamp counter to track insertion order
9let timestamp: number = 0;
10
11// Helper function to compare heap elements
12// Returns true if a should have higher priority than b
13function compareTuples(a: [number, number, number], b: [number, number, number]): boolean {
14    // First compare by frequency (higher frequency = higher priority)
15    if (a[0] !== b[0]) {
16        return a[0] > b[0];
17    }
18    // If frequencies are equal, compare by timestamp (later timestamp = higher priority)
19    return a[1] > b[1];
20}
21
22// Helper function to maintain heap property after insertion
23function heapifyUp(index: number): void {
24    while (index > 0) {
25        const parentIndex = Math.floor((index - 1) / 2);
26        if (compareTuples(maxHeap[index], maxHeap[parentIndex])) {
27            // Swap with parent
28            [maxHeap[index], maxHeap[parentIndex]] = [maxHeap[parentIndex], maxHeap[index]];
29            index = parentIndex;
30        } else {
31            break;
32        }
33    }
34}
35
36// Helper function to maintain heap property after removal
37function heapifyDown(index: number): void {
38    const length = maxHeap.length;
39    while (true) {
40        let largest = index;
41        const leftChild = 2 * index + 1;
42        const rightChild = 2 * index + 2;
43      
44        if (leftChild < length && compareTuples(maxHeap[leftChild], maxHeap[largest])) {
45            largest = leftChild;
46        }
47        if (rightChild < length && compareTuples(maxHeap[rightChild], maxHeap[largest])) {
48            largest = rightChild;
49        }
50      
51        if (largest !== index) {
52            // Swap with largest child
53            [maxHeap[index], maxHeap[largest]] = [maxHeap[largest], maxHeap[index]];
54            index = largest;
55        } else {
56            break;
57        }
58    }
59}
60
61function push(val: number): void {
62    // Increment the frequency count for this value
63    const currentFreq = (frequency.get(val) || 0) + 1;
64    frequency.set(val, currentFreq);
65  
66    // Increment timestamp for this insertion
67    timestamp++;
68  
69    // Add tuple to the heap containing:
70    // 1. currentFreq: current frequency of the value (higher frequency = higher priority)
71    // 2. timestamp: current timestamp (later pushed = higher priority for same frequency)
72    // 3. val: the actual value
73    maxHeap.push([currentFreq, timestamp, val]);
74  
75    // Maintain heap property
76    heapifyUp(maxHeap.length - 1);
77}
78
79function pop(): number {
80    // Get the top element from the heap (most frequent, most recent)
81    const [freq, time, value] = maxHeap[0];
82  
83    // Move last element to top and remove the last element
84    maxHeap[0] = maxHeap[maxHeap.length - 1];
85    maxHeap.pop();
86  
87    // Maintain heap property if heap is not empty
88    if (maxHeap.length > 0) {
89        heapifyDown(0);
90    }
91  
92    // Decrement the frequency count for this value
93    const currentFreq = frequency.get(value)! - 1;
94    if (currentFreq === 0) {
95        frequency.delete(value);
96    } else {
97        frequency.set(value, currentFreq);
98    }
99  
100    return value;
101}
102