Implement a stack that pops out the most frequently added item.

Implement a stack that pops out the most frequently added item. Stack supports 3 functions - push, pop,and top. Give complexity of each functions in your implementation.


Approach:
Let the sample data be:
A = {7, 5, 9, 3, 7, 3, 9, 7, 3, 7, 9, 7};


We maintain 2 maps:
1. stackMap = new HashMap<Integer, Stack<Integer>>();
   stackMap keeps the mapping of count to stack of data.
2. countMap = new HashMap<Integer, Integer>();
   countMap keeps the mapping of data to frequency of data.
3. maxCount = 0;


Now lets trace the operations on sample data - we also keep track of the snapshots of the stackMap and countMap.
Push(A[0] = 7)
stackMap(1 => stack[7]);
countMap(7 => 1)
maxCount = 1;


Push(A[1] = 5)
stackMap(1 => stack[5, 7]);
countMap(7 => 1)
countMap(5 => 1)
maxCount = 1;


Push(A[2] = 9)
stackMap(1 => stack[9, 5, 7]);
countMap(7 => 1)
countMap(5 => 1)
countMap(9 => 1)
maxCount = 1;


Push(A[3] = 3)
stackMap(1 => stack[3, 9, 5, 7]);
countMap(7 => 1)
countMap(5 => 1)
countMap(9 => 1)
countMap(3 => 1)
maxCount = 1;


Push(A[4] = 7)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[7]);
countMap(7 => 2)
countMap(5 => 1)
countMap(9 => 1)
countMap(3 => 1)
maxCount = 2;


Push(A[5] = 3)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[3, 7]);
countMap(7 => 2)
countMap(5 => 1)
countMap(9 => 1)
countMap(3 => 2)
maxCount = 2;


Push(A[6] = 9)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
countMap(7 => 2)
countMap(5 => 1)
countMap(9 => 2)
countMap(3 => 2)
maxCount = 2;


Push(A[7] = 7)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[7]);
countMap(7 => 3)
countMap(5 => 1)
countMap(9 => 2)
countMap(3 => 2)
maxCount = 3;


Push(A[8] = 3)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[3, 7]);
countMap(7 => 3)
countMap(5 => 1)
countMap(9 => 2)
countMap(3 => 3)
maxCount = 3;


Push(A[9] = 7)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[3, 7]);
stackMap(4 => stack[7]);
countMap(7 => 4)
countMap(5 => 1)
countMap(9 => 2)
countMap(3 => 3)
maxCount = 4;


Push(A[10] = 9)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[9, 3, 7]);
stackMap(4 => stack[7]);
countMap(7 => 4)
countMap(5 => 1)
countMap(9 => 3)
countMap(3 => 3)
maxCount = 4;


Push(A[11] = 7)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[9, 3, 7]);
stackMap(4 => stack[7]);
stackMap(5 => stack[7]);
countMap(7 => 5)
countMap(5 => 1)
countMap(9 => 3)
countMap(3 => 3)
maxCount = 5;


Lets trace a top() operation now:
top()
maxCount is 5 now, so we do get the stack corresponding to key=5 from stackMap
we have the following map pair for key=5 stackMap(5 => stack[7]);
so we retieve the stack[7] from the stackMap and then do a stack.peek() to return the top for the frequentStack top() call.


Lets see now how the pop() would work:
maxCount is 5
Get the stack corresponding to the key=maxCount(5) from stackMap datastructure.
stackMap(5 => stack[7]);
so we get here stack[7], now do pop from the stack - that would be our result data which would be returned fromt he pop() call.
we also update countMap(7 => 5) to countMap(7 => 4)
Now since the stack would be empty corresponding to key=5, we decrement the maxCount by 1 ie now maxCount=4.


now lets call pop() second time.
maxCount is 4
stack corresponding to key=4 in stackMap is stack[7] refer - stackMap(4 => stack[7]);
we pop the stack, again stack is empty so we decrement the maxCount by 1, now maxCount=3;
we also update countMap(7 => 4) to countMap(7 => 3)


pop() third time:
maxCount is 3.
stack corresponding to key=3 in stackMap is stack[9, 3, 7] refer stackMap(3 => stack[9, 3, 7]);
after popping the stack it becomes stack[3, 7] - which is not empty so we dont decrement the maxCount, it stays at 3.
we update countMap(9 => 3) to countMap(9 => 2)


pop() 4th time:
maxCount is still 3.
stack corresponding to key=3 in stackMap is now stack[3, 7].
after popping the stack it becomes stack[7] - which is not empty so we dont decrement the maxCount, it stays at 3.
we update countMap(3 => 3) to countMap(3 => 2)


pop() 5th time:
maxCount is still 3.
stack corresponding to key=3 in stackMap is now stack[7].
we pop the stack, stack is empty correponding to key=3, so we decrement the maxCount by 1, now maxCount=2
we also update countMap(7 => 3) to countMap(7 => 2)


I think by now you got the idea.
If now please drop me a line for clarification.


Time complexity:
Push: O(1)
Pop: O(1)
top: O(1)


Space Complexity: O(n)


Code output:
Pushing following elements on frequency stack: 
7 5 9 3 7 3 9 7 3 7 9 7 
Top from frequency stack: 7
Sequence of pops from frequency stack: 
7 7 9 3 7 9 3 7 3 9 5 7