用Java代码实现栈数据结构的基本方法归纳
链式实现：
在栈的一段添加和删除元素，在栈中维护一个指向栈顶的结点和一个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
使用集合LinkedList来模拟栈
方法
java的泛型可以让LinkedList模拟存储各种数据类型的栈，包括int，double，String，Object等等，介绍一下几种用到的API接口：
入栈
voidaddFirst(Ee);//将指定元素插入此列表的开头
获取栈顶元素
EgetFirst();//返回此列表的第一个元素
出栈
EremoveFirst();//移除并返回此列表第一个元素
判栈空
booleanisEmpty();//判断栈空
示例代码
importjava.util.LinkedList;
importjava.util.NoSuchElementException;
publicclassSimulateStack{
privateLinkedList<Integer>stack=newLinkedList<Integer>();
publicbooleanisEmpty(){
returnthis.stack.isEmpty();
}
publicvoidpush(intdata){
this.stack.addFirst(data);
}
publicintpop()throwsNoSuchElementException{
returnthis.stack.removeFirst();
}
publicintgetTop()throwsNoSuchElementException{
returnthis.stack.getFirst();
}
publicstaticvoidmain(Stringargs[]){
SimulateStacks=newSimulateStack();
s.push(1);
s.push(2);
s.push(3);
while(!s.isEmpty()){
intdata=s.getTop();
System.out.println(data);
s.pop();
}
}
}