数据结构——Java实现链栈

一、分析

  栈是限定仅在表的一端进行插入或删除操作的线性表,对于栈来说,操作端称为栈顶,另一端则称为栈底,栈的修改是按照后进先出的原则进行的,因此又称为后进先出的线性表。

  链栈是指采用链式存储结构实现的栈,通常用单链表来表示,在单链表表头进行栈的操作。

  一个标准的链栈具有如下的基本操作:

    1、初始化链栈

    2、销毁链栈

    3、清空链栈

    4、检测链栈是否为空

    5、返回链栈中的元素个数

    6、返回链栈的栈顶元素,不修改栈指针

    7、向链栈顶压入元素

    8、从链栈顶弹出元素

    9、从栈底到栈顶遍历链栈

  在Java中,我们可以将链栈中的每个结点统一定义成一个类,类中包含有“元素值”和“下一地址”两个属性。链栈的基本操作即为类的方法,每压入一个元素即生成一个结点对象。为了操作方便,我们附设一个头结点,头结点不存储值,它保存的是链栈的地址。这样,初始化链栈即生成头结点,销毁链栈即销毁头结点。

二、实现

1、定义类属性和构造函数

 class InitStack{

     private int [] data = new int[1];    //存储元素值

     private InitStack nextStack;       //存储下一地址

     public InitStack() {            //用于生成头结点
this.data = null;
this.nextStack = null;
} public InitStack(int data) {      //用于生成链栈结点
this.data[0] = data;
this.nextStack = null;
}
}

2、清空链栈

 public void clearStack() {
this.nextStack = null;     //令头结点的下一地址为空,链栈即被清空
}

3、检测链栈是否为空

 public boolean stackEmpty() {
if(this.nextStack == null) {   //判断头结点的下一地址是否为空即可
return true;
}
return false;
}

4、返回链栈中的元素个数

 public int stackLength() {

     InitStack theStack = this.nextStack;    //获取头结点的下一地址即链栈的第一个结点
int i = 0;                   //初始化计数器 for (i = 0; theStack != null; i++) {   //循环判断如不为空,则计数器加一
theStack = theStack.nextStack;
}
return i;
}

5、返回链栈的栈顶元素,不修改栈指针

 public int [] getTop() {

     if(this.nextStack == null) {      //判断是否为空栈
return null;
} return this.nextStack.data;
}

6、向链栈顶压入元素

 public void push(int input) {
InitStack initStack = new InitStack(input);
initStack.nextStack = this.nextStack;
this.nextStack = initStack;
}

7、从链栈顶弹出元素

 public int [] pop() {

     if (this.nextStack == null) {            //判断栈是否为空
return null;
} int [] i = this.nextStack.data;          //获取栈顶元素值
this.nextStack = this.nextStack.nextStack;   //删除栈顶元素
return i;
}

8、从栈底到栈顶遍历链栈

 public String stackTraverse() {          //这里通过输出栈元素值来表示遍历

     InitStack theStack = this.nextStack;
String s = ""; while(theStack != null) {          //循环遍历栈
s = theStack.data[0] + "、" + s;
theStack = theStack.nextStack;
} if(s.length() == 0) {            //如果未获得值,则直接输出空字符串
return s;
}
return s.substring(0,s.length() - 1);  //除去最后的顿号后返回字符串

三、小结

  以上就是链栈用Java的实现,由于只定义了整数的数组,因此只能操作整数数据,但链栈的基本思想都已实现。

四、纠正

  隔了一段时间又回来看代码,猛地发现这段代码其实还不够完善。(⊙x⊙;)

  将链栈的基本操作定义成了InitStack类的方法,实例化结点时,会使每个结点都拥有这些方法,然而其实只有头结点需要这些方法,其他结点都不需要。

  因此可以将InitStack类定义成头节点类,而其他节点定义成头节点的内部类,这样,就只有头节点可以操作其他节点。

  由于要修改的地方太多,这里我就不修改了,放在这里提醒自己。(就是因为懒……(><))

上一篇:Application.Exit()结束程序,但线程还在的解决方法


下一篇:java基础3_循环语句,数组