Java - 数据结构，栈

分手后的思念是犯贱 2024-03-27 16:34 89阅读 0赞

## 一、栈 ##

### 1.1、什么是栈 ###

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈  
顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。  
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。  
出栈：栈的删除操作叫做出栈。出数据在栈顶  
![在这里插入图片描述][9ef6d7f6247e400484ad015e5be80f91.png]

> **什么是Java虚拟机栈？**  
> ![在这里插入图片描述][69f301c9bc4f4bdba4f15e8b69ef7c58.png]  
> java虚拟机栈也是栈，就是JVM中的一块内存，也是符合栈的规则 – 先进后出规则
> 
> > 方法区：存放类定义信息、字节码、常量等数据，在Sun HotSpot JVM中，这块也称为Perm Gen。  
> >    
> > 堆：创建的对象信息将放入堆中，堆内部如何实现各虚拟机各不相同，对于Sun HotSpot JVM来说又分为Young Gen和Tenured Gen，更详细描述参见《\[Java性能剖析\]Sun JVM内存管理和垃圾回收 》  
> >    
> > Java栈：对于每个执行线程，会分配一个Java栈，JVM在执行过程当中，每执行一个方法，都会为方法在当前栈中增加一个栈帧，每个栈帧的信息与具体实现相关，但一般会由3部分组成：变量区，方法参数和本地变量会放入这个位置，大小是固定的，在进行方法时会先分配好，在类定义中，会由max local来指定这块区的大小；方法信息区，会包括当前类常量池的入口地址等信息，这块大小也是固定的；操作栈，与Intel体系架构中的运算使用寄存器来进行不一样，JVM的字节码的方法调用、运算等需要的参数，都是通过操作栈来传递的。在类定义中，会由max stack指定最大的操作栈。关于Java栈的更详细描述参见《Java 栈内存介绍 》  
> >    
> > 本地方法栈：对本地方法的调用，并不会使用Java栈而是使用本地方法栈，本地方法栈的组成取决于所使用的平台和操作系统.  
> >    
> > PC寄存器/程序计数器：对于每个执行线程会分配一个PC寄存器，寄存器中存放当前字节码的执行位置
> 
> **什么是栈帧？**  
> 调用函数的时候，我们会为函数开辟一块内存，这块内存叫做栈帧，这个内存在Java虚拟机栈中开辟

### 2.2、栈的笔试题 ###

#### 2.2.1、一个栈的输入顺序是ABCDEF，那么不可能出现的出栈顺序是什么（） ####

A、DCBAEF

B、ACBEDF

C、DEFBCA

D、CDBAFE

在出栈的时候可以入一个出一个，入栈和出栈的顺序可以打乱，但是出栈的时候，一定是先出栈顶的元素  
![在这里插入图片描述][33fa29e8c7f947c48755a20ed594b3c4.png]

##### 剑指 Offer 31. 栈的压入、弹出序列 #####

[输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 \{1,2,3,4,5\} 是某栈的压栈序列，序列 \{4,5,3,2,1\} 是该压栈序列对应的一个弹出序列，但 \{4,3,5,1,2\} 就不可能是该压栈序列的弹出序列。][_1_2_3_4_5_ _ _4_5_3_2_1_ _ _4_3_5_1_2_]

public boolean validateStackSequences(int[] pushed, int[] popped) {
        
            Stack<Integer> stackA = new Stack<Integer>();
            int j = 0;
            //遍历数组pushed
            for(int i = 0; i < pushed.length; i++){
        
                stackA.push(pushed[i]);
    
                //判断栈顶元素是否和popped数组的j下标相等，如果相等就出栈
                while(j < popped.length && !stackA.empty() && stackA.peek() == popped[j]){
        
                    stackA.pop();
                    j++;
                }    
            }
    
            return stackA.empty();
        }

#### 2.2.2、中缀表达式转后缀表达式 ####

