java实现栈结构

栈的定义

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。

(2)当表中没有元素时称为空栈。

(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。

栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"

最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，

要到最后才能删除。

【示例】元素是以a1，a2，…，an的顺序进栈，退栈的次序却是an，an-1，…，

a1。

2、栈的基本运算

（1）InitStack（S）

构造一个空栈S。

（2）StackEmpty（S）

判栈空。若S为空栈，则返回TRUE，否则返回FALSE。

（3）StackFull（S）

判栈满。若S为满栈，则返回TRUE，否则返回FALSE。

注意：该运算只适用于栈的顺序存储结构。

（4）Push（S，x）

进栈。若栈S不满，则将元素x插入S的栈顶。

（5）Pop（S）

定义堆栈ADT
StackADT
packageStack;
publicinterfaceStackADT{
publicvoidpush(Objectelement);//压栈
publicObjectpop();//出栈
publicbooleanisEmpty();
publicintsize();
publicObjectpeek();//返回栈顶对象的一个引用
publicStringtoString();
}

链式实现：

在栈的一段添加和删除元素，在栈中维护一个指向栈顶的结点和一个count变量指示栈的大小：
privateLinearNodetop;//指向栈顶
privateintcount;//标记栈的大小
每次出栈和压栈在链表的表头：（也可以再表尾，实现方式不一样而已）
top--->元素1--->元素2--->元素3.........
实现（附带测试main）：
LinkedStack
packageStack;
importBag.LinearNode;
//为了重点来实现算法，将异常情况直接打印出然后退出程序，不再声明异常类
publicclassLinkedStackimplementsStackADT{
privateLinearNodetop;//指向栈顶
privateintcount;//标记栈的大小
publicstaticvoidmain(String[]args){
LinkedStackstack=newLinkedStack();
System.out.println("将0到10依次压栈");
for(inti=0;i<10;i++)
stack.push(i);
System.out.println("连续执行5次出栈操作");
for(inti=0;i<5;i++)
stack.pop();
System.out.println("栈为空吗？："+stack.isEmpty());
System.out.println("栈的大小为："+stack.size());
System.out.println("栈顶元素为："+stack.top.getElement());
System.out.println("栈顶元素为："+stack.peek());
}
publicLinkedStack()
{
top=null;
count=0;
}
publicintsize(){
returncount;
}
publicbooleanisEmpty(){
return(size()==0);
}
publicvoidpush(Objectelement){
LinearNodenode=newLinearNode(element);
node.setNext(top);
top=node;
count++;
}
publicObjectpop(){
if(isEmpty())
{
System.out.println("stackisempty!");
System.exit(1);
}
Objectresult=top.getElement();
top=top.getNext();
count--;
returnresult;
}
publicObjectpeek(){
Objectresult=top.getElement();
returnresult;
}
}
运行结果：
将0到10依次压栈
连续执行5次出栈操作
栈为空吗？：false
栈的大小为：5
栈顶元素为：4
栈顶元素为：4

数组实现：

栈底总是数组下标为0的位置，入栈出栈从数组下标的最后一个元素开始：
privateObject[]contents;
privateinttop;//top标记下一个入栈的位置，同时也表示栈的容量大小，跟链式实现的count比较一下！！！
实现（附带测试main）：
ArrayStack
packageStack;
publicclassArrayStackimplementsStackADT{
privateObject[]contents;
privateinttop;//top标记下一个入栈的位置，同时也表示栈的容量大小，跟链式实现的count比较一下！！！
privatestaticintSIZE=10;
publicArrayStack()
{
contents=newObject[SIZE];
top=0;
}
publicvoidexpand(){//借助于申请一个辅助空间,每次扩展容量一倍
Object[]larger=newObject[size()*2];
for(intindex=0;index<top;index++)
larger[index]=contents[index];
contents=larger;
}
publicintsize(){
returntop;
}
publicbooleanisEmpty(){
return(size()==0);
}
publicvoidpush(Objectelement){
//if(isEmpty())
//expand();
if(top==contents.length)
expand();
contents[top]=element;
top++;
}
publicObjectpop(){
if(isEmpty())
{
System.out.println("stackisempty!");
System.exit(1);
}
Objectresult=contents[top-1];
contents[top-1]=null;//出栈
top--;
returnresult;
/*书上这样写简便一点：：：
*top--;
*Objectresult=contents[top];
*contents[top]=null;*/
}
publicObjectpeek(){
Objectresult;
if(isEmpty())
result=null;
else
result=contents[top-1];
returnresult;
}
publicstaticvoidmain(String[]args){
ArrayStackstack=newArrayStack();
System.out.println("将0到24依次压栈，然后连续10次出栈");
for(inti=0;i<25;i++)
stack.push(i);
for(inti=0;i<10;i++)
stack.pop();
System.out.println("栈的大小为："+stack.size());
System.out.println("栈为空吗？："+stack.isEmpty());
System.out.println("栈顶元素为："+stack.peek());
}
}
运行结果：
将0到24依次压栈，然后连续10次出栈
栈的大小为：15
栈为空吗？：false
栈顶元素为：14