单调栈与队列的概念与练习！【建议收藏】_队列面积

本期文章，小编给大家介绍一下数据结构中很重要的两个角色，那就是栈与队列两兄弟。文中若有欠妥之处，还望指正！感谢！

一、栈与队列的概念

1、栈

栈是限定仅在表尾进行插入和删除操作的线性表。 栈的插入操作叫做：压栈或者入栈，栈的删除操作叫做 ： 弹栈或者出栈。栈的特点是先进后出。什么意思？

如图：我们可以将栈想象为一个杯子，假设我先将“冰红茶”倒入，再将“绿茶”倒入杯子里。在不搅拌的情况下，是不是“冰红茶”在“绿茶”的下面。如图：

所在我们在喝茶（出栈）的时候，是先喝了“绿茶”，喝完之后才是喝的“冰红茶”。这也就满足了先进后出的特点。

单调栈结构： 分为单调递增栈和单调递减栈。切记递增还是递减，从从栈顶到栈底进行判断的，如下图：

单调递增栈伪代码

Stack<Integer> stack = new Stack<>();
for (遍历整个数组) {
    
    while(栈不为空   并且  栈顶元素 < 当前遍历到的数组元素) { //这里的循环，决定是递增栈还是递减栈
        出栈，进行一些关于题目的操作
    }
    
    将当前数组的元素  入栈
        
}
1
2
3
4
5
6
7
8
9
10

2、队列

队列（queue）是只允许在一端进行插入操作，而只能在另一端进行删除操作。 队列的插入操作称为：入队；队列的删除操作称为：出队。对列的特点是：先进先出。例如：我们在排队拿号时，先去排队的，肯定就是先拿到号。

入队：

出队：

二、栈的运用

典型的斐波那契数、青蛙跳台阶和汉诺塔问题，看我的前期文章（递归的讨论！）。今天我们重新说一个题，表达式求值问题

题目：逆波兰表达式求值问题

在线OJ链接

题意：会提供一个一个字符串数组，数组里放的是后缀表达式的结果，如上图中的输入，就是一个后缀表达式，要我们计算出这个式子的结果。

先简单说一个中缀表达式如果转换为后缀表达式吧：我们首先有一个栈，叫操作符栈。

1）如果遇到操作数，我们就直接将其输出。

2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

3）如果遇到一个右括号，则将栈元素弹出，一直弹到左括号出来为止。注意，左括号只弹出并不输出。

