06 【LeetCode】栈与队列 - 常见题型与思路总结（小白向）

【Day 10-13】 -【代码随想录训练营20期】打卡

栈的基础知识

栈就是一种特殊的数据结构（和JVM的栈区不一样），是线性表的一种。

但与其不同的是，数据的添加与删除都只在一端（栈顶），另一端叫栈底。数据以堆叠的形式存放，先进后出（LIFO）。

在java中，Stack（栈）继承了Vector。

实现的方法：

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.size()); // 输出 4

        System.out.println("获取栈顶元素 : "+stack.peek()); // 获取栈顶元素,但是不出栈,栈中元素不变

        stack.pop();   // 出栈  元素 4 出栈 ,栈中剩余元素 3,2,1

        System.out.println("获取栈顶元素 : " + stack.pop()); // 获取栈顶元素,出栈, 此时栈中剩余 2,1两个元素

        System.out.println("栈中有效元素个数 : "+ stack.size()); // 输出 2

        System.out.println("stack是否为空 : "+ stack.isEmpty()); // 判断栈中是否为空

    }

队列的java语法和栈类似，只有出入方式不同，出入栈分别为pop 、push，出入队列分别为poll 、offer。

队列的基础知识

队列也是线性表，但只允许一端进行插入，另一端进行删除，具有先进先出FIFO的特性。

进行插入的一端是队尾，删除操作的那一段就是队头。

public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        //插入元素
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5);

        System.out.println("元素个数 : "+q.size()); // 获取元素个数 输出5

        System.out.println("获取队头元素 : "+q.peek()); // 获取队头元素,但不删除元素
        q.poll();
        System.out.println("出队列元素 : "+q.poll()); // 从队头出队列，并将删除的元素返回

        if(q.isEmpty()){
            System.out.println("队列空");
        }else{
            System.out.println("元素个数 : "+q.size());
        }
    }

队列的变种——单调队列！

单调队列是一种特殊的队列，它维护元素的单调性（递增或递减）。

其底层是Deque，也就是双端队列，可以通过poll offer 和 Last First的组合，实现两端添加或移除元素。

单调递减队列用于找出滑动窗口中的最大值。队列中的元素按照递减的顺序排列，即队头元素是最大的。

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> decreasingQueue = new ArrayDeque<>();

for (int i = 0; i < nums.length; i++) {
    // 在队尾删除比当前元素大的元素
    while (!decreasingQueue.isEmpty() && nums[i] >= nums[decreasingQueue.peekLast()]) {
        decreasingQueue.pollLast();
    }

    // 添加当前元素的索引到队尾
    decreasingQueue.offerLast(i);

    // 如果队头元素不在滑动窗口范围内，移除队头元素
    if (decreasingQueue.peekFirst() <= i - k) {
        decreasingQueue.pollFirst();
    }

    // 如果已经形成窗口，处理当前窗口的最大值
    if (i >= k - 1) {
        int maxInWindow = nums[decreasingQueue.peekFirst()];
        // 在这里处理最大值
    }
}

单调递增队列用于找出滑动窗口中的最小值。队列中的元素按照递增的顺序排列，即队头元素是最小的。

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> increasingQueue = new ArrayDeque<>();

for (int i = 0; i < nums.length; i++) {
    // 在队尾删除比当前元素小的元素
    while (!increasingQueue.isEmpty() && nums[i] <= nums[increasingQueue.peekLast()]) {
        increasingQueue.pollLast();
    }

    // 添加当前元素的索引到队尾
    increasingQueue.offerLast(i);

    // 如果队头元素不在滑动窗口范围内，移除队头元素
    if (increasingQueue.peekFirst() <= i - k) {
        increasingQueue.pollFirst();
    }

    // 如果已经形成窗口，处理当前窗口的最小值
    if (i >= k - 1) {
        int minInWindow = nums[increasingQueue.peekFirst()];
        // 在这里处理最小值
    }
}

队列的变种——优先队列！

优先队列（Priority Queue）是一种数据结构，类似于普通队列，但具有特殊的排序规则：元素根据其优先级被排列。在 Java 中，优先队列通常基于堆（Heap）实现，它可以是最小堆（Min Heap）或最大堆（Max Heap）。

