Python 数据结构基础（三）：队列

1. 队列的定义

队列（Queue）是一种先进先出（First In First Out，FIFO）的数据结构。我们把队列中允许插入的一端称为队头，允许删除的一端称为队尾。当队列中没有数据元素时，称为空队列。

队列中的元素离队头越近，代表其在队列中的时间越长，因此队头具有非常重要的意义。最早添加的元素将被最先移除。

2. 队列的基本操作

队列的基本操作有：

入队（enqueue）：将元素添加到队尾。
出队（dequeue）：从队头移除元素。
队头（front）：获取队头元素。
队尾（rear）：获取队尾元素。
队列长度（size）：获取队列中的元素个数。
判断队列是否为空（is_empty）：判断队列是否为空队列。

3. 使用 Python 实现队列

3.1 顺序队列

在 Python 中我们可以借助列表 list 来实现队列的顺序存储结构。这种采用顺序存储结构的队列也被称为顺序队列。

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        """入队操作"""
        self.queue.append(item)

    def dequeue(self):
        """出队操作"""
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("Queue is empty")

    def front(self):
        """获取队头元素"""
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("Queue is empty")

    def rear(self):
        """获取队尾元素"""
        if not self.is_empty():
            return self.queue[-1]
        else:
            raise IndexError("Queue is empty")

    def size(self):
        """获取队列长度"""
        return len(self.queue)

    def is_empty(self):
        """判断队列是否为空"""
        return self.size() == 0

3.2 循环队列

如果队列的长度是固定的，那么当队列满时，再入队就会导致队列溢出。为了解决这个问题，我们可以使用循环队列。

循环队列的基本思想是：将队列的数组首尾相连，形成一个环。当队尾指针到达数组末尾时，将其指向数组的第一个元素，即队头元素。循环队列可以通过取模运算来实现。

入队时，队尾指针 self.rear 循环前进一个位置，也就是 self.rear = (self.rear + 1) % self.size。
出队时，队头指针 self.front 循环前进一个位置，也就是 self.front = (self.front + 1) % self.size。

循环队列在一开始初始化，队列为空时，满足条件 self.front == self.rear。
而队列满时，仍然满足 self.front == self.rear。

class CircularQueue:
    def __init__(self, size):
        self.size = size + 1
        self.queue = [None] * self.size
        self.front = 0
        self.rear = 0
    
    def enqueue(self, item):
        """入队操作"""
        if self.is_full():
            raise IndexError("Queue is full")
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.size
    
    def dequeue(self):
        """出队操作"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.size

    def is_empty(self):
        """判断队列是否为空"""
        return self.front == self.rear

    def is_full(self):
        """判断队列是否已满"""
        return (self.rear + 1) % self.size == self.front

4. 队列的应用场景

队列在实际应用中，有以下几个场景：

任务调度：操作系统中的任务调度器使用队列来管理进程。
缓存：缓存系统使用队列来管理缓存数据。
消息队列：消息队列用于在不同进程或线程之间传递消息。
图算法：图算法中，如广度优先搜索（BFS），使用队列来管理节点。
网络应用：如 HTTP 服务器，使用队列来管理请求。

5. 队列的练习

描述： 写一个 RecentCounter 类来计算特定时间范围内最近的请求。

要求： 请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证： 每次对 ping 的调用都使用比之前更大的 t 值。

示例：

>>> rc = RecentCounter()
>>> rc.ping(1)
1
>>> rc.ping(100)
2
>>> rc.ping(3001)
3
>>> rc.ping(3002)
3

代码：

class RecentCounter:
    def __init__(self):
        self.queue = []
    
    def ping(self, t: int) -> int:
        self.queue.append(t)
        while self.queue[0] < t - 3000:
            self.queue.pop(0)
        return len(self.queue)