Implement a stack where, getMinValue() operation is of O(1)

Main source of the article

http://www.rawkam.com/?p=1337

The problem statement is: Implement a stack where, getMinValue() operation is of O(1).

Solution :
1st Soultion : maintain two stacks. First stack is the normal one. Second stack top will always contain the minimum value at the point. So when ever you need min value simply take it form the second stack top element.

Push Operation
aprat from normal operation on first stack
Add the element to second stack if top most element of the second stack is less then the current element.

Pop Operation
First stack normal pop up will be done.
Check if the poped element is same as the top element in the second stack. then remove that element from the second stack as well.

Pros and Cons: Pros are all three operations ie. push pop and getMinValue are of O(1). But the flip side is that the it requires more space.


2nd Solution:
Mainin the pointer minPoiner, and you need to modify the pointer when doing Pop operation.in Pop operation may require traversal of the entire stack to find the next min value.

pros : NO extra space, but the Pop operation is O(n).



3rd solution :
Modify the stack node structure itself. add one field that points to the next min element.
Funda is like this. first each node will have an extra field called next min.
node {
next;
data;
nextMin;
}

Plus as usal there would be one pointer Min Pointer which will point to the current min value element.

Push operation
if current pusehed element is less then the earlier maintained min value. Definatly you need to modify the Min Pointer but you also need to do one more thing. like

top->nextMin = Old Min
Min = new min.

Pop Operation
Very simple if current poped node is the min node simply put the min node to top->next min node.


Please note that this can be little deseptive, as this nextMin we will not use for all the nodes.

Both push pop and get min are of order O(1)