AI summary
type
status
date
slug
summary
category
tags
icon
password

考察先进先出性质

队列常见考点主要是元素「先进先出」的顺序特性，比如维护队列内的元素在「时序上」的某些性质，下面是几道例题，队列充当「滑动窗口」的作用。

933. 最近的请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
  • RecentCounter() 初始化计数器，请求数为 0 。
  • int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
这题很简单，和 346. 数据流中的移动平均值 有点类似，要求动态维护队列中的元素。

队列相关的设计题

队列相关的设计题也是一大重点，但不算很难，下面是几道例题。

622. 设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。
这道题考察的是普通队列的实现，底层可以用链表或数组实现，用链表实现比较简单，用数组的话要用到环形数组的技巧。直接看代码吧。
注意：环形数组需要多留一个空位 self.q = [0] * (k + 1)，不然无法区分空和满。

641. 设计循环双端队列

和上面差不多，略了。

1670. 设计前中后队列

请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。
请你完成 FrontMiddleBack 类：
  • FrontMiddleBack() 初始化队列。
  • void pushFront(int val) 将 val 添加到队列的 最前面 。
  • void pushMiddle(int val) 将 val 添加到队列的 正中间 。
  • void pushBack(int val) 将 val 添加到队里的 最后面 。
  • int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 1 。
  • int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 1 。
  • int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 1 。
请注意当有 两个 中间位置的时候，选择靠前面的位置进行操作。比方说：
  • 将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。
  • 从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。
这题有点难度，主要是细节不好把控。常规的队列只能在收尾进行操作，想在中间操作队列，需要在底层把队列切分成 left, right 两个列表，但这里的细节问题就是元素为奇数时两个链表中元素的分配问题。
多实现一个函数 balance 专门用于平衡左右两边的队列，每次操作后都平衡一下，逻辑就很清晰。

2073. 买票需要的时间

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到  队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
既然是排队问题，你用一个队列模拟整个买票过程，然后数一数过了多少秒就行了，不过时间空间复杂度就高了。
动动脑子可以想到更高效的方式：
第 k 个人离开的时间，其实就是从开始到这个人买完票之后，卖出的总票数。那么第 k 个人买完票之后，总共卖了多少票呢？
我们可以对每个人的下标 i 分类讨论：
  • 如果这个人初始在第 k 个人的前方，或者这个人恰好为第 k 个人，即 i≤k，此时在第 k 个人买完票之前他最多可以购买 tickets[k] 张。考虑到他想要购买的票数，那么他买票所需时间即为 min(tickets[k],tickets[i])；
  • 如果这个人初始在第 k 个人的后方，即 i>k，此时在第 k 个人买完票之前他最多可以购买 tickets[k]−1 张。考虑到他想要购买的票数，那么他买票所需时间即为 min(tickets[k]−1,tickets[i])。
我们遍历每个人的下标，按照上述方式计算并维护每个人买票所需时间之和，即可得到第 k 个人买完票所需的时间，我们返回该值作为答案。