Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:


	FreqStack() constructs an empty frequency stack.
	void push(int val) pushes an integer val onto the top of the stack.
	int pop() removes and returns the most frequent element in the stack.
	
		If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.
	
	


&nbsp;
Example 1:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

Explanation
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].


&nbsp;
Constraints:


	0 &lt;= val &lt;= 109
	At most 2 * 104 calls will be made to push and pop.
	It is guaranteed that there will be at least one element in the stack before calling pop.


class FreqStack:

    def __init__(self):
        self.cnt = {}
        self.maxcount = 0
        self.stack = {}

    def push(self, val: int) -> None:
        count = self.cnt.get(val,0)+1
        self.cnt[val] = count
        if count>self.maxcount:
            self.maxcount = count
            self.stack[count] = []
        self.stack[count].append(val)

    def pop(self) -> int:
        res = self.stack[self.maxcount].pop()
        self.cnt[res]-=1
        if not self.stack[self.maxcount]:
            self.maxcount-=1
        return res

# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
class Node{
    int data, freq, time;
    Node(int data, int freq, int time){
        this.data=data;
        this.freq=freq;
        this.time=time;
    }
}

class CompareNode implements Comparator<Node>{
    @Override
    public int compare(Node a, Node b){
        if(a.freq-b.freq==0){
            return b.time-a.time;
        }
        return b.freq-a.freq;
    }
}

class FreqStack {
    PriorityQueue<Node> pq;
    Map<Integer,Node> map;
    int c=0;
    public FreqStack(){
        pq=new PriorityQueue<>(new CompareNode());
        map=new HashMap<>();
    }

    public void push(int val){
        c++;
        int freq=1;
        if(map.containsKey(val)){
            freq+=map.get(val).freq;
        }
        map.put(val, new Node(val, freq, c));
        pq.add(new Node(val,freq,c++));
    }

    public int pop() {
        Node r=pq.remove();
        Node a=map.get(r.data);
        a.freq--;
        return r.data;
    }
}
class FreqStack {
public:
    unordered_map<int,int> ump;
    unordered_map<int,stack<int>> ump_st;
    
    int cap=1;
    
    FreqStack() {
        ump.clear();
        ump_st.clear();
    }
    
    void push(int val) {
	
		//increasing the count
        if(ump.find(val)!=ump.end())
        {
            ump[val]++;
        }
        else
        {
            ump[val]=1;
        }
        
		//update the highest level
        if(cap<ump[val])
        {
            cap = ump[val];
        }
		
        //push the elements in the stack where it belongs as per height
        ump_st[ump[val]].push(val);
    }
    
    int pop() {
        int val = ump_st[cap].top();
        ump_st[cap].pop();
        
        if(ump_st[cap].size()==0)
        {
            cap--;
        }
        
        ump[val]--;
        
        if(ump[val]==0)
        {
            ump.erase(val);
        }
        
        return val;
    }
};
var FreqStack = function() {
    //hashMap to keep track of the values being repeated
    this.frequencyMap = {};

    //List map to keep track of the sequence of the value being entered
    this.listMap = {};

    //Max Frequency variable to keep track of the max frequency
    this.maxValueFrequency = 0;
};

/**
 * @param {number} val
 * @return {void}
 */
FreqStack.prototype.push = function(val) {
    //if the hashMap doesn't have value being pushed then make a entry to it with 1 else increament by 1
    this.frequencyMap[val] = this.frequencyMap[val] ? this.frequencyMap[val]+1 : 1;

    //get the frequency of the value being pushed
    const currentValueFrequency = this.frequencyMap[val];

    //check if the current frequency is max or itself
    this.maxValueFrequency = Math.max(this.maxValueFrequency, currentValueFrequency);

    //if current value frequency is not in the listmap then make a new entry else push it
    if(!this.listMap[currentValueFrequency]) this.listMap[currentValueFrequency] =[val];
    else this.listMap[currentValueFrequency].push(val);

};

/**
 * @return {number}
 */
FreqStack.prototype.pop = function() {
    //make a temporary list of the max value frequency
    const tempList = this.listMap[this.maxValueFrequency];

    //get the last element from the temporary list
    const top = tempList[tempList.length - 1];

    //remove the item from the list
    tempList.pop();

    //update the list
    this.listMap[this.maxValueFrequency] = tempList;

    //if the popped item exist in the frequecy map then decrease it by 1
    if(this.frequencyMap[top]) this.frequencyMap[top]--;

    //if the max value frequency in the listmap is blank then reduce the maxValueFrequency;
    if(this.listMap[this.maxValueFrequency].length === 0) this.maxValueFrequency--;

    //return the max value frequency with proper order if it is same
    return top;

};

//Time O(Log n) // for both Push and Pop
//Space O(n) for storing all the values in the hashMap and listMap
Maximum Frequency Stack