Propose a data structure which supports the stack Push and Pop operations and a third

Q. Propose a data structure which supports the stack Push and Pop operations and a third operation FindMin, which returns the smallest element in the data structure.

Answer :-

Use two stacks say S1 and S2 - S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.

1. When first element is pushed in stack S1, push it to stack S2 too, considering that this is the minimum element.
2. When one needs to insert an element, say Ele:

(a) we first push Ele on to S1 and
(b) then access the top element, say T of S2 which is the minimum before the insertion of Ele.
(c) Compare Ele with T; if only Ele is less than T, we push Ele on to S2. Hence the current minimum will always be on top of S2.

3. When one needs to pop an element,

(a) pop the top element of S1 and
(b) if this element is also equal to the one on top of S2, then pop from S2 as well.