minStack: Data Structures and Algorithm

Java
1

Both the exercise on stacks have bugs, not scalable and with limitation. For a beginner like me, after doing it myself and not be able to find the correct solution, I will go check Mosh solution and try to analyze how to solve it.

For example in minStack exercise.

While testing around the logic with command below:
var stacks = new MinStack();
stacks.push(8);
stacks.push(1);
stacks.push(2);
stacks.push(3);
stacks.push(5);
stacks.push(1);
stacks.pop();
var x = stacks.min();
System.out.println(x);

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

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

    if (minStack.isEmpty())
        minStack.push(item);
    else if (item < minStack.peek())
        minStack.push(item);
}

public int pop(){
    var top = stack.pop();

    if ( minStack.peek() == top )
        minStack.pop();

    return top;
}

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

}

problem is that, after adding 1(the least) after pushing 8. Since 1 is less than any other element pushed. The next minimum value would be 8. Thus if you push 1 as duplicate and pop it out. You only have one value left on stack which is 8 and that’s going to be your minimum regardless of the value of others.

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.