一、队列基础知识 {#一-队列基础知识}

1. 队列概念 {#1--队列概念}

• 略

二、队列知识扩展 {#二-队列知识扩展}

1. 队列的知识 {#1--队列的知识}

• 略。

队列题目 | 队列的应用 {#队列题目---队列的应用}

题目一：滑动窗口的平均值 {#题目一-滑动窗口的平均值}

  请实现如下类型MovingAverage，计算滑动窗口中所有数字的平均值，该类型构造函数的参数确定滑动窗口的大小，每次调用成员函数next时都会在滑动窗口中添加一个整数，并返回滑动窗口中所有数字的平均值。

public MovingAverage {
    public MovingAverage (int size);
    public double next(int val);
}

  例如，假设滑动窗口的大小为3。第1次调用next函数时在滑动窗口中添加整数1，此时窗口中只有一个数字1，因此返回平均值1。第2次调用next函数时添加整数2，此时窗口中有两个数字1和2，因此返回平均值1.5。第3次调用next函数时添加数字3，此时有3个数字1、2、3，因此返回平均值2。第4次调用next函数时添加数字4，由于受到窗口大小的限制，滑动窗口中最多只能有3个数字，因此第1个数字1将滑 出窗口，此时窗口中包含3个数字2、3、4，返回平均值3。

题目分析 {#题目分析}

难度： 略
思路： 略

参考代码 {#参考代码}

Tips：2024-06-14 17:02 {#Tips-2024-06-14-17-02}

题目二：最近请求次数 {#题目二-最近请求次数}

  题目：请实现如下类型RecentCounter，它是统计过去3000ms内的请求次数的计数器。该类型的构造函数RecentCounter初始化计数器，请求数初始化为0；函数ping(int t)在时间t添加一个新请求（t表示以毫秒为单位的时间），并返回过去3000ms内（时间范围为[t-3000，t]）发生的所有请求数。假设每次调用函数ping的参数t都比之前调用的参数值大。

public RecentAverage {
    public RecentAverage ();
    public int ping(int t);
}

  例如，在初始化一个RecentCounter计数器之后，ping(1)的返回值是1，因为时间范围[-2999，1]只有1个请求；ping(10)的返回值是2，因为时间范围[-2990，10]有2个请求；ping(3001)的返回值是3，因为时间范围[1，3001]有3个请求；ping(3002)的返回值是3，因为时间范围[2，3002]有3个请求，发生在时间1的请求已经不在这个时间范围内。

题目分析 {#题目分析-}

难度： 略
思路： 略

参考代码 {#参考代码-}

Tips：2024-08-06 18:00 {#Tips-2024-08-06-18-00}

队列题目 | 二叉树的广度优先搜索 {#队列题目---二叉树的广度优先搜索}

题目一：在完全二叉树中添加节点 {#题目一-在完全二叉树中添加节点}

  题目：在完全二叉树中，除最后一层之外其他层的节点都是满 的（第n层有2n-1个节点）。最后一层的节点可能不满，该层所有的 节点尽可能向左边靠拢。例如，图中的4棵二叉树均为完全二叉 树。实现数据结构CBTInserter有如下3种方法。

• 构造函数CBTInserter (TreeNode root)，用一棵完全二叉树的根节点初始化该数据结构。
• 函数insert (int v)在完全二叉树中添加一个值为v的节点，并返回被插入节点的父节点。例如，在如图(a)所示的完全二叉树中添加一个值为7的节点之后，二叉树如图(b)所示，并返回节点3。在如图(b)所示的完全二叉树中添加一个值为8的节点之后，二叉树如图(c)所示，并返回节点4。在如图(c)所示 的完全二叉树中添加节点9会得到如图(d)所示的二叉树并返回节点4。
• 函数get_root()返回完全二叉树的根节点。
  

题目分析 {#题目分析--}

难度： 略
思路： 略

参考代码 {#参考代码--}

Tips：2024-08-06 18:16 {#Tips-2024-08-06-18-16}

题目二：二叉树中每层的最大值 {#题目二-二叉树中每层的最大值}

  题目：输入一棵二叉树，请找出二叉树中每层的最大值。例如，输入图中的二叉树，返回各层节点的最大值[3，4，9]。

题目分析 {#题目分析---}

难度： 略
思路： 略

参考代码 {#参考代码---}

Tips：2024-09-02 15:05 {#Tips-2024-09-02-15-05}

题目三：二叉树最低层最左边的值 {#题目三-二叉树最低层最左边的值}

  题目：如何在一棵二叉树中找出它最低层最左边节点的值？假设二叉树中最少有一个节点。例如，在如图所示的二叉树中最低层最左边一个节点的值是5。

题目分析 {#题目分析----}

难度： 略
思路： 略

参考代码 {#参考代码----}

Tips：2024-09-02 15:05 {#Tips-2024-09-02-15-05-}

题目四：二叉树的右侧视图 {#题目四-二叉树的右侧视图}

  题目：给定一棵二叉树，如果站在该二叉树的右侧，那么从上到下看到的节点构成二叉树的右侧视图。例如，图7.6中二叉树的右侧视图包含节点8、节点10和节点7。请写一个函数返回二叉树的右侧视图节点的值。

题目分析 {#题目分析-----}

难度： 略
思路： 略

参考代码 {#参考代码-----}

Tips：2024-09-02 15:05 {#Tips-2024-09-02-15-05--}

2. 附加题 {#2--附加题}

队列题目 | 队列 & 栈 {#队列题目---队列---栈}

题目一：用两个栈实现队列 {#题目一-用两个栈实现队列}

  用两个栈来实现一个队列，使用n个元素来完成n次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

题目分析 {#题目分析------}

难度： ⭐
思路： 此题很容易想到，入栈时放入stack1，出栈时，借助stack2存入stack1依次出栈的元素，最后出栈第一个元素，再将stack2元素依次入栈stack1中。这个过程中，不难发现，stack2元素依次出栈到stack1的过程是不必要的；stack1用于存放入栈数据，stack2用于出栈数据，当stack2元素出栈完时，再次出栈时将stack1的所有元素出栈到stack2，再由stack2进行出栈操作即可，如此可以省下一定操作次数。

参考代码 {#参考代码------}

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
//入栈操作
public void push(int node) {
    stack1.push(node);
}

//出栈操作
public int pop() {
    if(stack2.size()&amp;lt;=0){
        while(stack1.size()!=0){
            stack2.push(stack1.pop());
        }
    }
return stack2.pop();
}

}

Tips：2024-09-11 18:35 {#Tips-2024-09-11-18-35}

题目二：包含min函数的栈 {#题目二-包含min函数的栈}

  定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
  此栈包含的方法有：
    1. push(value):将value压入栈中
    2. pop():弹出栈顶元素
    3. top():获取栈顶元素
    4. min():获取栈中最小元素

题目分析 {#题目分析-------}

难度： ⭐
思路： 略

参考代码 {#参考代码-------}

Tips：2024-09-11 18:39 {#Tips-2024-09-11-18-39}

三、章节小结 {#三-章节小结}

  略