Coding Exercises Day 25 (Problem #19)

Problem:
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 all operate in O(1) time.

class Stack {
  List<Node> minList = new LinkedList<Node>();

  Node top = null;

  public void push(Node node) {
    if (null == top) {
      top = node;
      node.setNext(null);

      minList.add(0, node);
    }    
    else {
      node.setNext(top);
      top = node;

      // This is the new minimum
      if (node.getValue() < minList.get(0).getValue()) {
        minList.add(0, node);
      }
      else {
        // previous minimum node is still the minimum
        minList.add(0, minList.get(0));
      }
    }
  } 

  public Node pop() {
    rval = top;

    top = top.getNext();

    minList.remove(0);

    return rval;
  }

  public Node min() {
    return minList.get(0);
  }
}