它们都是对表达式的记法，因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同：前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。

举例：  
(3 + 4) × 5 - 6 就是中缀表达式

\-× + 3 4 5 6 前缀表达式

3 4 + 5 × 6 - 后缀表达式

**中缀表达式（中缀记法）**  
中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。  
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

**前缀表达式（前缀记法、波兰式）**  
前缀表达式的运算符位于操作数之前。

**后缀表达式（后缀记法、逆波兰式）**  
后缀表达式与前缀表达式类似，只是运算符位于操作数之后。

**如何将中缀表达式转换成后缀表达式**  
![在这里插入图片描述][08c8c0fa1cff42d7820925afd34db1a5.png]

###### 利用栈实现计算后缀表达式的值：[逆波兰表达式求值][Link 1] ######

![在这里插入图片描述][62a9973dc74943a2a45666a4545eea15.png]  
![在这里插入图片描述][1acc7ac89a0d4211a9d0696ddc1b4f0c.png]

class Solution {
        
        public int evalRPN(String[] tokens) {
        
            Stack<Integer> stack = new Stack<>();
            for(int i = 0; i < tokens.length; i++){
        
                String val = tokens[i];
                if(isOperator(val) == false){
        
                    stack.push(Integer.parseInt(val));
                }else {
        
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    switch (val){
        
                        case "+":
                            stack.push(num1 + num2);
                            break;
                        case "-":
                            stack.push(num1 - num2);
                            break;
                        case "*":
                            stack.push(num1 * num2);
                            break;
                        case "/":
                            stack.push(num1 / num2);
                            break;    
                    }
                }
            }
            return stack.pop();
        }
        //判断是不是运算符，是就返回true，不是就返回FALSE
        private boolean isOperator(String val){
        
            if(val.equals("+") || val.equals("-") || val.equals("*") || val.equals("/")){
        
                return true;
            }
            return false;
        }
    }

### 2.3、栈的方法 ###

![push(); -- 添加元素][push_ --]

public static void main(String[] args) {
        
            Stack<Integer> stack = new Stack<>();
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            System.out.println(stack);
            System.out.println(stack.pop());
            System.out.println(stack);
            stack.peek();
            System.out.println(stack);
        }

### 2.4、模拟实现一个栈 ###

![在这里插入图片描述][3cc5f270942145049c6c7776e34a2f8b.png]

public class MyStack {
        
        public int elem[];
        public int usedSize;
    
        public MyStack(){
        
            //源码中默认大小为10
            this.elem = new int[10];
        }
    
        //添加元素
        public void push(int val){
        
            //判断是否满
            if(isFull()){
        
                //如果满了就要扩容,
                this.elem = Arrays.copyOf(elem, 2*this.usedSize);
            }
            this.elem[this.usedSize] = val;
            this.usedSize++;
        }
        private boolean isFull(){
        
            //满了返回true
            return this.elem.length == this.usedSize;
        }
    
        //出栈
        public int pop(){
        
            //首先要判断栈里面有没有元素
            if(empty()){
        
                //如果没有元素就不能出栈，此时就要抛出异常
                throw new RuntimeException("栈为空！");
            }
            //如果有元素就可以出栈了
            int oldVal = this.elem[usedSize-1];
            //如果栈里面存的是引用类型，那这个就要置位null
            usedSize--;
            return oldVal;
        }
    
        public boolean empty(){
        
            return this.usedSize == 0;
        }
    
        //获取栈顶元素
        public int peek(){
        
            //首先要判断栈里面有没有元素
            if(empty()){
        
                //如果没有元素就不能出栈，此时就要抛出异常
                throw new RuntimeException("栈为空！");
            }
            return this.elem[usedSize-1];
        }
        
    }

#### 面试题：能不能用单链表实现一个栈 ####

