java实现栈

栈的定义及抽象数据类型：     栈（Stack）：又称堆栈，它是运算受限的线性表，其限制是仅仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入，查找，删除等操作。表中进行插入删除操作的一端称为栈顶。     栈顶保存的元素称为栈顶元素。他有一个特性就是后进先出。     

    栈的实现方法也包括顺序存储实现以及链式存储实现。

定义栈操作的接口：

package 数据结构; public interface Stack { //返回堆栈的大小 public int getSize(); //判断堆栈是否为空 public boolean isEmpty(); //数据元素e入栈 public void push(Object c); //栈顶元素出栈 public Object pop(); //取栈顶元素 public Object peek(); } 定义栈的异常：

package 数据结构; /** * 堆栈的异常 * @author acer * 当栈为空时执行出栈或者获取栈顶元素的操作，抛出此异常 */ public class StackEmptyException extends RuntimeException{ public StackEmptyException(String err) { super(err); } } 顺序存储的实现：

package 数据结构; /** * 栈的顺序存储结构的实现 * @author acer * 利用一组地址连续的存储单元依次存放堆中的元素数据。同线性表的实现类似，先为栈分配一定的空间，如果空间不足，再进行扩容 */ public class StackArray implements Stack{ private final int LEN = 8; private Object[] elements; private int top;//栈顶指针 public StackArray() { top = -1; elements = new Object[LEN]; } @Override public int getSize() { return top+1; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return top == -1; } @Override public void push(Object c) { if(getSize()>= elements.length) expandSpace(); elements[++top] = c; } private void expandSpace() { Object a[] = new Object[LEN*2]; for(int i=0;i<getSize();i++){ a[i] = elements[i]; } elements = a; } @Override public Object pop() { if(getSize() < 1) throw new StackEmptyException("栈为空"); Object obj = elements[top]; elements[top --] = null; return obj; } @Override public Object peek() { if(getSize() < 1) throw new StackEmptyException("错误，堆栈为空"); return null; } } 链式存储的实现：

package 数据结构; import 线性表.linkedlist.SLNode; /** * 栈的链式存储结构实现 * @author acer * */ public class StackSLinked implements Stack{ private SLNode top; private int size; public StackSLinked() { top = null; size = 0; } @Override public int getSize() { // TODO Auto-generated method stub return size; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return size == 0; } @Override public void push(Object c) { // TODO Auto-generated method stub SLNode node = new SLNode(c,top); top = node; size++; } @Override public Object pop() { if(size < 1) throw new StackEmptyException("错误：堆栈为空"); Object o = top.getData(); top = top.getNext(); size--; return o; } @Override public Object peek() { if(size < 1) throw new StackEmptyException("错误：堆栈为空"); return top.getData(); } } 以上便是栈的俩种实现方法，这俩种的效率是接近的。