最小堆：在最小堆中，父节点的值始终小于或等于其子节点的值。

最大堆：在最大堆中，父节点的值始终大于或等于其子节点的值。

PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

使用lambda 表达式设置优先级队列从大到小存储， o1 - o2 为从大到小，o2 - o1 反之。

232.?用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现?MyQueue?类：

• void push(int x)?将元素 x 推到队列的末尾
• int pop()?从队列的开头移除并返回元素
• int peek()?返回队列开头的元素
• boolean empty()?如果队列为空，返回?true?；否则，返回?false

说明：

• 你?只能?使用标准的栈操作 —— 也就是只有?push to top,?peek/pop from top,?size, 和?is empty?操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

思路：用两个栈的话，一个栈顺序反过来，一个栈又可以将顺序再反，所以只需要两个栈颠倒数据就行。

class MyQueue {


    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    /** Initialize your data structure here. */
    public MyQueue() {
        stackIn = new Stack<>(); // 负责进栈
        stackOut = new Stack<>(); // 负责出栈
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stackIn.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {    
        dumpstackIn();
        return stackOut.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
    private void dumpstackIn(){
        if (!stackOut.isEmpty()) return; 
        while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
        }
    }

}

225.?用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop?和?empty）。

实现?MyStack?类：

• void push(int x)?将元素 x 压入栈顶。
• int pop()?移除并返回栈顶元素。
• int top()?返回栈顶元素。
• boolean empty()?如果栈是空的，返回?true?；否则，返回?false?。

注意：

• 你只能使用队列的基本操作 —— 也就是?push to back、peek/pop from front、size?和?is empty?这些操作。
• 你所使用的语言也许不支持队列。?你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列?, 只要是标准的队列操作即可。

思路：可以用一个队列，将要移出的那个元素推到队头就行，一直poll和offer，第1个是将前size-1个移到后面，第n个是第size-n个。

class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    /** Initialize your data structure here. */
    public MyQueue() {
        stackIn = new Stack<>(); // 负责进栈
        stackOut = new Stack<>(); // 负责出栈
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stackIn.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {    
        dumpstackIn();
        return stackOut.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
    private void dumpstackIn(){
        if (!stackOut.isEmpty()) return; 
        while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
        }
    }
}

20.?有效的括号

给定一个只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

思路：这种对称类的题目很适合用栈来解。

import java.util.EmptyStackException;
class Solution {
    public boolean isValid(String s) {
        //用三个栈，遇到左括号就push，遇到右括号就pop
        Stack<Integer> st1 = new Stack<>();
        char temp;
        if(s.length() % 2 == 1){
            return false;
        }
        for(int i = 0; i < s.length(); i++){
            temp = s.charAt(i);
            try{
                if(temp == '('){
                    st1.push(1);
                }else if(temp == ')'){
                    if(st1.peek() == 1){
                        st1.pop();
                    }else{
                        return false;
                    }
                }else if(temp == '{'){
                    st1.push(2);
                }else if(temp == '}'){
                    if(st1.peek() == 2){
                        st1.pop();
                    }else{
                        return false;
                    }
                }else if(temp == '['){
                    st1.push(3);
                }else if(temp == ']'){
                   if(st1.peek() == 3){
                        st1.pop();
                    }else{
                        return false;
                    }
                }
            }catch(EmptyStackException e){
                return false;
            }   
        }
        if( st1.isEmpty() ){
            return true;
        }else{
            return false;
        }
    }
}

还有一个更简单的思路，就是遇到左括号，直接push右括号，然后在后面的元素比较中，与栈顶的元素比较是否相同，不同就false。

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }
}

1047.?删除字符串中的所有相邻重复项

给出由小写字母组成的字符串?S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

思路：这种也是对称类问题，用stack来判断当前元素是否与上一个元素相同，是就pop，否就push。

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> st = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(!st.isEmpty() && s.charAt(i) == st.peek()){
                st.pop();
            }else{
                st.push(s.charAt(i));
            }
        }
        StringBuilder s1 = new StringBuilder();
        while (!st.isEmpty()) {
            s1.insert(0, st.pop());
        }
        
        return s1.toString();

    }
}

