1.栈
1.1什么是栈
栈是一种特殊的线性表，只允许在固定的一段进行插入和删除操作，进行插入和删除操作的一段称为栈顶，另一端称为栈底。
栈中的数据元素遵顼后进先出LIFO（Last In First Out）的原则，就像一叠盘子，只能在顶部添加或移除盘子。
压栈：栈的插入操作叫做压栈/进栈/入栈，新插入的元素在栈顶。
出战：栈的删除操作叫做出栈，要删除的 元素在栈顶。
从图上观察发现：无论是插入还是删除操作，栈底的位置不发生变化，但是栈顶的位置会随插入或删除操作而发生变化。
1.2栈的常用方法
在Java标准库中提供了java.util.Stack（栈的实现类），此处的常用方法指的是Stack的常用方法。
Stack的常用方法如下表所示：
| 方法 | 解释 |
| Stack() | 构造方法，构造一个空的栈 |
| E push(E,e) | 将元素e入栈，并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素的个数 |
| boolean empty() | 检验栈是否为空 |
注意：
pop()是删除元素，并返回删除（删除前的栈顶元素）的元素
peek()是获取栈顶元素并返回，不进行出栈操作
常用方法的代码演示：
public class Test {
public static void main(String[] args) {
Stack<String> stack=new Stack<>();
//入栈
stack.push("My");
stack.push("name");
stack.push("is");
stack.push("hajimi");
//获取栈中有效元素的个数-->4
System.out.println(stack.size());
//获取栈顶元素-->hajimi 遵循后进先出
System.out.println(stack.peek());
//peek方法不会改变栈中的元素个数
System.out.println(stack.size());
//出栈
String deleteElem=stack.pop();
//获取栈中有效元素的个数-->3
System.out.println(stack.size());
//判断栈是否为空-->false
System.out.println(stack.isEmpty());
}
}2.Stack
2.1什么是Stack
Java提供了多种方式来实现栈，包括使用java.util.Stack类，使用Deque接口，或者手动实现栈。
java.util.Stack是Java标准库中提供的一个栈实现类。它继承自Vector类，是一个线程安全的栈实现。
2.2 Stack的特点
1.线程安全：
由于Stack继承自Vector，它的所有方法都是同步的(线程安全的)。
2.动态扩容：
Stack的底层是Vector，它会根据需要进行动态扩容。
这是Vector的动态扩容方法的原码：
2.3 Stack的局限性
虽然Stack提供了很方便的栈操作，但仍存在一些局限性：
1.继承自Vector：Stack继承自Vector，意味着它继承了一些与栈无关的方法，可能会导致误用
2.性能问题：由于Stack是线程安全的，它的同步机制可能会导致性能的下降，尤其是单线程环境中
2.4实现一个Stack
Stack的底层是Vector，而Vector的底层是数组，接下来我们来编写自己的"Stack"。
代码编写：
package datastructure;
import java.util.Arrays;
public class MyStack2 {
//用来存放栈中的元素
private int[] elem;
//计算栈中有效元素的个数
private int usedSize;
//默认初始容量
private static final int DEFAULT_SIZE=10;
public MyStack2(){
this.elem=new int[DEFAULT_SIZE];
}
//判断栈是否已满
private boolean isFull(){
return elem.length==usedSize;
}
//判断栈是否为空
private boolean isEmpty(){
return usedSize==0;
}
//元素入栈方法
public void push(int val){
//判断栈是否已满，如果已满进行扩容
if(isFull()){
Arrays.copyOf(elem,2*elem.length);
}
//将元素压入，并将有效元素的个数加一
elem[usedSize++]=val;
}
//元素出栈操作
public int pop(){
if(isEmpty()){
System.out.println("栈中没有元素，无法进行出栈操作");
return Integer.MAX_VALUE;
}
//获取栈顶元素，即要删除的元素
int deleteElem=elem[usedSize-1];
usedSize--;
return deleteElem;
}
//获取栈顶元素
public int peek(){
if(isEmpty()){
System.out.println("栈为空，无法获取栈顶元素");
return Integer.MAX_VALUE;
}
return elem[usedSize-1];
}
//计算栈中元素的个数
public int size(){
return usedSize;
}
}
对上述的代码进行运行测试：
public class Test {
public static void main(String[] args) {
MyStack2 myStack2=new MyStack2();
myStack2.push(1);
myStack2.push(2);
myStack2.push(3);
myStack2.push(4);
myStack2.push(5);
System.out.println("当前栈中元素的个数:"+myStack2.size());
System.out.println("获取栈顶元素:"+myStack2.peek());
System.out.println("进行出栈:"+myStack2.pop());
System.out.println("当前栈中元素的个数:"+myStack2.size());
System.out.println("获取栈顶元素:"+myStack2.peek());
}
}运行结果：
3.栈，虚拟机栈，栈帧
概念区分：栈，虚拟机栈和栈帧
栈：一种数据结构，遵循后进先出（LIFO）的原则，允许在栈顶进行元素的插入和删除操作，常用于括号匹配，表达式求值，深度优先搜索等场景。
虚拟机栈：Java虚拟机（JVM）运行时数据区的一部分，用于存储方法调用，局部变量。每个线程都具有一个自己的虚拟机栈，虚拟机栈中存储的是栈帧
栈帧：是虚拟机栈中的一个条目，用于存储方法调用的相关信息。每个方法调用都会创建一个栈帧，并将其压入虚拟机栈，方法结束后，栈帧会被弹出。
4.栈的应用-逆波兰表达式求值
4.1 什么是逆波兰表达式
逆波兰表达式，也称后缀表达式，是一种特殊的算数表达式表示方式。在逆波兰表达式中，操作符位于操作数之后，这种表达方式的优点式不需要括号来表示操作的优先级，从而简化了表达式的解析和计算
4.2 逆波兰表达式的特点
1.操作符在操作数之后：例如，普通的表达式 （中缀表达式）5 - 2 在逆波兰表达式中表示为 5 2 -
2.无需括号：由于操作符位置明确，不需要括号来表示优先级
3.易于计算：可以使用栈这种数据结构计算表达式的值
4.3 如何用栈解决逆波兰表达式求值
我们知道栈遵循后入先出（Last In First Out）的原则，逆波兰表达式中操作符位于操作数之后，我们可以根据这两个特点对元素进行出栈和入栈操作。
1.先初始化一个空栈
2.从左向右扫描表达式，如果遇到操作数就将其压入栈中，如果遇到操作符，就从栈中弹出两个元素，进行计算，并将计算的结果压入栈中
3.表达式扫描完成后，栈顶元素即为计算的结果
假设传递的参数是一个数组：tokens=["2","1","+","3","*"]
将其转为中缀表达式：(2+1)*3=9
代码编写：
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack();
for (int i = 0; i < tokens.length; i++) {
String token = tokens[i];
if (isNumber(token)) {
stack.push(Integer.parseInt(token));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();
}
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
