Stack DS to implement constant time Minimum element lookup
Problem: You need to implement a stack data structure that can also report the minimum element in constant-time. Solution Method 1 - Using extra stack This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can’t just add a new variable to track the minimum because when the stack is popped you wouldn’t be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly. So we need to keep some auxiliary list of the stack items so we can update the minimum variable after we pop items. ...