150.?逆波兰表达式求值

给你一个字符串数组?tokens?，表示一个根据?逆波兰表示法?表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为?'+'、'-'、'*'?和?'/'?。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是?向零截断?。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用?32 位?整数表示。

思路：本题思路非常清晰，就用栈的先进后出来解决问题。难点有如下几个：

1. 如何将字符串类型转换为整数型？

使用：Integer xxx = Integer.parseInt(xxx);

parsenlnt是Integer将字符串转换为整数型的一个方法，当无法转换时，会抛出NumberFormatException异常。

2. 如何使得push进的全部是数字？

先判断是否是算符，否则就转换整数然后push进去。

class Solution {
    public int evalRPN(String[] tokens) {
        if(tokens.length == 1){
            int result = Integer.parseInt(tokens[0]);
            return result;
        }
        Stack<Integer> stack = new Stack<>();
        Integer temp = null;
        for(int i = 0; i < tokens.length; i++){
            try{
                Integer parsedValue = Integer.parseInt(tokens[i]);
                stack.push(parsedValue);
            }catch(NumberFormatException e){
                temp = stack.pop();
                
                if(tokens[i].equals("+")){
                    temp = temp + stack.pop();
                }else if(tokens[i].equals("-")){
                    temp = - temp + stack.pop();
                }else if(tokens[i].equals("*")){
                    temp = stack.pop()*temp;
                }else if(tokens[i].equals("/")){
                    temp = stack.pop()/temp;
                }
                stack.push(temp);

            }
        }
        
        int result = temp;
        return result;
    }
}

239.?滑动窗口最大值

给你一个整数数组?nums，有一个大小为?k?的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的?k?个数字。滑动窗口每次只向右移动一位。

返回?滑动窗口中的最大值?。

思路：这题思路比较直，就每次比较后一位和窗口内最大值的大小就行。

1. 难点！如何保证时间复杂度是O(n)？

这就需要运用到单调队列，单调队列的特点是维护一个元素递增或递减的队列，以便在常数时间内找到当前队列中的最值元素。

2. 注意！单调队列内保存的不是数组的值，而是数组的值对应的数组下标！这样才方便滑动窗口时，元素的移除。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //初始化一个双向队列
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        //初始化结果数组
        int[] res = new int[n - k + 1];
        //初始化结果数组指针，从0开始
        int idx = 0;
        for(int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.模拟窗口滑动，队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.模拟单调队列，既然是单调，就要保证每次放进去的数字要比末尾的都大
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            //注意，放入的是元素下标，而非元素本身
            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
}

347.?前 K 个高频元素

给你一个整数数组?nums?和一个整数?k?，请你返回其中出现频率前?k?高的元素。你可以按?任意顺序?返回答案。

思路：这道题我没有啥思路，因为没有接触到优先队列，实际上我就卡在了给哈希表内的元素排序这里。

难点：优先队列！

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 优先级队列，为了避免复杂 api 操作，pq 存储数组
        // lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从大到小，o2 - o1 反之
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int[] res = new int[k]; // 答案数组为 k 个元素
        Map<Integer, Integer> map = new HashMap<>(); // 记录元素出现次数
        //这里主要是用map储存元素本身以及元素的个数
        //map.getOrDefault实际上是获取num对应的键值，该键值就表示num出现的次数；若该num没有出现在map中，则是第一次添加，那么就返回0；+1代表加入当前的元素次数1次
        for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        for(var x : map.entrySet()) { // entrySet 获取 k-v Set 集合
            // 将 kv 转化成数组
            int[] tmp = new int[2];
            tmp[0] = x.getKey();
            tmp[1] = x.getValue();
            //通过PriorityQueue优先队列排序
            pq.offer(tmp);
            //由于从大到小排列，只需维护前K个就行，超过k的就poll出去
            if(pq.size() > k) {
                pq.poll();
            }
        }
        for(int i = 0; i < k; i ++) {
            res[i] = pq.poll()[0]; // 获取优先队列里的元素
        }
        return res;
    }
}