数据结构——Java实现顺序栈

时间:2021-08-20 10:27:10

一、分析

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

  顺序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。

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

    1、初始化顺序栈

    2、销毁顺序栈

    3、清空顺序栈

    4、检测顺序栈是否为空

    5、返回顺序栈中的元素个数

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

    7、向顺序栈顶中压入元素

    8、从顺序栈顶中弹出元素

    9、从栈底到栈顶遍历顺序栈

  在Java中,可以将整个顺序栈定义成一个类,类中定义有一个数组类型的属性表示顺序存储结构来存储元素,再定义一个int类型的属性top来作为指针指示栈顶元素在数组中的位置,顺序栈的基本操作则定义成类的方法。初始化顺序栈即实例化类,销毁顺序栈即销毁实例化出来的对象。

二、实现

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

 1 class InitStack{
 2     
 3     private int [] stack = null;      //存储元素
 4     
 5     private int top = 0;           //指示栈顶元素在顺序栈中的位置
 6     
 7     public InitStack(int max) {       //初始化自定义大小的顺序栈
 8         this.stack = new int[max];
 9     }
10 }

2、清空顺序栈

1 public void clearStack() {
2     this.top = 0;          //直接令栈顶指针指向栈底即可
3 }

3、检测顺序栈是否为空

1 public boolean stackEmpty() {
2     if(this.top == 0) {        //检测栈顶指针是否指向栈底即可
3         return true;
4     }else {
5         return false;
6     }
7 }

4、返回顺序栈中的元素个数

1 public int stackLength() {
2     return this.top;        //栈顶指针的值即代表了元素个数
3 }

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

 1 public int [] getTop() {
 2 
 3     if (this.top == 0) {        //如果顺序栈为空,则返回空
 4         return null;
 5     }
 6 
 7     int [] i = new int[1];
 8     i[0] = stack[this.top - 1];    //获取栈顶元素
 9 
10     return i;
11 }

6、向顺序栈顶中压入元素

 1 public boolean push(int value) {
 2 
 3     if(this.top == this.stack.length) {    //判断顺序栈是否已满
 4         return false;
 5     }
 6 
 7     this.stack[this.top] = value;        //压入元素
 8     this.top++;                  //栈顶指针加一
 9     return true;
10 }

7、从顺序栈顶中弹出元素

 1 public int [] pop() {
 2 
 3     if (this.top == 0) {      //判断顺序栈是否已空
 4         return null;
 5     }
 6 
 7     int [] i = new int[1];
 8     this.top--;            //栈顶指针减一
 9     i[0] = stack[this.top];    //获取栈顶元素
10     return i;
11 }

8、从栈底到栈顶遍历顺序栈

 1 public String stackTraverse() {            //通过输出顺序栈元素来表示遍历
 2 
 3     String s = "";                    //存储要输出的元素
 4 
 5     for (int i = 0; i < this.top; i++) {      //循环遍历
 6         s += this.stack[i] + "、";
 7     }
 8 
 9     if(s.length() == 0) {               //如果未获取到元素,返回空字符串
10         return s;
11     }
12 
13     return s.substring(0,s.length() - 1);     //除去最后一个顿号后返回
14 }

三、小结

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