4）如果遇到任何其他的操作符，如“+”， “-”，“（”等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( "。

5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

后缀表达式得到后，问题就来到了，如何将后缀表达式计算出结果了。我们先准备一个栈：操作数栈。从左到右遍历后缀表达式：

1. 遇到操作数，我们直接压入到操作数栈即可；
2. 遇到操作符，我们就弹出操作数栈里的两个数据进行计算，然后再次压入计算后的结果；

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> numStack = new Stack<>(); //操作数栈
        int size = tokens.length;
        for (int i = 0; i < size; i++) {
            if (isChar(tokens, i)) { //判断是不是操作符
                int num2 = numStack.pop();
                int num1 = numStack.pop();
                numStack.push(calculate(num1, tokens[i], num2)); //计算的数据重新压入栈中
            } else {
                numStack.push(Integer.parseInt(tokens[i]));
            }
        }
        return numStack.pop(); //最后栈里剩下的一个数据，就是最后的结果
    }

    private boolean isChar(String[] tokens, int i) {
        if (tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") 
            || tokens[i].equals("/")) {
            return true;
        }
        return false;
    }

    private int calculate(int num1, String option, int num2) {
        if (option.equals("+")) {
            return num1 + num2;
        }
        if (option.equals("-")) {
            return num1 - num2;
        }
        if (option.equals("*")) {
            return num1 * num2;
        }

        if (num2 == 0) {
            throw new RuntimeException("num2 is zero.");
        } 
        return num1 / num2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

最后：大家可以尝试，假设题目给定的是中缀表达式，如何将它计算出来？其实思想跟我上面讲的一样，只不过需要自己去转换后缀表达式。一个操作数栈，另一个操作符栈，两个栈配合起来，就能解。

三、单调栈运用

题目：最大子矩形面积

在线OJ链接

题意：给定一些柱子，计算相邻的柱子之间所构成的最大矩阵面积。例如上图：5、6高度的柱子，可以组合成面积为10的矩形。

分析：这道题我们就要用到单调递减栈。我们从左到右遍历每一根柱子，假设当前遍历到的柱子就是上图的第四根数组（高度为6），此时这根柱子左边离它最近并且还比它小的就是第三根柱子（高度为5），右边离它最近 并且比它小的柱子就是第五根柱子（高度为2）。 本质上，我们就是在寻找每一根柱子，左右两边最近且比它小的柱子，就能计算出这左右两边的柱子中间的矩形面积。如图：

压栈过程：维持栈顶到栈底是降序的。所以上图压入前3个柱子的数据后： 栈顶到栈顶为{6, 5, 1}；

当我们遍历到高度为2的柱子时，就打破了降序的规则，所以我们就要弹出栈中的元素，直到压入高度为2的柱子，还能够保持降序即可。

• 弹出栈顶元素，记为j。新栈顶元素记为k。

因为新栈顶元素（k）肯定是小于刚刚弹出的元素（j）的，所以说：j位置的柱子，左边最多就能够扩展到k+1位置。 又因为当前柱子（i）也是小于刚刚弹出的元素（j）的，所以j位置右边的柱子最多也就扩展到i位置。。所以我们可以得到面积计算公式：(i - k - 1) * height[j]。
而在数组遍历完之后，栈中还剩下的数值，它的右边已经不能继续扩展了，所以只能是数组的长度值，所以此时的面积公式是（数组长度 - k - 1） * height[j]。

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>(); //单调递减栈,压入的是下标
        int size = heights.length;
        int max = -1;
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) { //维持单调递减栈的结构
                int j = stack.pop();
                int k = stack.isEmpty()? -1 : stack.peek();
                int res = (i - k - 1) * heights[j]; // i - （k + 1）
                max = Math.max(res, max);
            }
            stack.push(i);
        }
        //最后栈中可能还有元素，进行结算
        while (!stack.isEmpty()) {
            int j = stack.pop();
            int k = stack.isEmpty()? -1 : stack.peek();
            int res = (size - k - 1) * heights[j];
            max = Math.max(max, res);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三、队列的运用

题目：生成窗口最大数值

在线OJ链接

题意：给定一个数组，和一个窗口的大小，从左到右遍历数组，每次移动一个位置，输出窗口中的最大值。

分析：这道题也是一点点“单调”的感觉，也就是单调队列。我们可以用一个双链表或者是数组，用来存储当前元素的下标。队尾到队头，保持升序的状态。

值得注意的是：我们需要注意当前队列的最大值，是否还在窗口的范围内，所以队列里存储不是数据元素，而是对应下标。

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] nums = in.readLine().split(" ");
        int n = Integer.parseInt(nums[0]);
        int w = Integer.parseInt(nums[1]);
        
        nums = in.readLine().split(" ");
        LinkedList<Integer> qmax = new LinkedList<>(); //最大窗口值结构，单调队列结构
        for (int i = 0; i < n; i++) {
            while (qmax.size() != 0 && Integer.parseInt(nums[qmax.getLast()]) <
                   Integer.parseInt(nums[i])) {
                qmax.removeLast();
            }
            qmax.addLast(i);
            if (qmax.getFirst() <= i - w) { //更新当前最大值，是否还在窗口里
                qmax.removeFirst();
            }
            if (i >= w - 1) { //超过窗口值后，就应该输出最大值
                System.out.print(Integer.parseInt(nums[qmax.getFirst()]) + " ");
            }
        }
        in.close();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

好啦，本期更新就到此结束啦！关于单调栈的OJ题，可以去刷题网站上搜一搜，多练习几道题就能理解其中的奥妙。下期见啦，拜拜！！！