> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/design/untitled/895.-maximum-frequency-stack.md).

# 895. Maximum Frequency Stack!

{% hint style="info" %}
valueToFreq map and freqToValue  map\<Integer, Stack>
{% endhint %}

```java
class FreqStack {

    HashMap<Integer, Integer> valueToFreqs;
    HashMap<Integer, Stack<Integer>> freqToValues;
    int maxFreq;
    public FreqStack() {
        valueToFreqs = new HashMap<>();
        freqToValues = new HashMap<>();
    }
    
    public void push(int val) {
        int freq =valueToFreqs.getOrDefault(val, 0)+1;
        valueToFreqs.put(val, freq);
        
        //update freqToValue
        if(!freqToValues.containsKey(freq)) freqToValues.put(freq, new Stack<>());
        freqToValues.get(freq).push(val);
        
        maxFreq = Math.max(maxFreq, freq);
    }
    
    public int pop() {
        int value = freqToValues.get(maxFreq).pop();
        valueToFreqs.put(value, maxFreq-1);
        if(freqToValues.get(maxFreq).isEmpty()){
            maxFreq--;
        }

        return value;
    }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(val);
 * int param_2 = obj.pop();
 */
```

```java
class FreqStack {
    //key int, value: frequency
    private HashMap<Integer, Integer> freq = new HashMap<>();
    // stack<Integer> use to get the element if there are same frequency element
    // key: freq
    private HashMap<Integer, Stack<Integer>> map = new HashMap<>();
    int maxfreq = 0;
    
    public FreqStack() {
        
    }
    
    public void push(int val) {
        freq.put(val, freq.getOrDefault(val, 0)+1);
        int frequency = freq.get(val);
        if(map.containsKey(frequency)){
            map.get(frequency).push(val);
        }else{
            Stack<Integer> stack = new Stack<>();
            stack.push(val);
            map.put(frequency, stack);
        }
        maxfreq = frequency>maxfreq ? frequency : maxfreq;
    }
    
    public int pop() {
        Stack<Integer> stack = map.get(maxfreq);
        int result = stack.pop();
        if(stack.isEmpty()){
            maxfreq--;
        }
        freq.put(result, freq.get(result)-1);
        return result;
    }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(val);
 * int param_2 = obj.pop();
 */
```