895. Maximum Frequency Stack

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

push(int x), which pushes an integer x onto the stack.
pop(), which removes and returns the most frequent element in the stack.
If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

class FreqStack {
private:
    unordered_map<int,int> frequencyOfElement;
    unordered_map<int,list<int>> stack;
    int maxFrequency;
public:
    FreqStack() {
        frequencyOfElement.clear();
        stack.clear();
        maxFrequency = 0;
    }
    
    void push(int x) {       
        ++ frequencyOfElement[x];
        stack[ frequencyOfElement[x] ].push_front(x);
        maxFrequency = max(maxFrequency, frequencyOfElement[x]);
    }
    
    int pop() {
        int ans = stack[maxFrequency].front();
        stack[maxFrequency].pop_front();
        if(stack[maxFrequency].empty()){
            stack.erase(maxFrequency);
            -- maxFrequency;
        }
        -- frequencyOfElement[ans];
        return ans;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 */