补充
一脚油门立马拉开你跟我的差距 所以也要继续努力呀！
- 注意：Iterator只能单向移动，但是ListIterator可以双向移动（即：向前向后遍历）
- 顺序存储：底层是数组 ； 链式存储：底层是链表。
一起加油加油！-for u and me
一、栈(Stack)
1. 概念
- 栈的重要特征：先进后出！！
- 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
- 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈。出数据在栈顶。
- 栈顶和栈底图示：（操作都是从栈顶）
2. 栈的使用
栈的方法：
Stack是继承Vector的，所以即使Stack中没有size()方法，但是其可以继承父类Vector中的成员方法。（所以Stack同样可以调用size方法）
实例：（注意看注释）
public static void main(String[] args) {
Stack<Integer> s = new Stack<>(); //注意这里的定义格式
s.push(1);
s.push(2);
s.push(3);
s.push(4); // 进行压栈操作
System.out.println(s.size()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4 （但是不删除）
s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3 （会将栈顶元素删除）
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
if(s.empty()){
System.out.println("栈空");
}else{
System.out.println(s.size());
}
}
3. 栈的模拟
- 相关思路以及知识点：
栈的底层其实就是一个数组
- 创建变量：数组、以及usedSize：记录当前栈中存储的有效数据个数，也可以作为当前可以存放数据元素的下标
- 给数组默认大小+使用构造方法进行数组初始化
- push（）压栈方法：判断栈是否已满（写一个方法isFull + 是否需要扩容）、存放元素且自增usedSize
- pop（）出栈方法-即删除栈顶元素：如果是引用类型，存放的是地址，删除则置空就行；但是如果是基本数据类型呢？：usedSize–; 但是要注意要进行判空操作：看usedSize是否为0
- peek()拿到栈顶元素：单纯返回栈顶元素就行（但是同样需要进行判空操作）
- getUsedSize（）：拿到有效长度
以上讲的是栈的顺序存储，栈也是可以链式存储的。
顺序存储：出栈和入栈的时间复杂度（执行次数）都是O(1)
如果是单向链表存储为栈：
尾插法：入栈O(n) 出栈O(n)
头插法：入栈O(1):相当于从头结点插入,必须遍历链表
出栈O(1)：相当于删除头结点
所以：要想单向链表作为栈，就是需要进行头插，时间复杂度也是最低的
如果双向链表存储为栈：
从头出入栈以及从尾结点出入栈都ok 时间复杂度均为O(1)
- 代码：
- MyStack.java
// 模拟实现Stack的功能
// 为什么是使用数组进行操作：因为Stack的底层是数组，所以操作就在数组上进行！！！
import java.util.Arrays;
public class MyStack {
// 新建数组、以及默认大小 + 有效大小
public int[] array;
public static int DEFAULT_SIZE = 3;
public int usedSize;
// 使用构造方法进行数组初始化
public MyStack() {
//int[] array = new int[DEFAULT_SIZE];
// 其实是进行初始化（以数组名来初始化）
array = new int[DEFAULT_SIZE];
}
// 判满
public boolean isFull() {
return (getSize()==DEFAULT_SIZE);
}
// 扩容
public void ensureCapacity() {
if(isFull()) { // man了就进行扩容
System.out.println("进行扩容：");
//Arrays.copyOf(array,2*DEFAULT_SIZE); // 注意这里扩容后要赋值给数组！！
array = Arrays.copyOf(array,2*DEFAULT_SIZE);
}
// 这里就是说明未满不需要扩容或者已经扩容成功
return ;
}
// push压栈:元素入栈
public int push(int e) {
// 进行判满+扩容
ensureCapacity();
// 进行数据元素的存储：数组存储--下标利用usedSize
/*array[usedSize] = e;
usedSize++;*/
// 注意以上两行可以合并成一行：先用后加：即后置++操作
array[usedSize++] = e;
return e;
}
// pop出栈:拿到栈顶元素+删除
public int pop() {
/*// 判空
if(isEmpty()) {
throw new EmptyException("sorry 栈为空，无法获取栈顶元素！");
}
// 先进行-- 再进行使用
return (array[--usedSize]);*/
// 或者使用peek，省去判空
int tmp = peek();
usedSize--;
return tmp;
}
// peek拿到栈顶元素但不删除
public int peek() {
// 首先要进行判空操作
if(isEmpty()) {
throw new EmptyException("sorry 栈为空，无法获取栈顶元素！");
}
return (array[usedSize-1]);
}
// 拿到实际有效长度
public int getSize() {
return usedSize;
}
// 判空
public boolean isEmpty() {
return (0==usedSize);
}
}
- EmptyException.java
public class EmptyException extends RuntimeException{
public EmptyException() {
}
public EmptyException(String message) {
super(message);
}
}
- Test.java
public class Test {
public static void main(String[] args) {
MyStack myStack = new MyStack();
System.out.println("进行压栈操作：");
myStack.push(2);
myStack.push(8);
myStack.push(1998);
myStack.push(0);
System.out.println("获取栈的实际大小：");
System.out.println(myStack.getSize());
System.out.println("获取开辟数组长度：");
System.out.println(myStack.array.length);
System.out.println("进行出栈操作：");
System.out.println(myStack.pop());
System.out.println("获取栈的实际大小：");
System.out.println(myStack.getSize());
System.out.println("进行拿到栈顶元素操作：");
System.out.println(myStack.peek());
System.out.println("获取栈的实际大小：");
System.out.println(myStack.getSize());
}
}
4. 栈的应用场景
1. 场景小结：
- 不可能的出栈顺序（就是给定一个入栈序列，选择不可能的出栈顺序）
- 解决该类题要考虑出栈不一定是全部入栈后才出栈，而是出栈过程中同时也入栈）
- 第二种考法：中缀表达式转后缀表达式【考研选择】
通过后缀/逆波兰表达式计算表达式的结果【写代码】
如：中缀表达式：2 + 3 * 5 ，则后缀表达式：2 3 5 * +
中缀表达式：(2 + 3) * 5 ，则 后缀表达式：2 3 + 5 * - 中缀转后缀方式：按照运算顺序依次加括号，然后将运算符拉到每个括号外面，最后去掉括号就ok
- 中缀转前缀：方法一致—加括号，运算符拉到前面就ok
- 后缀表达式计算结果：画一个栈，如果是数字就放栈里放，如果是运算符就弹出栈顶的两个元素，首个作为右操作数，第二个作为左操作数（顺序很重要！！），然后进行运算，运算结果再入栈！
- 将递归转为循环：（此处代码写在单链表章节上：利用栈的先进后出原理进行打印！：具体看Gitee代码）
- 括号匹配（匹配问题多往栈去想）–考试频率较高！
其实我认为就是类似于回文结构！但是利用栈去实现就是：左括号就进栈，右括号则利用左括号出栈（拿到栈顶元素）进行匹配。（然后匹配依据其实就是：字符串遍历完成 and 栈为空）
- 不匹配：左右括号直接不匹配；左括号多：字符串遍历完成，但是栈不为空；右括号多：当前下标是右括号，但是栈为空
- 出栈入栈次序匹配：
- 一定要注意一个点：就是比较大小时，Integer是包装类/ 引用类，比较大小时不能直接用 == ，因为引用类比较的是地址。
- 但是其实Integer在-128~127之间是可以直接使用 == 比较大小的，因为数在-128到127之间，就直接在缓存里取，拥有相同的地址；否则就返回一个新对象。
2. 实例：
- 元素出栈顺序
- 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A: 1,4,3,2
B: 2,3,4,1
C: 3,1,4,2
D: 3,4,2,1
2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A: 12345ABCDE
B: EDCBA54321
C: ABCDE12345
D: 54321EDCBA
答案：C B
- 将递归转换为循环
（使用单链表：）
// 递归实现单链表的逆序打印
// 判断是否空 or 是否只有一个结点+ 另外
// 递归：当return后有返回到递归之后开始继续向后执行！！！
public void printReverse(Node head) {
// 进行判断：
if(head==null) {
return ;
}
if(head.next == null) {
System.out.print(head.val+" ");
return;
}
// 来到这儿说明可以递归：有好多个结点
printReverse(head.next); //递归传入的是下一个结点地址
System.out.print(head.val+" ");
// 一定要打印：否则在递归返回后要往下运行时就没有运行的代码，也就无法打印了
}
// 非递归实现逆序打印--模拟栈（先进后出）
public void printReverseStack(Node head) {
// 自定义类型存储的是地址！
// 利用栈的思想
// 注意泛型类型是Node结点！！
Stack<Node> stack = new Stack<>(); // 注意是没有传入任何参数的！
// 定义一个临时变量
Node cur = head;
// 首先进行压栈
while(cur!=null) {
stack.push(cur);
cur = cur.next;
}
// 再进行弹出
//while(cur!=null) {// 注意这里循环的条件！！！ --此处是关于栈的！
while(!stack.empty()) { // 判断是否为空：这里重要！！！
Node node = stack.pop(); //直接把节点弹出来！
System.out.print(node.val+" ");
}
System.out.println();
}
- 括号匹配 有效的括号
时间以及空间复杂度都是O(n)
class Solution {
public boolean isValid(String s) {
// 不用进行判空操作，因为长度已知是大于0的
// 创建一个栈
Stack<Character> stack = new Stack<> ();
// 首先拿到字符串的每一个字符
for(int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
// 进行左括号的判断:左括号就压栈
if((ch=='(')||(ch=='[')||(ch=='{')) {
stack.push(ch);
} else {
// 判断是不是第一个
// if(i==0) {
// 注意判断方法:栈是不是为空 ：因为如果是第一个就是右括号则不入栈，就为空
if(stack.empty()){
return false;
} else {
//注意这里的判断方法
/*switch(ch) {
case ')':
if(stack.pop(ch)=='(')
break;
return false;
case ']':
if(stack.pop(ch)=='[')
break;
return false;
case '}':
if(stack.pop(ch)=='{')
break;
return false;
}*/
// 修改如下：
char top = stack.peek();
if((ch==')'&&top=='(') || (ch==']'&&top=='[') || (ch=='}'&&top=='{')) {
// 说明匹配 弹出
stack.pop();
}else {
// 不匹配
return false;
}
}
}
}
// 来到这儿：进行判断栈中是否还有剩余：（左括号是否多）
if(!stack.empty()) {
return false;
}
return true;
}
}
- 逆波兰表达式求值逆波兰表达式
1）思路：
使用栈+foreach进行遍历 + 判断是否为操作符的方法（注意字符串比较相等使 用的是equals +因为是字符串，当弹入栈时转换为int型–Integer.parseInt （如果是中缀表达式，先转后缀表达式再进行栈操作）
2）代码：
class Solution {
public int evalRPN(String[] tokens) {
// 字符串弹入栈时要转为int型
Stack<Integer> stack = new Stack<>();
// 遍历判断是否为运算符
for(String x: tokens) {
if((x.equals("+")) || (x.equals("-")) || (x.equals("*")) || (x.equals("/"))) {
// 是运算符则保留,并且把运算数取出来
int num2 = stack.pop(); // 第一个数作为右操作数
int num1 = stack.pop(); // 第二个数作为左操作数
// 然后计算结果又进行压栈
switch(x) {
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1-num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1/num2);
break;
}
} else {
// 运算数则压栈
stack.push(Integer.parseInt(x));
}
}
return stack.pop();
}
}
- 出栈入栈次序匹配 出栈入栈次序匹配
1） 思路：
- 两个数组不匹配就进行压栈，匹配就出栈且继续比对匹配 （最后看栈是否为空）
- 不一样的情况：pushA数组已经遍历完，但是栈中依旧有元素
- for循环实现pushA的遍历 + while循环（注意条件顺序）+ 注意引用类型的比较equals
2） 代码：
(注意while循环条件+顺序）
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
/*
// 首先进行Apush压栈，然后再与popA进行对比，如果一样就出栈，不一样则继续压栈
Stack<Integer> stack = new Stack<>();
int j =0;
// 首先进行两个都为空的判断
if(pushA.length==0 && popA.length==0) {
return false;
}
// 进行长度判断：相等才有继续的必要！
if(popA.length != pushA.length) {
return false;
}
// 说明长度一样，有可比性
for(int i=0; i<pushA.length; i++) {
//if(stack.empty()) {
// 栈为空就进行压栈--不用判空才压栈，直接只要运行到i就要压栈！
stack.push(pushA[i]);
//break; // 这里不能使用break 不然如果只有一个元素就直接执行不到后面的操作
//}
// 此处应该使用循环进行操作：因为可能对比拿到栈顶元素后还要继续对比拿到下一个栈中元素
// 这里要进行循环条件等的修改！
while((!stack.empty()) && (j<popA.length) && (i<pushA.length)) {
// 进行对比操作
int top = stack.peek();
if(top==popA[j]) {
stack.pop(); //删除栈顶元素,但是i不用变化
j++; // 进行变换！
}
//else {
// // 如果不相等即继续压栈操作
// i++;
// stack.push(pushA[i]);
// } // 所以这里也没必要！
}
}
if(stack.empty()) {
// 如果最后栈为空，则说明ok（因为长度一样）
return true;
}
return false; */
// 重新修改！尤其要注意循环！！
Stack<Integer> stack = new Stack<>();
if(popA.length==0 || pushA.length==0) { // 或者是因为二者相等
return false;
}
int j =0;
for(int i=0; i<pushA.length; i++) {
// 进来先进行压栈
stack.push(pushA[i]);
// 进行匹配（循环！）
//while((stack.peek()==popA[j]) && (!stack.empty()) & (j<popA.length)) {
// 注意顺序!!! j先满足条件 然后看栈是否为空，最后才判断相等
while((j<popA.length) && (!stack.empty()) && (stack.peek()==popA[j]) ) {
// 注意 Integer是引用类型，比较大小用equals
// stack.peek().equals(popA[j]) // 但此时也要注意popA【i】不是引用类型
// 要非空--否则会报异常！
stack.pop(); // 删除栈顶
j++;
}
}
// 为什么不用判断两个数组的相等呢？因为题给相等，如果未给就要自己在之前进行长度相等判断
return (stack.empty());
}
}
5. 概念区分
栈、虚拟机栈、栈帧有什么区别呢？
1） 栈：先进后出的数据结构
2） 虚拟机栈：指的是JVM的一块内存，定义的局部变量、方法使得开辟都在虚拟机栈上
3） 栈帧：方法开辟出来的内存叫做栈帧
THINK
- 栈以及栈的方法
- 栈的方法模拟实现
- 概念区分：栈、虚拟栈帧、栈帧
本文含有隐藏内容，请 开通VIP 后查看