欢迎光临散文网 会员登陆 & 注册

Java三十一篇：栈

2023-03-07 00:12 作者:小刘Java之路  | 我要投稿


平安春运

栈

栈是一种先进后出的数据结构，最后入栈的元素，最先读取出来。就像向箱子里放书一样，最后放进去的那本书，我们可以最先从箱子里取出来。

img

栈可以分为静态栈(数组实现)和动态栈(链表实现)

Java实现动态栈

通过链表实现栈，我们可以想象有个栈顶节点，当入栈的时候，原先的栈顶节点成为新的节点后继节点，新的节点成为新的栈顶节点。同理，出栈的时候，讲栈顶节点弹出，第二个节点成为新的栈顶节点。

  • 入栈

/**
    * 入栈
    * @param value
    */
   public void push(Object value){
       Node pushedNode = new Node(value);
       pushedNode.next = top;
       top = pushedNode;

       size++;
   }

  • 出栈

/**
    * 出栈
    */
   public Object pop() throws Exception {

       if(size == 0){
           thrownew Exception("空栈异常");
       }

       Node popedNode = top;
       top = top.next;
       size --;

       return  popedNode.data;
   }

  • 返回栈顶元素

/**
    * 返回栈顶元素
    */
   public Object peek() throws Exception {
       if(size == 0){
           thrownew Exception("空栈异常");
       }

       return  top.data;
   }

  • 遍历栈

/**
    * 遍历栈
    */
   public void traverse(){
       Node temp = top;
       while (temp != null){
           System.out.println(""+temp.data);

           temp = temp.next;

       }
   }

Java 实现静态栈

通过数组实现栈，我们可以想象栈顶索引，当入栈的时候，栈顶索引加一，赋值给栈顶。当出栈的时候，返回栈顶的值，并且栈顶索引减一。

publicclass ArrayStatck {

   private Object[] data;
   privateint top;
   privateint maxSize;

   public ArrayStatck(int maxSize) {
       this.maxSize = maxSize;
       this.top = -1;
       data = new Object[maxSize];
   }

   /**
    * 入栈
    * @param value
    */
   public void push(Object value) throws Exception {
       if(top == maxSize-1){
           thrownew Exception("栈满异常");
       }

       data[++top] = value;
   }

   /**
    * 出栈
    * @throws Exception
    */
   public void pop()throws Exception{
       if(top == -1){
           thrownew Exception("栈空异常");
       }

       Object value = data[top--];
   }

   /**
    * 遍历栈
    */
   public void traverse(){
       while (top != -1){
           System.out.println(""+data[top--]);
       }
   }
}

栈的实际需求

  • 请计算表达式：[722-5+1-5+3-3] 的值

  • 请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算，因为我们看这个算式 7 * 2 * 2 - 5，但是计算机怎么理解这个算式的

  • 对计算机而言， 它接收到的就是一个字符串， 我们讨论的是这个问题：栈

img

栈的基本性质

栈的英文为(stack)

栈是一个先入后出(FILO-First In Last Out)的有序列表

栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。 允许插入和删除的一端， 为变化的一端， 称为栈顶(Top)， 另一端为固定的一端， 称为栈底(Bottom)。

根据栈的定义可知， 最先放入栈中元素在栈底， 最后放入的元素在栈顶， 而删除元素刚好相反， 最后放入的元素最先删除， 最先放入的元素最后删除

图解方式说明出栈(pop)和入栈(push)的概念


img

栈的应用场景

子程序的调用： 在跳往子程序前， 会先将下个指令的地址存到堆栈中， 直到子程序执行完后再将地址取出， 以回到原来的程序中。

处理递归调用： 和子程序的调用类似， 只是除了储存下一个指令的地址外， 也将参数、 区域变量等数据存入栈中。

表达式的转换：[中缀表达式转后缀表达式]与求值(实际解决)。

二叉树的遍历。

图形的深度优先(depth 一 first)搜索法。

数组模拟栈

代码思路

maxSize ：栈的大小（数组的大小）

arr ：用来模拟栈的数组

top ：指向当前栈顶元素，初始值为 -1 ，表示栈空

判断栈满：top == maxSize ，即已经到达数组最后一个位置

判断栈空：top == -1

入栈：arr[++top] = arr;

出栈：return arr[top–] ;

img

代码实现

  • 栈的定义

//定义一个 ArrayStack 表示栈
class ArrayStack {
privateint maxSize; // 栈的大小
privateint[] stack; // 数组，数组模拟栈，数据就放在该数组
privateint top = -1;// top表示栈顶，初始化为-1

// 构造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = newint[this.maxSize];
}

