【练习】队列的经典习题
考察先进先出性质
队列常见考点主要是元素「先进先出」的顺序特性，比如维护队列内的元素在「时序上」的某些性质，下面是几道例题，队列充当「滑动窗口」的作用。
933. 最近的请求次数
933. 最近的请求次数 | 力扣 | LeetCode | 🟢
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
RecentCounter()初始化计数器，请求数为 0 。int ping(int t)在时间t添加一个新请求，其中t表示以毫秒为单位的某个时间，并返回过去3000毫秒内发生的所有请求数（包括新请求）。确切地说，返回在[t-3000, t]内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例 1：
输入： ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] 输出： [null, 1, 2, 3, 3]解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
提示：
1 <= t <= 109- 保证每次对
ping调用所使用的t值都 严格递增 - 至多调用
ping方法104次
基本思路
这题很简单，和 346. 数据流中的移动平均值 有点类似，要求动态维护队列中的元素。
详细题解：
解法代码
from queue import Queue
class RecentCounter:
def __init__(self):
self.q = Queue()
def ping(self, t: int) -> int:
self.q.put(t)
while self.q.queue[0] < t - 3000:
# t 是递增的，所以可以从队头删除 3000 毫秒之前的请求
self.q.get()
return self.q.qsize()类似题目：
队列相关的设计题
队列相关的设计题也是一大重点，但不算很难，下面是几道例题。
622. 设计循环队列
622. 设计循环队列 | 力扣 | LeetCode | 🟠
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4
提示：
- 所有的值都在 0 至 1000 的范围内；
- 操作数将在 1 至 1000 的范围内；
- 请不要使用内置的队列库。
基本思路
这道题考察的是普通队列的实现，底层可以用链表或数组实现，用链表实现比较简单，用数组的话要用到环形数组的技巧。具体可以参见 用链表实现队列/栈 和 用数组实现环形队列 两篇文章。
详细题解：
解法代码
from collections import deque
# 底层用数组实现队列
class ArrayQueue:
INIT_CAP = 2
def __init__(self, init_cap=INIT_CAP):
self.size = 0
self.data = [None] * init_cap
self.first = 0
self.last = 0
# 不传参数，默认大小为 INIT_CAP
# Initializer with default capacity
# 增
def enqueue(self, e):
if self.size == len(self.data):
self.resize(self.size * 2)
self.data[self.last] = e
self.last += 1
if self.last == len(self.data):
self.last = 0
self.size += 1
# 删
def dequeue(self):
if self.is_empty():
raise Exception('Queue underflow')
if self.size == len(self.data) // 4:
self.resize(len(self.data) // 2)
old_val = self.data[self.first]
self.data[self.first] = None
self.first += 1
if self.first == len(self.data):
self.first = 0
self.size -= 1
return old_val
def resize(self, new_cap):
temp = [None] * new_cap
# first ----- last
# --- last first ---
for i in range(self.size):
temp[i] = self.data[(self.first + i) % len(self.data)]
self.first = 0
self.last = self.size
self.data = temp
# 查
def peek_first(self):
if self.is_empty():
raise Exception('Queue underflow')
return self.data[self.first]
def peek_last(self):
if self.is_empty():
raise Exception('Queue underflow')
if self.last == 0:
return self.data[len(self.data) - 1]
return self.data[self.last - 1]
def size(self):
return self.size
def is_empty(self):
return self.size == 0
class MyCircularQueue:
def __init__(self, k):
self.q = ArrayQueue(k)
self.max_cap = k
def enQueue(self, value):
if self.q.size == self.max_cap:
return False
self.q.enqueue(value)
return True
def deQueue(self):
if self.q.is_empty():
return False
self.q.dequeue()
return True
def Front(self):
if self.q.is_empty():
return -1
return self.q.peek_first()
def Rear(self):
if self.q.is_empty():
return -1
return self.q.peek_last()
def isEmpty(self):
return self.q.is_empty()
def isFull(self):
return self.q.size == self.max_cap641. 设计循环双端队列
641. 设计循环双端队列 | 力扣 | LeetCode | 🟠
设计实现双端队列。
实现 MyCircularDeque 类:
MyCircularDeque(int k)：构造函数,双端队列最大为k。boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回true，否则返回false。boolean insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回true，否则返回false。boolean deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回true，否则返回false。boolean deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回true，否则返回false。int getFront())：从双端队列头部获得一个元素。如果双端队列为空，返回-1。int getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回-1。boolean isEmpty()：若双端队列为空，则返回true，否则返回false。boolean isFull()：若双端队列满了，则返回true，否则返回false。
示例 1：
输入 ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []] 输出 [null, true, true, true, false, 2, true, true, true, 4]解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4
提示：
1 <= k <= 10000 <= value <= 1000insertFront,insertLast,deleteFront,deleteLast,getFront,getRear,isEmpty,isFull调用次数不大于2000次
基本思路
这道题考察的是双端队列的实现，底层可以用链表或数组实现，用链表实现比较简单，用数组的话要用到 环形数组 的技巧。
详细题解：
解法代码
class MyArrayDeque:
INIT_CAP = 2
# 不传参数，默认大小为 INIT_CAP
def __init__(self, init_cap=INIT_CAP):
self.size = 0
self.data = [None] * init_cap
# last 是下一次应该添加元素的索引
# first----last, [first, last)
# 比如 first = 1，last = 3，size = 2
self.first = self.last = 0
# 从头部获取元素
def getFirst(self):
if self.isEmpty():
raise IndexError("getFirst from empty deque")
return self.data[self.first]
# 从尾部获取元素
def getLast(self):
if self.isEmpty():
raise IndexError("getLast from empty deque")
if self.last == 0:
return self.data[len(self.data) - 1]
return self.data[self.last - 1]
# 从头部插入元素
def addFirst(self, e):
if self.size == len(self.data):
self.resize(self.size * 2)
# 情况一：first----last
# 情况二：---last first---
# 左移 first，所以 first == 0 是一种特殊情况
if self.first == 0:
self.first = len(self.data) - 1
else:
self.first -= 1
# 插入元素
self.data[self.first] = e
self.size += 1
# 从尾部插入元素
def addLast(self, e):
if self.size == len(self.data):
self.resize(self.size * 2)
# 插入元素
self.data[self.last] = e
self.last += 1
if self.last == len(self.data):
self.last = 0
self.size += 1
# 从头部删除元素
def removeFirst(self):
if self.isEmpty():
raise IndexError("removeFirst from empty deque")
if self.size == len(self.data) // 4:
self.resize(len(self.data) // 2)
old_val = self.data[self.first]
self.data[self.first] = None
self.first += 1
if self.first == len(self.data):
self.first = 0
self.size -= 1
return old_val
# 从尾部删除元素
def removeLast(self):
if self.isEmpty():
raise IndexError("removeLast from empty deque")
if self.size == len(self.data) // 4:
self.resize(len(self.data) // 2)
# 情况一：first----last
# 情况二：---last first---
# 左移 last，当 last == 0 的时候是特殊情况
if self.last == 0:
self.last = len(self.data) - 1
else:
self.last -= 1
old_val = self.data[self.last]
# 删除元素
self.data[self.last] = None
self.size -= 1
return old_val
def getSize(self):
return self.size
def isEmpty(self):
return self.size == 0
def resize(self, new_cap):
temp = [None] * new_cap
for i in range(self.size):
temp[i] = self.data[(self.first + i) % len(self.data)]
self.first = 0
self.last = self.size
self.data = temp
class MyCircularDeque:
def __init__(self, k):
self.cap = k
self.list = MyArrayDeque()
# Adds an item at the front of Deque. Return true if the operation is successful.
def insertFront(self, value):
if self.list.getSize() == self.cap:
return False
self.list.addFirst(value)
return True
# Adds an item at the rear of Deque. Return true if the operation is successful.
def insertLast(self, value):
if self.list.getSize() == self.cap:
return False
self.list.addLast(value)
return True
# Deletes an item from the front of Deque. Return true if the operation is successful.
def deleteFront(self):
if self.list.isEmpty():
return False
self.list.removeFirst()
return True
# Deletes an item from the rear of Deque. Return true if the operation is successful.
def deleteLast(self):
if self.list.isEmpty():
return False
self.list.removeLast()
return True
# Get the front item from the deque.
def getFront(self):
if self.list.isEmpty():
return -1
return self.list.getFirst()
# Get the last item from the deque.
def getRear(self):
if self.list.isEmpty():
return -1
return self.list.getLast()
# Checks whether the circular deque is empty or not.
def isEmpty(self):
return self.list.isEmpty()
# Checks whether the circular deque is full or not.
def isFull(self):
return self.list.getSize() == self.cap1670. 设计前中后队列
1670. 设计前中后队列 | 力扣 | LeetCode | 🟠
请你设计一个队列，支持在前，中，后三个位置的 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]。
示例 1：
输入： ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"] [[], [1], [2], [3], [4], [], [], [], [], []] 输出： [null, null, null, null, null, 1, 3, 4, 2, -1]解释：
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1); // [1]
q.pushBack(2); // [1, 2]
q.pushMiddle(3); // [1, 3, 2]
q.pushMiddle(4); // [1, 4, 3, 2]
q.popFront(); // 返回 1 -> [4, 3, 2]
q.popMiddle(); // 返回 3 -> [4, 2]
q.popMiddle(); // 返回 4 -> [2]
q.popBack(); // 返回 2 -> []
q.popFront(); // 返回 -1 -> [] （队列为空）
提示：
1 <= val <= 109- 最多调用
1000次pushFront，pushMiddle，pushBack，popFront，popMiddle和popBack。
基本思路
这题有点难度，主要是细节不好把控。常规的队列只能在首尾进行操作，想在中间操作队列，需要在底层把队列切分成 left, right 两个列表，但这里的细节问题就是元素为奇数时两个链表中元素的分配问题。
直接看代码吧，注释很详细。
详细题解：
解法代码
from collections import deque
class FrontMiddleBackQueue:
# 用两个列表表示队列的左右两部分，一遍从中间操作元素
def __init__(self):
self.left = deque()
self.right = deque()
# 维护左边少右边多的状态，每次增删元素之后都要执行一次
def balance(self):
# 右边最多比左边多一个元素
if len(self.right) > len(self.left) + 1:
# 右边多，匀一个给左边
self.left.append(self.right.popleft())
if len(self.left) > len(self.right):
# 左边多，匀一个给右边
self.right.appendleft(self.left.pop())
def pushFront(self, val: int) -> None:
self.left.appendleft(val)
self.balance()
def pushMiddle(self, val: int) -> None:
if self.size() % 2 == 0:
# 如果有偶数个元素时，pushMiddle 优先向右边添加
self.right.appendleft(val)
else:
self.left.append(val)
self.balance()
def pushBack(self, val: int) -> None:
self.right.append(val)
self.balance()
def popFront(self) -> int:
if self.size() == 0:
return -1
if self.size() == 1:
# 如果只有 1 个元素，popFront 的时候，要去右边删除
return self.right.popleft()
e = self.left.popleft()
self.balance()
return e
def popMiddle(self) -> int:
if self.size() == 0:
return -1
if self.size() % 2 == 0:
e = self.left.pop()
else:
# 如果有奇数个元素时，popMiddle 优先从右边删除
e = self.right.popleft()
self.balance()
return e
def popBack(self) -> int:
if self.size() == 0:
return -1
e = self.right.pop()
self.balance()
return e
def size(self) -> int:
return len(self.left) + len(self.right)2073. 买票需要的时间
2073. 买票需要的时间 | 力扣 | LeetCode | 🟢
有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
示例 1：
输入：tickets = [2,3,2], k = 2 输出：6 解释： - 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。 - 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。 位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。
示例 2：
输入：tickets = [5,1,1,1], k = 0 输出：8 解释： - 第一轮，队伍中的每个人都买到一张票，队伍变为 [4, 0, 0, 0] 。 - 接下来的 4 轮，只有位置 0 的人在买票。 位置 0 的人成功买到 5 张票，用掉 4 + 1 + 1 + 1 + 1 = 8 秒。
提示：
n == tickets.length1 <= n <= 1001 <= tickets[i] <= 1000 <= k < n
基本思路
既然是排队问题，你用一个队列模拟整个买票过程，然后数一数过了多少秒就行了，不过时间空间复杂度就高了。
稍微思考一下可以想到更高效的方式：
首先，第 k 个人离开的时间，其实就是从开始到这个人买完票之后，卖出的总票数。
那么第 k 个人买完票之后，总共卖了多少票呢？
排在 k 之前的人最多买了 tickets[k] 张票；而排在 k 之后的人最多买了 tickets[k] - 1 张票。为什么说「最多」呢，因为有的人可能需要的票比较少，买完就直接走了。
综上，思路就出来了，看代码理解吧。
详细题解：
解法代码
class Solution:
def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
res = 0
for i in range(len(tickets)):
if i <= k:
# 前面的人最多买了 tickets[k] 张票
res += min(tickets[k], tickets[i])
else:
# 后面的人最多买了 tickets[k] - 1 张票
res += min(tickets[k] - 1, tickets[i])
return res
