一、基本概念 栈是一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(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(){ |