[f]izzbuzzer

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Stack with min() operation

Problem Statement
Create a stack data structure that supports the following operations as efficiently as possible:

Push, which adds a new element atop the stack,
Pop, which removes the top element of the stack,
Find-Min, which returns (but does not remove) the smallest element of the stack

Full Code

```package stacksqueues;

import java.util.ArrayList;
import java.util.List;

import datastructures.MyStack;

/**
* How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum
* element? Push, pop and min should all operate in O(1) time.
*
* @author lucas
*/
public class E2 {
protected static class MyStackWithMin extends MyStack {
MyStack mins;

public MyStackWithMin() {
mins = new MyStack();
}

public void push(int item) {
super.push(item);

if (item <= min()) {
mins.push(item);
}

}

public Integer pop() {
int item = (int) super.pop();
if (item == min()) {
mins.pop();
}

return item;
}

/**
* Return min element on stack
*
* @return
*/
public int min() {
if (mins.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return (int)mins.peek();
}
}
}

public static void main(String[] args) {
MyStackWithMin stack = new MyStackWithMin();

stack.push(3);
stack.push(31);
stack.push(13);
stack.push(2);
stack.push(5);

System.out.println(stack.min());
}

}
```