1.1. 栈的顺序存储和链式存储
栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说，它们也是线性结构，
与线性表不同的是它们所支持的基本操作是受到限制的，它们是操作受限的线性表，是一种
限定性的数据结构。
栈（stack ）又称堆栈，它是运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为 栈顶（top） ），栈顶保存的元素称为 栈顶元素。相对的，表的另一端称为栈底（栈底（bottom） 。
Stack接口
public interface Stack {
//返回堆栈的大小
public int getSize();
//判断堆栈是否为空
public boolean isEmpty();
//数据元素 e 入栈
public void push(Object e);
//栈顶元素出栈
public Object pop() throws StackEmptyException;
//取栈顶元素
public Object peek() throws StackEmptyException;
}
1.2. 顺序存储结构实现
顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈
中的数据元素。由于堆栈是一种特殊的线性表，因此在线性表的顺序存储结构的基础上，选
择线性表的一端作为栈顶即可。根据数组操作的特性，选择数组下标大的一端，即线性表顺
序存储的表尾来作为栈顶，此时入栈、出栈等操作可以在Ο(1)时间完成。
由于堆栈的操作都在栈顶完成，因此在顺序栈的实现中需要附设一个指针 top 来动态的
指示栈顶元素在数组中的位置。通常 top 可以用栈顶元素所在数组下标来表示，top= -1 时表
示空栈。
堆栈在使用过程中所需的最大空间很难估计，因此，一般来说在构造堆栈时不应设定堆
栈的最大容量。一种合理的做法和线性表的实现类似，先为堆栈分配一个基本容量，然后在
实际的使用过程中，当堆栈的空间不够时再倍增存储空间，这个过程所需的时间均摊到每个
数据元素时间为Θ(1)，不会影响操作实现的时间复杂度
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() {
return top < 0;
}
/**
*对元素入栈
*/
@Override
public void push(Object e) {
if (getSize()>=elements.length){
expandSpace();
elements[++top]=e;
}
}
private void expandSpace() {
Object[] a = new Object[elements.length*2];
for (int i=0; i<elements.length; i++)
a[i] = elements[i];
elements = a;
}
/**
*栈顶元素出栈
*/
@Override
public Object pop() throws StackEmptyException {
if (getSize()<1){
throw new StackEmptyException("错误，堆栈为空");
}
Object obj = elements[top];
elements[top--]=null;
return obj;
}
@Override
public Object peek() throws StackEmptyException {
if (getSize()<1)
throw new StackEmptyException("错误，堆栈为空。");
return elements[top];
}
}
1.3. 栈的链式存储实现
链栈即采用链表作为存储结构实现的栈。当采用单链表存储线性表后，根据单链表的操
作特性选择单链表的头部作为栈顶，此时，入栈、出栈等操作可以在Ο(1)内完成。由于堆
栈的操作只在线性表的一端进行，在这里使用带头结点的单链表或不带头结点的单链表都可
以。使用带头结点的单链表时，结点的插入和删除都在头结点之后进行；使用不带头结点的
单链表时，结点的插入和删除都在链表的首结点上进行。
public class StackSLinked implements Stack {
private SLNode top; //链表首节点引用
private int size;
public StackSLinked() {
top=null;
size=0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public void push(Object e) {
SLNode q=new SLNode(e,top);
top=q;
size++;
}
@Override
public Object pop() throws StackEmptyException {
if (size<1){
throw new StackEmptyException("错误，堆栈为空");
}
Object obj = top.getData();
top=top.getNext();
size--;
return obj;
}
@Override
public Object peek() throws StackEmptyException {
if (size<1){
throw new StackEmptyException("错误，堆栈为空");
}
Object obj = top.getData();
return obj;
}
}
