队列是BFS的引擎，单调队列是滑动窗口的最优解
队列（Queue）是一种先进先出（FIFO）的数据结构，只能从队尾入队、队首出队。队列是 BFS（广度优先搜索）的天然搭档，也是任务调度、消息传递等场景的基础。面试中，队列的进阶应用——单调队列，是滑动窗口最大值等问题的最优解。
# collections.deque（推荐，O(1)两端操作）
from collections import deque
q = deque()
q.append(1) # 右端入队
q.appendleft(2) # 左端入队
q.popleft() # 左端出队
q.pop() # 右端出队
q[0] # 看队首
len(q) # 长度
# queue.Queue（线程安全，多线程用）
from queue import Queue
q = Queue()
q.put(1)
q.get()题目描述：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个元素。请返回滑动窗口中的最大值。
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
from collections import deque
dq = deque() # 存索引，对应值单调递减
result = []
for i, num in enumerate(nums):
# 移除超出窗口的队首
while dq and dq[0] <= i - k:
dq.popleft()
# 维护单调递减：弹出队尾所有 ≤ 当前值的
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
# 窗口形成后开始记录答案
if i >= k - 1:
result.append(nums[dq[0]])
return result时间复杂度：O(n) — 每个元素最多入队出队各一次
空间复杂度：O(k) — 队列最多 k 个元素
题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
class MyStack:
def __init__(self):
from collections import deque
self.q1 = deque()
self.q2 = deque()
def push(self, x: int) -> None:
self.q2.append(x)
while self.q1:
self.q2.append(self.q1.popleft())
self.q1, self.q2 = self.q2, self.q1
def pop(self) -> int:
return self.q1.popleft()
def top(self) -> int:
return self.q1[0]
def empty(self) -> bool:
return not self.q1push：O(n) | pop/top/empty：O(1)
空间复杂度：O(n)
题目描述：设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO 原则并且队尾被连接在队首之后以形成一个循环，利用固定大小的数组实现。
class MyCircularQueue:
def __init__(self, k: int):
self.capacity = k + 1
self.arr = [0] * self.capacity
self.front = 0
self.rear = 0
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.arr[self.rear] = value
self.rear = (self.rear + 1) % self.capacity
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.front = (self.front + 1) % self.capacity
return True
def Front(self) -> int:
if self.isEmpty():
return -1
return self.arr[self.front]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self.arr[(self.rear - 1) % self.capacity]
def isEmpty(self) -> bool:
return self.front == self.rear
def isFull(self) -> bool:
return (self.rear + 1) % self.capacity == self.front时间复杂度：所有操作 O(1)
空间复杂度：O(k)