Stack的ADT：

 

1 package ren.laughing.datastructure.base; 2  3 import ren.laughing.datastructure.exception.StackEmptyException; 4  5 /** 6  * Stack 栈：后进先出 7  * 只能在栈顶top进行插入（入栈）、删除（出栈）操作 8  * @author Laughing_Lz 9  * @time 2016年4月6日10  */11 public interface Stack {12     //返回堆栈的大小13     public int getSize();14     //判断堆栈是否为空15     public boolean isEmpty();16     //数据元素 e入栈17     public void push(Object e);18     //栈顶元素出栈19     public Object pop() throws StackEmptyException;20     //取栈顶元素21     public Object peek() throws StackEmptyException;22     }

 栈的顺序存储：

1 package ren.laughing.datastructure.baseImpl; 2  3 import ren.laughing.datastructure.base.Stack; 4 import ren.laughing.datastructure.exception.StackEmptyException; 5 /** 6  * 栈的顺序存储结构 7  * 一般来说在构造堆栈时不应设定堆栈的最大容量。 8  * 一种合理的做法为先为堆栈分配一个基本容量，然后在实际的使用过程中， 9  * 当堆栈的空间不够时再倍增存储空间，这个过程所需的时间均摊到每个数10  * 据元素时间为Θ(1)，不会影响操作实现的时间复杂度。11  * @author Laughing_Lz12  * @time 2016年4月6日13  */14 public class StackArray implements Stack {15     private final int LEN = 8;//默认数组的存储大小16     private Object[] elements;//数据元素数组17     private int top;//栈顶指针18     19     public StackArray() {20         this.elements = new Object[LEN];21         this.top = -1;//top为-1时表示空栈22     }23 24     @Override25     public int getSize() {26         return top+1;27     }28 29     @Override30     public boolean isEmpty() {31         if(top < 0){32             return true;33         }else{34             return false;35         }36     }37 38     @Override39     public void push(Object e) {40         if(getSize()>=elements.length){41             expandSpace();42         }43         //++top:因为入栈操作相当于insertAfter，44         //只能在顶点后插入，所以首先将top加1，再放入数据元素45         elements[++top] = e;46     }47 48     @Override49     public Object pop() throws StackEmptyException {50         if(top<0){51             throw new StackEmptyException("错误：栈为空，不可出栈操作");52         }else{53             Object obj = elements[top];54             elements[top--] = null;//先取出原栈顶数据元素，再置空、top减一55             return obj;56         }57     }58     //取栈顶元素59     @Override60     public Object peek() throws StackEmptyException {61         if(getSize()<=0){62             throw new StackEmptyException("错误：栈顶为空");63         }else{64             return elements[top];65         }66     }67     /**68      * 扩充数组长度69      */70     private void expandSpace() {71         Object[] a = new Object[elements.length * 2];72         for (int i = 0; i < elements.length; i++)73             a[i] = elements[i];74         elements = a;75     }76 }

栈的链式存储：

1 package ren.laughing.datastructure.baseImpl; 2  3 import ren.laughing.datastructure.base.Stack; 4 import ren.laughing.datastructure.exception.StackEmptyException; 5 /** 6  * Stack的链式存储 7  * ★此链表为的不含头结点的单链表 8  * @author Laughing_Lz 9  * @time 2016年4月6日10  */11 public class StackLinked implements Stack{12     private SLNode top;//链表首结点引用13     private int size;//栈的大小14     15     public StackLinked() {16         this.size = 0;17 //        this.top = new SLNode(null, null);18         top = null;//这个是否也实例化了呢？和上面是否有区别？19     }20 21     @Override22     public int getSize() {23         return size;24     }25 26     @Override27     public boolean isEmpty() {28         return size==0;29     }30     31     @Override32     public void push(Object e) {33         SLNode node = new SLNode(e, top);//相当于insertBefore 在原栈顶前插入新的数据元素34         top = node;35         size++;36     }37 38     @Override39     public Object pop() throws StackEmptyException {40         if (size<=0){41             throw new StackEmptyException("错误，堆栈为空。");42         }43         Object obj = top.getData();44         top = top.getNext();45         size--;46         return obj;47     }48 49     @Override50     public Object peek() throws StackEmptyException {51         if (size<=0){52             throw new StackEmptyException("错误，堆栈为空。");53         }54         Object obj = top.getData();55         return obj;56     }57 58 }