Stack with Min() Operation - Easy

Problem : Implement a stack with push() , pop() and a min() (which returns the minimum element in the stack). All operations should be O(1).

Another popular question, I've searched around a lot came across many answers, but only one had completeness. It's important to note that with the stack you don't have random access to the contents of the stack when implementing your solution.

The solution I'm describing involves using 2 stacks, one is to store the data elements themselves (mainstack) and the other to store minimum values, which i'll refer to as minstack. Now we can have 2 parallel stacks where we push and pop on the minstack along with the mainstack, keeping track of the minimum value of course. But we can optimize this further. We only need to push values on the minimum stack only when you push a value on the main stack that is less than or equal to the current top element of the minstack.
Here's are the two stacks after pushing 67,44,20,77,99,12 in that order.

When an element is poped, you check if the value on the minstack top is the same as the one on the mainstack, if it is we pop it from the minstack as well. Here's me poping 12.

Let's get to the code now. I pick Java as my weapon of choice.

	class StackMin extends Stack {
	private Stack minStack;
	public StackMin(int size) {
	super(size);
	minStack = new Stack(size);
	}
	@Override
	public void push(int item) throws Exception {
	if(empty() || item <= minStack.peek())
	minStack.push(item);
	super.push(item);
	}
	@Override
	public int pop() throws Exception {
	int item = super.pop();
	if(item == minStack.peek())
	minStack.pop();
	return item;
	}
	public int min() throws Exception {
	if(empty()) throw new Exception("Stack is empty.");
	return minStack.peek();
	}
	}

view raw Stack with Min() hosted with ❤ by GitHub

Complete Code can be found here. It's important to note that we can implement both max() and min() for the same stack. You'll need one more stack for keeping track of the maximum element. I'll leave that as an exercise for you. Cheers!