栈是一种后进先出或先进后出的线性表。
1.1栈的抽象数据类型描述
栈也是由n个数据元素所构成的有限序列，其数据元素的类型可以任意，但只要是同一种类型即可。根据栈的特性，定义在栈的抽象数据元素类型中的基本操作如下。
（1）置栈空操作clear（）：将一个已经存在的栈置成空栈；
（2）判栈空操作isEmpty（）：判断一个栈是否为空，若栈为空，则返回true；否则返回null。
（3）求栈中数据元素个数操作length（）：返回栈中数据元素的个数。
（4）去栈顶元素操作peek（）：读取栈顶元素并返回其值，若栈为空，则返回null。
（5）入栈操作push（）：将数据元素x压入栈顶。
（6）出栈操作pop（）：删除并返回栈顶元素。
栈的抽象数据类型用Java接口描述如下：
public interface IStack {
public void clear();//清空
public boolean isEmpty();//判空
public int length();//长度
public Object peek();//取栈顶元素
public void push(Object x)throws Exception;//入栈
public Object pop();//出栈
}
1.2栈的基本操作实现
top指向的是栈顶元素储存位置的下一个储存单元的位置，其值就是栈顶元素在数组中的储存位置编号加1（数组中位置的编号是从0开始），所以对于顺序栈的置空、判空、求长度、和取栈顶元素操作的实现，只要抓住以下几个关键问题，理解起来就非常简单。
（1）顺序栈为空的条件是top==0。
（2）顺序栈为满的条件是top==stackElem.length。
（3）栈的长度为top。
（4）栈顶元素就是以top-1为下标的数组元素satckElem[top-1]。
public class SqStack implements IStack {
public Object[] stackElem;//对象数组
private int top;//在非空栈中，top始终指向栈顶元素的下一个储存位置；当栈为空时，top值为0.
public SqStack(int maxSize){
top=0;//初始化top为0
stackElem=new Object[maxSize];//为栈分配maxSize个储存单位
}
public void clear() {//清空
top=0;
}
public boolean isEmpty() {//判空
return top==0;
}
@Override
public int length() {//元素个数
return top;
}
@Override
public Object peek() {//取栈顶元素
if(! isEmpty())
return stackElem[top-1];//返回栈顶元素
else
return null;
}
@Override
public void push(Object x) throws Exception {//入栈
if(top==stackElem.length)
throw new Exception("栈已满");
else
stackElem[top++]=x;//先将新的数据元素x压入栈顶，再top增1
}
@Override
public Object pop() {//出栈
if(isEmpty())//栈空
return null;
else//栈非空
return stackElem[--top];
}
public void display(){
for(int i=top-1;i>=0;i--)
System.out.print(stackElem[i].toString()+"");
}
