文章目录栈的应用场景与介绍栈的介绍出入栈的概念（如图所示）栈的应用场景数组模拟栈的思路分析图代码实现栈实现综合计算器要求思路分析代码实现
栈的应用场景与介绍
计算式：7*2*2-5+1-5*3-3=?
计算机底层是如何运算得到结果的？注意不是简单的把算是列出运算，因为我们看这个算式722-5，但是计算机怎么理解这个算式的（对计算机而言，它接收到的就是一个字符串），我们讨论的是这个问题。–>栈
栈的介绍
栈的英文为（stack）
栈是一个先入后出的（FILO-First In Last Out）的有序列表
栈（stack）是限制线性表中元素插入和删除只能在线性表的同一端进行的一种特殊线性表。允许
【Java数据结构与算法】栈及经典应用
在编程领域，数据结构与算法是至关重要的基础知识，其中栈（Stack）是一种基本且广泛使用的数据结构。本文将深入探讨栈的原理、概念及其在Java中的实现，并通过实例展示其应用场景。
栈的介绍：
栈，英文名为stack，是一个遵循“先进后出”（FILO-First In Last Out）原则的有序列表。它是一种特殊的线性表，只允许在表的一端（栈顶）进行插入和删除操作。栈顶元素是最新的，而栈底元素是最早被插入的。当元素被添加到栈中时，称为入栈；当元素被移除时，称为出栈。栈的这种特性使得它在很多问题中表现出高效性和便利性。
出入栈的概念：
在栈中，入栈操作是将一个元素添加到栈顶，而出栈操作则是从栈顶移除一个元素。以图示为例，入栈时元素移动到栈顶，出栈时栈顶元素被弹出。这种操作方式使得栈在处理需要按顺序进行的逆序任务时特别有用。
栈的应用场景：
1. 子程序的调用：在程序执行过程中，每当调用一个子程序，系统会将返回地址压入栈中，待子程序执行完毕后，再从栈顶取出地址返回到调用点继续执行。
2. 处理递归调用：递归调用同样涉及到栈的使用，除了存储返回地址，还会保存函数参数和局部变量。
3. 表达式的转换与求值：在计算中缀表达式时，可以将其转化为后缀表达式（也称逆波兰表示法），然后利用栈进行求值。例如，计算表达式7*2*2-5+1-5*3-3，计算机需要理解并处理这个字符串形式的算式，通过栈可以实现从左到右依次读取，遇到操作符时与栈顶的操作数进行运算，然后再将结果压入栈中。
4. 二叉树的遍历：在深度优先搜索（DFS）中，栈可以用来跟踪尚未访问的节点，从而实现前序、中序或后序遍历。
5. 图形的深度优先搜索：在图论中，深度优先搜索法用于遍历或搜索图的所有节点，每次从一个节点出发，沿着某条边深入到图的深处，直到到达叶子节点或回溯到无新节点可走为止，栈在这里起到记录路径的作用。
Java中的栈实现：
在Java中，我们可以使用`java.util.Stack`类来直接操作栈，或者使用数组模拟栈。以下是一个使用数组模拟栈的简单Java代码实现：
```java
package DataType;
import java.util.Scanner;
public class ArrayStackDemo {
public static void main(String[] agrs) {
// 创建一个数组栈对象
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("请输入你的选择：");
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.println("出栈的数据是：" + res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序已退出！");
}
}
// 定义一个数组栈类
class ArrayStack {
private int maxSize; // 栈的最大容量
private int[] stack; // 数组，用于模拟栈
private int top = -1; // top表示栈顶，初始化为-1
// 构造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
// 其他栈操作方法...
}
```
以上代码展示了如何使用数组实现一个简单的栈，包括入栈、出栈、显示栈内元素等功能。通过这样的实现，我们可以更直观地理解栈的工作原理以及其在实际问题中的应用。
