Question

link

Implement a stack, enable O(1) Push, Pop Top, Min. Where Min() will return the value of minimum number in the stack.

Solution

Using two stacks.

The first one is the regular stack.

The second one only store minimum numbers.

Eg:

Actual stack: (head) 16 15 29 19 18 (tail)

Auxiliary Stack: (head) 15 15 18 18 18 (tail)

Code

Psudu-code:

Push(int x):
1) push x to the first stack (the stack with actual elements)
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.
…..a) If x is smaller than y then push x to the auxiliary stack.
…..b) If x is greater than y then push y to the auxiliary stack.

Pop():
1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.

Code is skipped.