how to find maximum value stored in stack in constant time.

Question

Using a temp variable to store max value does not work for pop operations.

Answer 1

If you don't care about O(n) in the push operation:

My personal approach would be to keep a linked list of sorted items. Whenever you pop an item, compare it to the highest item in the sorted list. If it is the same, remove the highest item from the list, in addition to popping the item. If it is not, just pop the item.

This way, you should always have the highest item at the last element of the linked list, and the time for popping is O(1).

If you also need O(1) for pushing, then I'll have to pass.

Answer 2

You can't. A stack is unsorted, which means that you have to inspect all N values to find the highest. That alone means it is at least O(N) while "constant time " means O(1)