// 栈满
public boolean isFull() {
return top == maxSize - 1;
}

// 栈空
public boolean isEmpty() {
return top == -1;
}

// 入栈-push
public void push(int value) {
// 先判断栈是否满
if (isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}

// 出栈-pop, 将栈顶的数据返回
public int pop() {
// 先判断栈是否空
if (isEmpty()) {
// 抛出异常
thrownew RuntimeException("栈空，没有数据~");
}
int value = stack[top];
top--;
return value;
}

// 显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
public void list() {
if (isEmpty()) {
System.out.println("栈空，没有数据~~");
return;
}
// 需要从栈顶开始显示数据
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}

}

  • 测试代码

public static void main(String[] args) {
   // 测试一下ArrayStack 是否正确
   // 先创建一个ArrayStack对象->表示栈
   ArrayStack stack = new ArrayStack(4);
   String key = "";
   boolean loop = true; // 控制是否退出菜单
   Scanner scanner = new Scanner(System.in);

   while (loop) {
       System.out.println("show: 表示显示栈");
       System.out.println("exit: 退出程序");
       System.out.println("push: 表示添加数据到栈(入栈)");
       System.out.println("pop: 表示从栈取出数据(出栈)");
       System.out.println();
       System.out.println("请输入你的选择");
       key = scanner.next();
       switch (key) {
           case"show":
               stack.list();
               break;
           case"push":
               System.out.println("请输入一个数");
               int value = scanner.nextInt();
               stack.push(value);
               break;
           case"pop":
               try {
                   int res = stack.pop();
                   System.out.printf("出栈的数据是 %d\n", res);
               } catch (Exception e) {
                   // TODO: handle exception
                   System.out.println(e.getMessage());
               }
               break;
           case"exit":
               scanner.close();
               loop = false;
               break;
           default:
               break;
       }
   }

   System.out.println("程序退出~~~");
}

  • 程序运行结果

show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
push
请输入一个数
1
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
push
请输入一个数
2
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
push
请输入一个数
3
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
push
请输入一个数
4
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
push
请输入一个数
5
栈满
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
show
stack[3]=4
stack[2]=3
stack[1]=2
stack[0]=1
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
pop
出栈的数据是 4
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
pop
出栈的数据是 3
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
pop
出栈的数据是 2
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
pop
出栈的数据是 1
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择
pop
栈空，没有数据~
show: 表示显示栈
exit: 退出程序
push: 表示添加数据到栈(入栈)
pop: 表示从栈取出数据(出栈)

请输入你的选择

数组模拟栈全部代码

publicclass ArrayStackDemo {

public static void main(String[] args) {
// 测试一下ArrayStack 是否正确
// 先创建一个ArrayStack对象->表示栈
ArrayStack stack = new ArrayStack(4);
String key = "";
boolean loop = true; // 控制是否退出菜单
Scanner scanner = new Scanner(System.in);

while (loop) {
System.out.println("show: 表示显示栈");
System.out.println("exit: 退出程序");
System.out.println("push: 表示添加数据到栈(入栈)");
System.out.println("pop: 表示从栈取出数据(出栈)");
System.out.println();
System.out.println("请输入你的选择");
key = scanner.next();
switch (key) {
case"show":
stack.list();
break;
case"push":
System.out.println("请输入一个数");
int value = scanner.nextInt();
stack.push(value);
break;
case"pop":
try {
int res = stack.pop();
System.out.printf("出栈的数据是 %d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case"exit":
scanner.close();
loop = false;
break;
default:
break;
}
}

System.out.println("程序退出~~~");
}

}

//定义一个 ArrayStack 表示栈
class ArrayStack {
privateint maxSize; // 栈的大小
privateint[] stack; // 数组，数组模拟栈，数据就放在该数组
privateint top = -1;// top表示栈顶，初始化为-1

// 构造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = newint[this.maxSize];
}

// 栈满
public boolean isFull() {
return top == maxSize - 1;
}

// 栈空
public boolean isEmpty() {
return top == -1;
}

// 入栈-push
public void push(int value) {
// 先判断栈是否满
if (isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}

// 出栈-pop, 将栈顶的数据返回
public int pop() {
// 先判断栈是否空
if (isEmpty()) {
// 抛出异常
thrownew RuntimeException("栈空，没有数据~");
}
int value = stack[top];
top--;
return value;
}

// 显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
public void list() {
if (isEmpty()) {
System.out.println("栈空，没有数据~~");
return;
}
// 需要从栈顶开始显示数据
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}

}



标签：

Java三十一篇：栈的评论 (共 条)

分享到微博请遵守国家法律