minStack: Data Structures and Algorithm

Java
2

For the record, I just reviewed the same code and came to the same conclusion: Mosh’s code is buggy. I think you need to keep track of the “min so far” in a second stack and pop off of it every time pop is called. His code fails to account for the possibility that the same value is added to the stack multiple times. For example, if I just fill the stack with the same value (say 5), it will only put one value into the minStack (5) and that will get popped the moment we pop the first 5 off of the main stack resulting in an empty minStack (and hence a bug when min is called after that first pop. So, here is how I fix the implementation:

public class MinStack {
  private Stack stack = new Stack();
  private Stack minStack = new Stack();

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

    if (minStack.isEmpty() || item < min()) {
      minStack.push(item);
    } else {
      minStack.push(min());
    }
  }

  public int pop() {
    if (stack.isEmpty())
      throw new IllegalStateException();

    minStack.pop();

    return stack.pop();
  }

  public int min() {
    return minStack.peek();
  }
}

Uses more space, but does not have the bugs that were present in Mosh’s code.