什么是栈结构
栈结构是从数据的运算来分类的,也就是说栈结构具有特殊的运算规则.而从数据的逻辑结构来看,栈结构是一种线性结构,如果从数据的存储结构来进一步划分,栈结构包括两类:
- 顺序栈结构:即使用一组地址连续的内存单元一次保存栈中的数据,在程序中,可以定义一个指定大小的结构数组来作为栈,序号为0的元素就是栈底,再定义一个变量top保存栈顶的序号就可以了.
- 链式栈结构:即使用链表形式保存栈中的元素的值,链表首部(head引用所指向的元素)为栈顶,链表尾部(指向地址为null)为栈尾.
image
典型的栈结构,可以从上图可以看出,在栈结构中只能在一端进行操作,也就是栈顶,另一端是栈尾,保存和取出数据都从栈顶进行操作.这种操作叫(Last in First out ,LIFO)的原则进行处理的.
看到栈的这种先进后出,我们首先想到的是什么呢,子弹夹,对不对,子弹夹在放进子弹的时候就是这样,从上面一颗一颗的,这个叫入栈,取出子弹就是一颗一颗的弹出来,这个叫出栈!
- 入栈(Push):将数据保存到栈顶的操作,进行入栈操作前,先修改栈顶引用,使其向上移动一个元素位置,然后将数据保存到栈顶引用所指的位置.
- 出栈(Pop):将栈顶的数据弹出的操作,通过修改栈顶引用的,使其指向栈中的下一个元素.
准备数据
static final int MAXLEN = 50;
class DATA3
{
String name;
int age;
}
class StackType
{
static final int MAXLEN = 50;
DATA3 [] data = new DATA3[MAXLEN+1];
int top;
}
在上述代码中,我们定义栈结构的最大长度MAXLEN,栈结构的数据元素DATA3,我们定义了两个属性,一个名字,一个年龄.
StackType是我们定义的栈结构,其中data数组是我们存放栈的数据元素的数组,而top则是指向的栈结构的栈顶,在数组中是从0开始存储数据的,但是我们这里会从1这个位置存储数据.下标0的位置不使用.
初始化栈结构
在使用顺序栈之前,首先要创建一个空的顺序栈,也就是初始化一个顺序栈.有如下步骤:
- 按符号常量SIZE指定的大小申请一片内存空间,用来保存栈中的数据
- 设置栈顶引用的值为0,表示一个空栈
public StackType SYInit(){
StackType p;
if((p=new StackType())!=null){ //申请内存
p.top = 0; //设置栈顶为0
return p; //返回栈引用
}
return null;
}
判断是否是空栈
判断是否是空栈可以直接通过判断栈顶引用top是否为0就可以了知道了
public boolean STIsEmpty(StackType s){
if(s!=null){
return s.top == 0;
}
return false;
}
判断是否是满栈
判断是否是漫展就是判断栈顶引用top是否等于了它的最大值MAXLEN
public boolean SLIsFull(StackType s){
if(s!=null){
return s.top==MAXLEN;
}
return false;
}
清空栈
清空栈我们只需要把栈顶的引用top设置为0就可以了
public void STClear(StackType s){
if(s!=null){
s.top=0;
}
}
释放空间
在清空栈的方法里面,我们只是把栈顶设置为0,并没有释放空间,只需要把栈的引用指向null
public void STFree(StackType s){
if(s!=null){
s = null;
}
}
入栈
上面都是一些辅助操作,之所以把它们列在上面是因为我们下面有可能会用到它们,这里就是主要操作了.
入栈:把数据元素保存到栈结构中,主要操作如下:
1.首先判断栈是否已满,如果不满,则入栈
2.设置top=top+1,(栈顶引用加1,指向入栈地址)
3.将入栈元素指向top所在的位置
public int STPush(StackType s,DATA3 data){
if(SLIsFull(s)){ //判断是否已经满了
System.out.println("你的弹夹已经满了! \n");
return 0;
}
s.data[++s.top] = data; //将元素保存到++s.top的位置
return 1;
}
出栈
出栈是栈的基本操作,与入栈相反,主要是从栈顶弹出一个操作,步骤如下:
1.首先判断是否已经是个空的了
2.将栈顶引用top所指向的元素返回
3.栈顶引用top减1,也就是指向下面的一个元素
public DATA3 STpop(StackType s){
if(STIsEmpty(s)){
System.out.println("你的弹夹没有子弹了!");
return null;
}
return s.data[s.top--];
}
读取结点
读取栈的结点,因为栈的操作都是从一端读取,所以读取结点也是栈顶结点的数据,和出栈不同的是,这里只读取不删除
而出栈是弹出,就没有了
public DATA3 STPeek(StackType s){
if(STIsEmpty(s)){
System.out.println("你的弹夹没有子弹了!");
}
return s.data[s.top];
}
以上就是栈结构的java代码实现
网友评论