数据结构-Stack和栈

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");//获取栈中有效元素的个数-->4System.out.println(stack.size());//获取栈顶元素-->hajimi  遵循后进先出System.out.println(stack.peek());//peek方法不会改变栈中的元素个数System.out.println(stack.size());//出栈String deleteElem=stack.pop();//获取栈中有效元素的个数-->3System.out.println(stack.size());//判断栈是否为空-->falseSystem.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));
}