首先，要实现一个栈，就要知道栈的特点  
1、先进后出  
2、入栈和出栈的时间复杂度是O(1)  
那单链表呢，单链表可以头插和尾插，那用头插还是插？？？  
如果用头插：在入栈的时候就头插，时间复杂度也是O(1)，出栈的时候只要删除头结点，时间复杂度也是O(1)。  
如果用尾插：那就不可能实现，在插入的时候可以用尾插，时间复杂度是O(1)，但是在出栈的时候就不行了，在删除尾巴节点的时候，要知道尾巴节点的前驱才能删除，但是这时候就要遍历一遍链表，时间复杂度就是O(n)

那单链表不行，就可以使用双向链表。

#### [有效的括号][Link 2] ####

给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。  
有效字符串需满足：  
左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
每个右括号都有一个对应的相同类型的左括号。

/在做这道题的时候要考虑几种情况
        //1、左括号多了 （（（  ））
        //2、右括号多了 （（（（（  ））
        //2、括号不匹配  （ [ ] } 
        public boolean isValid(String s) {
        
            //栈里面存放的是左括号
            Stack<Character> stack = new Stack<>();
            char[] chars = s.toCharArray();
            for(int i = 0; i < chars.length; i++){
        
                if(chars[i] == '[' || chars[i] == '(' || chars[i] == '{'){
        
                    stack.push(chars[i]);
                }else{
        
                    if(stack.empty()){
        
                        //右括号多了
                        return false;
                    }else{
        
                        if((chars[i] == '}' && stack.peek() == '{') || (chars[i] == ']' && stack.peek() == '[') || (chars[i] == ')' && stack.peek() == '(')){
        
                            stack.pop();
                        }else{
        
                            //括号不匹配
                            return false;
                        }
                    }
                }
    
            }
    
            if(!stack.empty()){
        
                //右括号多了
                return false;
            }
            return true;
        }

#### [最小栈][Link 3] ####

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。  
void push(int val) 将元素val推入堆栈。  
void pop() 删除堆栈顶部的元素。  
int top() 获取堆栈顶部的元素。  
int getMin() 获取堆栈中的最小元素。

private Stack<Integer> stack;
        private Stack<Integer> minStack;
        public MinStack() {
        
            stack = new Stack<>();
            minStack = new Stack<>();
        }
        
        public void push(int val) {
        
            stack.push(val);
            if(minStack.empty() ){
        
                minStack.push(val);
            }else{
        
                if(val <= minStack.peek()){
        
                    minStack.push(val);
                }
            }
        }
        
        public void pop() {
        
            int popVal = stack.pop();
            if(!minStack.empty()){
        
                if(popVal == minStack.peek()){
        
                    minStack.pop();
                }
            }
        }
        
        public int top() {
        
            return stack.peek();
        }
        
        public int getMin() {
        
            return minStack.peek();
        }

[9ef6d7f6247e400484ad015e5be80f91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c37c9308857b44d38223e3802671b588.png
[69f301c9bc4f4bdba4f15e8b69ef7c58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f974c9ef0bda4e50b57075f3eaf9313d.png
[33fa29e8c7f947c48755a20ed594b3c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c562de98b3ef437da065243371985647.png
[_1_2_3_4_5_ _ _4_5_3_2_1_ _ _4_3_5_1_2_]: https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
[08c8c0fa1cff42d7820925afd34db1a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ccd13f43383447648e0ffdb888d67f7e.png
[Link 1]: https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
[62a9973dc74943a2a45666a4545eea15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/af52ee7d7b684aeaba307cc3e2219b60.png
[1acc7ac89a0d4211a9d0696ddc1b4f0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2829d066a0cf42c4abd5577c687f59a5.png
[push_ --]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bc268e43f5504571a40b610950767c38.png
[3cc5f270942145049c6c7776e34a2f8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/73131a4dbe104bc5ae09ece54070cf8b.png
[Link 2]: https://leetcode.cn/problems/valid-parentheses/
[Link 3]: https://leetcode.cn/problems/min-stack/