第10章 双端队列与循环队列

学习目标

完成本章学习后，读者将能够：

• 深入理解双端队列的实现原理
• 掌握循环队列的设计与实现
• 理解滑动窗口算法
• 运用双端队列解决实际问题

---

10.1 双端队列深入

10.1.1 双端队列实现

from typing import TypeVar, Generic, Optional, Iterator

T = TypeVar('T')

class Node(Generic[T]):
    def __init__(self, value: T):
        self.value = value
        self.prev: Optional['Node[T]'] = None
        self.next: Optional['Node[T]'] = None

class Deque(Generic[T]):
    """基于双链表的双端队列"""
    
    def __init__(self):
        self._head: Optional[Node[T]] = None
        self._tail: Optional[Node[T]] = None
        self._size: int = 0
    
    def append(self, value: T) -> None:
        """右端添加"""
        node = Node(value)
        if self._tail:
            self._tail.next = node
            node.prev = self._tail
        else:
            self._head = node
        self._tail = node
        self._size += 1
    
    def appendleft(self, value: T) -> None:
        """左端添加"""
        node = Node(value)
        if self._head:
            node.next = self._head
            self._head.prev = node
        else:
            self._tail = node
        self._head = node
        self._size += 1
    
    def pop(self) -> T:
        """右端弹出"""
        if not self._tail:
            raise IndexError("pop from empty deque")
        value = self._tail.value
        self._tail = self._tail.prev
        if self._tail:
            self._tail.next = None
        else:
            self._head = None
        self._size -= 1
        return value
    
    def popleft(self) -> T:
        """左端弹出"""
        if not self._head:
            raise IndexError("popleft from empty deque")
        value = self._head.value
        self._head = self._head.next
        if self._head:
            self._head.prev = None
        else:
            self._tail = None
        self._size -= 1
        return value
    
    def __len__(self) -> int:
        return self._size
    
    def __iter__(self) -> Iterator[T]:
        current = self._head
        while current:
            yield current.value
            current = current.next

10.1.2 滑动窗口算法

from collections import deque

def max_sliding_window(nums: list, k: int) -> list:
    """滑动窗口最大值"""
    result = []
    dq = deque()
    
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        
        if dq[0] <= i - k:
            dq.popleft()
        
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

---

10.2 循环队列

10.2.1 循环队列实现

from typing import TypeVar, Generic, Optional

T = TypeVar('T')

class CircularQueue(Generic[T]):
    """动态扩容的循环队列"""
    
    def __init__(self, capacity: int = 10):
        self._capacity = capacity
        self._items: list = [None] * capacity
        self._front = 0
        self._rear = 0
        self._size = 0
    
    def enqueue(self, item: T) -> None:
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        
        self._items[self._rear] = item
        self._rear = (self._rear + 1) % self._capacity
        self._size += 1
    
    def dequeue(self) -> Optional[T]:
        if self._size == 0:
            return None
        
        item = self._items[self._front]
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        
        if 0 < self._size < self._capacity // 4:
            self._resize(self._capacity // 2)
        
        return item
    
    def _resize(self, new_capacity: int) -> None:
        new_items = [None] * new_capacity
        for i in range(self._size):
            new_items[i] = self._items[(self._front + i) % self._capacity]
        
        self._items = new_items
        self._capacity = new_capacity
        self._front = 0
        self._rear = self._size
    
    def __len__(self) -> int:
        return self._size

---

10.3 本章小结

双端队列支持两端操作，循环队列高效利用固定空间，滑动窗口算法是重要应用。

---

下一章：第11章 树基础与二叉树