队列、双端队列、双栈队列与滑动窗口最大值
一、队列到底解决什么问题？
- o **队列（Queue）是一种先进先出（FIFO）**的线性结构：
- o 入队（enqueue）：从尾部插入
- o 出队（dequeue）：从头部删除
- o 典型应用：
- o 任务调度（按到达时间顺序处理）、宽度优先搜索（BFS）、缓存/异步消息、流式窗口统计（配合单调队列）、生产者-消费者模型等。
二、三种基础实现（数组 / 链表 / 循环数组）
2.1 数组（顺序表）实现：直观但会“搬家”
- o 思路：用数组存数据，用两个指针 head 和 tail 指示队首/队尾。
- o 问题：频繁 dequeue 会导致前半段空间“空了但不能复用”，常见做法是懒移动或定期挪动。
- o 适用：规模可预估、或愿意做循环优化。
# 语言：Python — 简易数组队列（未循环化）
class ArrayQueue:
def __init__(self, capacity=8):
self.data = [None]*capacity
self.head = 0 # 指向当前队首元素
self.tail = 0 # 指向将要插入元素的位置
self.n = 0
def is_empty(self):
return self.n == 0
def is_full(self):
return self.n == len(self.data)
def enqueue(self, x):
if self.is_full():
self._resize(len(self.data)*2)
self.data[self.tail] = x
self.tail += 1
self.n += 1
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty")
x = self.data[self.head]
self.data[self.head] = None
self.head += 1
self.n -= 1
# 可选：当浪费空间过多，触发一次“挪动”或“缩容”
if self.n and self.head > len(self.data)//4 and self.head > self.tail//2:
self._compact()
return x
def _compact(self):
# 把有效区间整体搬到数组前部
new = [None]*len(self.data)
for i in range(self.n):
new[i] = self.data[self.head + i]
self.data = new
self.head, self.tail = 0, self.n
def _resize(self, cap):
new = [None]*cap
for i in range(self.n):
new[i] = self.data[self.head + i]
self.data = new
self.head, self.tail = 0, self.n// 语言：Swift — 简易数组队列（未循环化）
struct ArrayQueue<T> {
private var data: [T?]
private var head = 0
private var tail = 0
private(set) var count = 0
init(_ cap: Int = 8) { data = Array(repeating: nil, count: cap) }
var isEmpty: Bool { count == 0 }
var isFull: Bool { count == data.count }
mutating func enqueue(_ x: T) {
if isFull { resize(data.count * 2) }
data[tail] = x
tail += 1
count += 1
}
mutating func dequeue() -> T {
precondition(!isEmpty, "dequeue from empty")
let v = data[head]!
data[head] = nil
head += 1
count -= 1
if count > 0 && head > data.count/4 && head > tail/2 { compact() }
return v
}
private mutating func compact() {
var newData = Array(repeating: Optional<T>.none, count: data.count)
for i in 0..<count { newData[i] = data[head + i] }
data = newData; head = 0; tail = count
}
private mutating func resize(_ cap: Int) {
var newData = Array(repeating: Optional<T>.none, count: cap)
for i in 0..<count { newData[i] = data[head + i] }
data = newData; head = 0; tail = count
}
}2.2 链表（链式）实现：永远O(1)入队/出队
- o 思路：维护 head 和 tail 两个指针。
- o 优点：不需要搬移元素；enqueue/dequeue 都是 O(1)。
- o 缺点：额外指针开销，不具备数组的局部性。
# 语言：Python — 链式队列（单链表，tail 指向尾节点）
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
class LinkedQueue:
def __init__(self):
self.head = self.tail = None
self.n = 0
def is_empty(self):
return self.n == 0
def enqueue(self, x):
node = Node(x)
if self.tail is None: # 空队列
self.head = self.tail = node
else:
self.tail.next = node
self.tail = node
self.n += 1
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty")
x = self.head.val
self.head = self.head.next
if self.head is None: # 出队后队空，tail 也要清空
self.tail = None
self.n -= 1
return x// 语言：Swift — 链式队列
final class QNode<T> { var val: T; var next: QNode<T>?; init(_ v: T, _ n: QNode<T>? = nil){ val=v; next=n } }
final class LinkedQueue<T> {
private var head: QNode<T>? = nil
private var tail: QNode<T>? = nil
private(set) var count = 0
var isEmpty: Bool { count == 0 }
func enqueue(_ x: T) {
let node = QNode(x)
if tail == nil { head = node; tail = node }
else { tail!.next = node; tail = node }
count += 1
}
func dequeue() -> T {
precondition(!isEmpty, "dequeue from empty")
let v = head!.val
head = head!.next
if head == nil { tail = nil }
count -= 1
return v
}
}2.3 循环队列（Circular Queue）：不挪动也不浪费
- o 核心：把数组看成一个环，下标通过 % capacity 回绕。
- o 两种常见定义：
- 1. 空一格：以 (tail + 1) % cap == head 作为“满”的判定，空间利用率 cap-1。
- 2. 记录 size：用 size 区分空/满，空间利用率 cap，实现更直观。
- o 这里用记录 size版本。
# 语言：Python — 循环队列（记录 size）
class CircularQueue:
def __init__(self, capacity=8):
self.data = [None]*capacity
self.cap = capacity
self.head = 0 # 指向当前队首
self.tail = 0 # 指向下一个写入位置
self.size = 0
def is_empty(self): return self.size == 0
def is_full(self): return self.size == self.cap
def enqueue(self, x):
if self.is_full(): self._resize(self.cap * 2)
self.data[self.tail] = x
self.tail = (self.tail + 1) % self.cap
self.size += 1
def dequeue(self):
if self.is_empty(): raise IndexError("dequeue from empty")
x = self.data[self.head]
self.data[self.head] = None
self.head = (self.head + 1) % self.cap
self.size -= 1
if 0 < self.size <= self.cap // 4: self._resize(max(8, self.cap // 2))
return x
def _resize(self, new_cap):
new = [None]*new_cap
for i in range(self.size):
new[i] = self.data[(self.head + i) % self.cap]
self.data = new
self.cap = new_cap
self.head = 0
self.tail = self.size// 语言：Swift — 循环队列（记录 size）
struct CircularQueue<T> {
private var data: [T?]
private var head = 0, tail = 0, size = 0
private var cap: Int { data.count }
init(_ capacity: Int = 8) { data = Array(repeating: nil, count: max(8, capacity)) }
var isEmpty: Bool { size == 0 }
var isFull: Bool { size == cap }
mutating func enqueue(_ x: T) {
if isFull { resize(cap * 2) }
data[tail] = x
tail = (tail + 1) % cap
size += 1
}
mutating func dequeue() -> T {
precondition(!isEmpty, "dequeue from empty")
let v = data[head]!
data[head] = nil
head = (head + 1) % cap
size -= 1
if size > 0 && size <= cap/4 { resize(max(8, cap/2)) }
return v
}
private mutating func resize(_ newCap: Int) {
var newData = Array(repeating: Optional<T>.none, count: newCap)
for i in 0..<size { newData[i] = data[(head + i) % cap] }
data = newData; head = 0; tail = size
}
}三、双端队列（Deque）：两头都能进出的“队列加强版”
- o 操作：push_front / push_back / pop_front / pop_back
- o 实现：数组双指针或双向链表。
- o 应用：滑动窗口、LRU 的双向链表骨架、回文检验两端收缩等。
# 语言：Python — 双端队列（简化数组环实现）
class Deque:
def __init__(self, capacity=8):
self.data = [None]*capacity
self.cap = capacity
self.front = 0 # 指向当前队首
self.back = 0 # 指向下一个写入的“队尾位置”
self.size = 0
def _idx(self, i): return i % self.cap
def is_empty(self): return self.size == 0
def _grow(self):
new = [None]*(self.cap*2)
for i in range(self.size):
new[i] = self.data[(self.front + i) % self.cap]
self.data = new; self.cap *= 2; self.front = 0; self.back = self.size
def push_back(self, x):
if self.size == self.cap: self._grow()
self.data[self.back] = x
self.back = self._idx(self.back + 1)
self.size += 1
def push_front(self, x):
if self.size == self.cap: self._grow()
self.front = self._idx(self.front - 1)
self.data[self.front] = x
self.size += 1
def pop_front(self):
if self.is_empty(): raise IndexError("pop_front from empty")
x = self.data[self.front]; self.data[self.front] = None
self.front = self._idx(self.front + 1); self.size -= 1; return x
def pop_back(self):
if self.is_empty(): raise IndexError("pop_back from empty")
self.back = self._idx(self.back - 1)
x = self.data[self.back]; self.data[self.back] = None
self.size -= 1; return x// 语言：Swift — 双端队列（双向链表骨架）
final class DNode<T> { var val: T; var prev: DNode<T>?; var next: DNode<T>?; init(_ v: T){ val=v } }
final class Deque<T> {
private var head: DNode<T>? = nil // 头部（队首）
private var tail: DNode<T>? = nil // 尾部（队尾）
private(set) var count = 0
var isEmpty: Bool { count == 0 }
func pushFront(_ x: T) {
let n = DNode(x)
if head == nil { head = n; tail = n }
else { n.next = head; head!.prev = n; head = n }
count += 1
}
func pushBack(_ x: T) {
let n = DNode(x)
if tail == nil { head = n; tail = n }
else { tail!.next = n; n.prev = tail; tail = n }
count += 1
}
func popFront() -> T {
precondition(!isEmpty, "popFront from empty")
let v = head!.val
head = head!.next
head?.prev = nil
if head == nil { tail = nil }
count -= 1; return v
}
func popBack() -> T {
precondition(!isEmpty, "popBack from empty")
let v = tail!.val
tail = tail!.prev
tail?.next = nil
if tail == nil { head = nil }
count -= 1; return v
}
}四、双栈实现队列：用“栈”把“队列”装出来
- o 维护两个栈：sIn（仅入）和 sOut（仅出）
- o 出队时：若 sOut 为空，把 sIn 逐个弹出并压入 sOut（翻转顺序），随后从 sOut 弹出即是队首。
- o 摊还复杂度：每个元素最多被搬运两次，均摊 O(1)。
# 语言：Python — 双栈队列
class MyQueue:
def __init__(self):
self._in, self._out = [], []
def push(self, x: int):
self._in.append(x)
def _move(self):
if not self._out:
while self._in:
self._out.append(self._in.pop())
def pop(self) -> int:
self._move()
return self._out.pop()
def peek(self) -> int:
self._move()
return self._out[-1]
def empty(self) -> bool:
return not self._in and not self._out// 语言：Swift — 双栈队列
struct MyQueue {
private var sIn: [Int] = []
private var sOut: [Int] = []
mutating func push(_ x: Int) { sIn.append(x) }
private mutating func move() {
if sOut.isEmpty { while let v = sIn.popLast() { sOut.append(v) } }
}
mutating func pop() -> Int { move(); return sOut.removeLast() }
mutating func peek() -> Int { move(); return sOut.last! }
var empty: Bool { sIn.isEmpty && sOut.isEmpty }
}五、单调队列（Monotonic Queue）：滑动窗口最大值的王牌
单调队列常用一个双端队列来维护候选下标，队列中的元素值单调递减，这样队首永远是当前窗口最大值的下标。
- o 处理新元素 nums[i] 时：
- 1. 弹出队尾：把所有小于等于 nums[i] 的下标从队尾移除（它们不可能再成为最大值）；
- 2. 加入队尾：把下标 i 放入；
- 3. 移出窗口：若队首的下标 < i-k+1，说明已离开窗口，弹出；
- 4. 当 i >= k-1 时，窗口形成，输出 nums[deque.front]。
# 语言：Python — 滑动窗口最大值（单调队列）
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
dq = deque() # 存“下标”，保持 nums[dq[0]] >= nums[dq[1]] >= ...
ans = []
for i, x in enumerate(nums):
# 1) 弹出所有比 x 小的队尾元素
while dq and nums[dq[-1]] <= x:
dq.pop()
# 2) 新下标入队尾
dq.append(i)
# 3) 队首过期则弹出
if dq[0] <= i - k:
dq.popleft()
# 4) 窗口就绪则输出
if i >= k - 1:
ans.append(nums[dq[0]])
return ans// 语言：Swift — 滑动窗口最大值（单调队列）
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
var dq: [Int] = [] // 存索引，保持 nums[dq[0]] >= nums[dq[1]] >= ...
var res: [Int] = []
for i in nums.indices {
// 1) 弹出小于等于 nums[i] 的队尾
while let last = dq.last, nums[last] <= nums[i] { _ = dq.popLast() }
// 2) 入队尾
dq.append(i)
// 3) 队首过期移除
if dq.first! <= i - k { dq.removeFirst() }
// 4) 窗口形成
if i >= k - 1 { res.append(nums[dq[0]]) }
}
return res
}六、复杂度与边界清单
场景时间复杂度额外空间要点与坑位数组队列（未循环）enqueue/dequeue 摊还 O(1)O(n)注意“空洞”与挪动/缩容时机链式队列O(1)O(n)出队空时同步置空 tail循环队列O(1)O(n)% capacity 回绕；判满/判空策略统一双端队列O(1)O(n)两端 push/pop 的下标回绕或链指针维护双栈队列均摊 O(1)O(n)只在 sOut 空时搬运，避免每次搬运单调队列O(n)O(k)每个元素最多入队出队一次，维护递减性
七、练习题
练习 1：设计循环队列
题意：实现
enQueue/deQueue/Front/Rear/isEmpty/isFull。
思路：记录 size 的循环数组实现，见 §2.3。
正确性：head 指向队首，tail 指向下一个写入位置；回绕使用 % cap。
复杂度：所有操作 O(1)。
代码：见 §2.3（Swift & Python 均提供）。
练习 2：用两个栈实现队列
题意：实现 push/pop/peek/empty，要求摊还 O(1)。
思路：sIn 入、sOut 出；sOut 空时集中倒腾。
正确性：倒腾一次即顺序翻转，保证 sOut 栈顶是队头。
复杂度：均摊 O(1)。
代码：见 §4（Swift & Python）。
练习 3：滑动窗口最大值
题意：给定数组 nums 与窗口大小 k，返回每个窗口的最大值。
思路：单调队列（递减）；见 §5。
正确性：队首总是当前窗口最大值下标，过期/更小者即时移除。
复杂度：O(n)。
代码：见 §5（Swift & Python）。
练习 4：双端队列基本操作
题意：实现
push_front/push_back/pop_front/pop_back 并通过 10^5 次随机操作压力测试。
思路：数组环或双向链表；参见 §3。
要点：索引回绕、缩扩容策略、空队边界。
代码：见 §3（Swift & Python）。
练习 5：课程表（BFS 拓扑排序）
题意：numCourses 与先修关系 prerequisites，判断是否能完成所有课程。
思路：构建入度表与邻接表，队列做 BFS（入度为 0 入队）。
复杂度：O(V+E)。
# 语言：Python — BFS 拓扑排序
from collections import deque, defaultdict
def can_finish(numCourses: int, prerequisites: list[list[int]]) -> bool:
g = defaultdict(list)
indeg = [0]*numCourses
for a,b in prerequisites:
g[b].append(a)
indeg[a] += 1
q = deque([i for i in range(numCourses) if indeg[i]==0])
taken = 0
while q:
u = q.popleft(); taken += 1
for v in g[u]:
indeg[v] -= 1
if indeg[v]==0: q.append(v)
return taken == numCourses// 语言：Swift — BFS 拓扑排序
func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
var g = Array(repeating: [Int](), count: numCourses)
var indeg = Array(repeating: 0, count: numCourses)
for p in prerequisites { let a = p[0], b = p[1]; g[b].append(a); indeg[a] += 1 }
var q: [Int] = []
for i in 0..<numCourses { if indeg[i] == 0 { q.append(i) } }
var head = 0, taken = 0
while head < q.count {
let u = q[head]; head += 1; taken += 1
for v in g[u] {
indeg[v] -= 1
if indeg[v] == 0 { q.append(v) }
}
}
return taken == numCourses
}八、常见坑位与面试问答
- o 循环队列判满/判空：要么空一格，要么记录 size；混用会错。
- o 链式队列出队为最后一个元素：记得同时置空 tail。
- o 双栈队列：不要每次 pop/peek 都搬运，仅在 sOut 为空时执行搬运。
- o 单调队列边界：
- o 新值入队前一定要弹出更小（或小于等于）的队尾；
- o 过期下标（i-k+1 左边）要及时移除；
- o 维护的是索引而不是值，方便判过期。
- o 扩容/缩容策略：避免频繁搬家造成抖动，设置上下触发阈值更稳。
九、知识小结
- o 队列 = FIFO：尾入头出；实现首选循环数组或链表。
- o 双端队列 = 两头都能进出，是滑动窗口与LRU的好伙伴。
- o 双栈可实现队列：均摊 O(1)，面试常考。
- o 单调队列：O(n) 解决滑动窗口最大值，每个元素最多入队/出队一次。
- o BFS 拓扑排序：入度为 0 入队、逐层释放依赖。