[教程]Java操作栈

2014-06-24 12:03:03 -0400
 一、基本概念
栈是一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。 栈也称为先进后出表。
栈可以用来在函数调用的时候存储断点,做递归时要用到栈!
栈的模型
二、基本算法
1、进栈(PUSH)算法
①若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则作②);
②置TOP=TOP+1(栈指针加1,指向进栈地址);
③S(TOP)=X,结束(X为新进栈的元素);
2、退栈(POP)算法
①若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈, 空则下溢;不空则作②);
②X=S(TOP),(退栈后的元素赋给X):
③TOP=TOP-1,结束(栈指针减1,指向栈顶)。
三、栈的实现
栈分顺序栈和链式栈,下面程序介绍了顺序栈的实现。
java栈的实现
public class MyStack {  //定义一个堆栈类
int[] array;             //用int数组来保存数据,根据需要可以换类型
int s_size;              //定义堆栈的宽度
public MyStack(int i){    //定义一个带参数构造器
array=new int[i];         //动态定义数组的长度
s_size=0;                     //堆栈的默认宽度为0
}
public MyStack(){          //默认构造器
this(50);                     //默认构造器可容纳50个元素
}
public void push(int i){ //压栈
array[this.s_size]=i;
this.s_size++;
}
public int pop(){     //从堆栈中取元素,从栈顶开始取
if(this.s_size!=0){
int t=array[s_size-1];        //用中间变量保存栈顶的元素
array[s_size-1]=0;              //取完元素该位置设为0
s_size--;                            //栈的大小减1
return t;                             //返回栈顶元素
}else{
System.out.println("This stack is empty");    //当栈为空时显示提示信息,返回0
return 0;
}
}
public boolean isEmpty(){                   //判断栈是否为空
return this.s_size==0;
}
public int top(){                                 //从栈顶取值,功能和 pop() 方法一样
if(!this.isEmpty()){
int t=array[this.s_size-1];
array[this.s_size-1]=0;
this.s_size--;
return t;
}else{
System.out.println("This stack is empty!");
return 0;
}
}
public void printAll(){                 //打印出堆栈中的所有元素的值,不是取出,元素依然在堆栈里
if(!this.isEmpty()){
for(int i=this.s_size - 1;i>=0;i--){
System.out.println(array[i]);
}
}
}
//下面是测试代码
public static void main(String[] args){
MyStack stack=new MyStack();
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
//System.out.println(stack.isEmpty());
stack.printAll();
System.out.println("===========");
System.out.println(stack.top());
System.out.println(stack.top());
System.out.println(stack.top());
System.out.println(stack.top());
System.out.println(stack.top());
}
}
转自:360doc
«Newer      Older»

----Comments(3)----
追梦小窝 (@yzm) | @ at 2014-07-23 12:10:
路过留名
落叶似秋 (@zyw8) | @ at 2014-06-24 23:34:
→_→
@ny | @ at 2014-06-24 22:45:
ㄟ(▔,▔)ㄏ
Comment:
Name:

Back to home

Subscribe | Register | Login | 中文 | N