Problem Description

1. The maximum frequency stack implements FreqStack, a class that simulates operations similar to the stack's data structure.

FreqStack has two functions:

push(int x), pushing the integer x onto the stack. pop(), which removes and returns the most frequent elements in the stack.
If more than one element is most frequent, remove and return the element closest to the top of the stack.

Source: LeetCode
Links: https://leetcode-cn.com/problems/maximum-frequency-stack

Solving problems

This question is still mostly written by frequency and time, and Two implementations of LFU algorithm c++. The problem is similar. Only in LFU, each element occurs at most once.
Therefore, two solutions are still provided in a similar way.

Idea 1 [hash Table + priority queue]

• The first is to record frequency information and time stamp information into each element node, and then sort them in order of frequency from large to small and time from large to small, taking the first one each time.
• A hash table is still needed to record the mapping of < Value, Frequency > because when push or pop, you need to know whether or not the element has appeared in the queue in priority and how often it occurs. Because the new frequency is always its original frequency + 1.
• This is different from the LFU algorithm, in which the get function is parameterized and must return the X that you want to get(x), so recording frequency alone is not enough, and you need to know where it is. Then update the frequency and time in the priority queue (delete and insert new nodes, priority queue can only delete heap top elements, so set implementation is used in LFU). In this topic, pop returns heap top elements and can be deleted directly. push creates a new node without having to care where the old node is.

struct Node{
    int val;
    int time;
    int freq;
    Node(){}
    Node(int _val, int _time, int _freq){
        val=_val;
        time=_time;
        freq=_freq;
    }

    
};
struct cmp{
    bool operator () (const Node& lhs,const Node&rhs)const {
        // Default big root heap, so we can sort by frequency from small to large and time stamp from small to large
        return lhs.freq==rhs.freq?lhs.time<rhs.time:lhs.freq<rhs.freq;
    }
};
class FreqStack {
public:
    
    unordered_map<int,int> v2f;

    priority_queue<Node,vector<Node>,cmp>pq;
    int global_time=0;

    FreqStack() {
    }
    
    void push(int val) {
        int f;
        if(v2f.count(val)){
            // If it already exists, the frequency of the new node is + 1
            f = ++v2f[val];
        }else{
            f=1;
            v2f[val]=1;
        }
        Node n(val,global_time++,f);
        pq.push(n);
    }
    
    int pop() {
        if(pq.empty()){
            return -1;
        }
        Node n=pq.top();
        pq.pop();
        // Update hash table
        v2f[n.val]--;
        if(!v2f[n.val])
        {
            v2f.erase(n.val);
        }
        return n.val;
    }
};

Idea two: hash table + single-chain table

• Use array subscripts to achieve freq ordering, which is freq (default freq=0, so no waste)
• Each element in the array is a single-linked list (or simply a stack), and each time it is inserted from the chain header, the deletion is also deleted directly.
• Use hash tables to record mappings for <val, freq>
• The push:hash table updates freq, generates a new node, and places it in the chain header of the corresponding freq.
• pop: delete from the last chain header of the array, and delete the array element if the chain is empty

class FreqStack {
public:
    vector<list<int>> array;
    unordered_map<int,int>v2f;

    FreqStack() {
        array.push_back(list<int>());
    }
    
    void push(int val) {
        int f;
        if(v2f.count(val)){
            f = ++v2f[val];
            
        }else{
            f =0;
            v2f[val]=0;
        }
        if(f==array.size()){
            array.push_back(list<int>());
        }
        array[f].push_front(val);
    }
    
    int pop() {
        int res = array.back().front();
        
        v2f[res]--;
        if(v2f[res]==-1){
            v2f.erase(res);
        }
        array.back().pop_front();
        if(array.back().empty())
        array.pop_back();
        return res;
        
    }
};