3.2 --- design a stack with function min() at O（1） time

Q: 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.

A： Thinking at after min value is popped out, it need find the minimum value that pushed before it.
So, we only need a pointer to it.  Thus, for stack S, with min value of B, we add a pointer, when push(A), where A is so far the minimum, then its pointer would point to node B.
但，这样， 修改了Node的结构，是否有点儿太深了？  -------------  书上就是这样解的。
就是把Node的结构，换成了，<Node , int curMin>

另一个方法，就是，加一个min-list,representing that, till now, the minValue,
 （考虑到有重复的min值出现的情况，我们有两个办法：
1：在每个min-list的node中，还要加一个，出现的次数
2：在加入min-list时，如果和迄今为止的最小的同样小 ，我们也加入min-list中。(从书上看到的，其实这个list，更多的是一个stack的功能。可以用stack代替。)

下面是实现。 (但是，从list加入item到stack的时候，push(),总是漏几个，问题出在哪儿呢？？？？)

public class MinStack3_2 {
 LinkList stackList;
 LinkList minList ;

 Node pop() {
  Node poppedNode  = stackList.deleteAtBeginning();
  if (poppedNode.data == minList.header.next.data) {
   minList.deleteAtBeginning();
  }else if(poppedNode.data == minList.header.next.data){
   System.out.println("Error at functioin pop();-----------minList is wrong");
  }
  return poppedNode;  
 }

 void push(Node t) {
  stackList.insertAtBeginning(t);  
  //update the minList, record only the ones, that is the minimum so far
  if (minList.header.next == null || t.data <= minList.header.next.data) {
   minList.insertAtBeginning(t);
  }

 }

 Object min() {
  return minList.header.next;
 }
 public MinStack3_2(){
   stackList = new LinkList();
   minList = new LinkList();
 }
}

 Mistakes:
 1:  Stack的实现 中，由于stack是基于linkList的，所以，如果直接加入的话，仅仅是加入了一个引用。其后，在list中的任何值改变的话，stack的值也会变化。------>故而尽量new 一个值。
2：  又是在printStack的时候， 没有update runner.

3：总是有两个top值，为什么呢? 应该是继承了一个，自己又声明了一个？？？？？是这样的吗？


Learned: