【Python 数据结构 6.队列】

创建一个队列（列表实现）来存储滑动窗口中的元素，初始化头指针 front 记录当前窗口中第一个有效元素的索引，列表长度等于传入的滑动窗口长度，初始化变量 sum 用于累计当前窗口所有元素的总和，避免每次重新计算总和。判断是否当前元素的个数大于滑动窗口的长度，由于题目中要求最后size个值的平均值，所以直接将超过size长度部分元素出队即可（通过递增 front 指针，出队变相移动 front

L_cl

1014人浏览 · 2025-03-04 11:27:28

L_cl · 2025-03-04 11:27:28 发布

目录

一、队列的基本概念

1.队列的概念

2.入队

Ⅰ、入队的概念

Ⅱ、入队的步骤

3.出队

Ⅰ、出队的概念

Ⅱ、出队的步骤

4.获取队首元素

Ⅰ、获取队首元素的概念

Ⅱ、获取队首元素的步骤

二、Python中的队列

1.顺序表实现

2.链表实现

三、队列的实战

1.933. 最近的请求次数

思路与算法

2.LCR 041. 数据流中的移动平均值

思路与算法

三、栈的应用

应用中，界面的打开

等你读懂相遇的意义，有了隔阂别放弃

—— 25.3.4

一、队列的基本概念

1.队列的概念

队列是仅限在表尾进行插入，表头进行删除的线性表，它遵循先进先出(First-In-First-Out，FIFO)的原则。队列就像排队等候的人群一样，最先进入队列的元素将首先被处理或移除。

在计算机科学中，队列通常用于实现排队系统、任务调度、消息传递(消息队列可用于进程间通信)。我们一般可以用顺序表或者链表来实现队列。

2.入队

Ⅰ、入队的概念

队列的插入操作叫做入队，它是将数据元素从队尾进行插入的过程

Ⅱ、入队的步骤

第1步：将元素添加到队列尾部，更新队尾指针（适用于链表）或者索引（适用于顺序表）

第2步：队列大小增加 1

3.出队

Ⅰ、出队的概念

队列的删除操作叫做出队，它是将队首元素进行删除的过程

Ⅱ、出队的步骤

第1步：删除队首元素，更新队首指针（适用于链表）或者索引（适用于顺序表）

第2步：队列的大小减小1

4.获取队首元素

查找只支持获取队首元素

Ⅰ、获取队首元素的概念

返回队首指针（或者指针）指向的元素的值，无论是链表还是顺序表，都可以通过队首指针（或者索引）在O（1）的时间复杂度获取到队首元素

Ⅱ、获取队首元素的步骤

第1步：利用队首指针(或者索引)获取队首元素并返回。由于是查询操作，所以不会改变队列本身的数据

二、Python中的队列

1.顺序表实现

class Queue:
    def __init__(self):
        self.data = []
        # head 和 tail 分别表示队头和队尾的索引，是一个左闭右开的区间
        self.head = 0
        self.tail = 0

    def push(self, val):
        self.data.append(val)
        self.tail += 1

    def pop(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        val = self.data[self.head]
        self.head += 1
        return val

    def  front(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.data[self.head]

    def size(self):
        return self.tail - self.head

    def is_empty(self):
        return self.size() == 0

def test():
    q = Queue()
    q.push(1)
    q.push(2)
    q.push(3)
    q.push(4)

    while not q.is_empty():
        print(f'Front element: {q.front()}')
        print(f'Popped element: {q.pop()}')
        print(f'Size: {q.size()}')

if __name__ == '__main__':
    test()

2.链表实现

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.len = 0

    # 入队
    def push(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.len += 1

    # 出队
    def pop(self):
        if self.head is None:
            return "Queue is empty"
        data = self.head.data
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.len -= 1
        return data

    # 获取队首元素
    def front(self):
        if self.head is None:
            return "Queue is empty"
        return self.head.data

    def size(self):
        return self.len

    def empty(self):
        return self.len == 0

def test():
    q = Queue()
    q.push(1)
    q.push(2)
    q.push(3)
    q.push(4)
    while not q.empty():
        print(f'Front element: {q.front()}')
        print(f'Popped element: {q.pop()}')
        print(f'Size: {q.size()}')

test()

三、队列的实战

1.933. 最近的请求次数

写一个 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 次

思路与算法

第一步：创建一个队列（列表实现），记录请求的时间戳，并初始化头指针front记录当前有效请求的起始位置

第二步：当ping操作被调用时，将 ping 操作传来的时间 t 加入队列尾部

第三步：检查队列头部的时间戳是否在 [t-3000, t]的范围内，当时间 t - 队首元素的 t 大于 3000毫秒时，说明该请求已过期，将头指针 front 向后移动一位（等价于将其从队列中移除）

第四步：计算有效请求数量，当遍历结束时，返回队列剩余元素的长度 - 头指针的索引位置，即调用完ping操作返回的请求数

list.append()：Python 列表的一个方法，用于在列表的末尾添加一个元素。添加后，列表的长度会增加 1

参数名	类型	是否必选	描述
`element`	任意类型	是	要添加到列表末尾的元素。

len()：Python 的内置函数，用于返回对象的长度（或元素个数），可以用于字符串、列表、元组、字典、集合等可迭代对象

参数名	类型	是否必选	描述
`object`	可迭代对象	是	需要计算长度的对象，例如列表、字符串等。

class RecentCounter:

    def __init__(self):
        self.Queue = []
        self.front = 0

    def ping(self, t: int) -> int:
        self.Queue.append(t)
        while t - self.Queue[self.front] > 3000:
            # 超过3000毫秒范围的请求，直接减去
            self.front += 1
        return len(self.Queue) - self.front
        


# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

2.LCR 041. 数据流中的移动平均值

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

实现 MovingAverage 类：

MovingAverage(int size) 用窗口大小 size 初始化对象。

double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。

示例：
输入：
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3
提示：

1 <= size <= 1000

-105 <= val <= 105

最多调用 next 方法 104 次

思路与算法

第一步：创建一个队列（列表实现）来存储滑动窗口中的元素，初始化头指针 front 记录当前窗口中第一个有效元素的索引，列表长度等于传入的滑动窗口长度，初始化变量 sum 用于累计当前窗口所有元素的总和，避免每次重新计算总和

第二步：创建一个函数getSize，获取队列当前的元素个数，将出队操作等价于移动头指针位置

第三步：定义成员函数 next，每次调用 next 函数时，传入一个整数，将这个整数添加到队列尾部，然后变量 sum 值加和这个整数

第四步：判断是否当前元素的个数大于滑动窗口的长度，由于题目中要求最后size个值的平均值，所以直接将超过size长度部分元素出队即可（通过递增 front 指针，出队变相移动 front 指针的位置即可）

第五步：返回窗口内元素的平均值，即 self.sum / self.getSize()

list.append()：Python 列表的一个方法，用于在列表的末尾添加一个元素。添加后，列表的长度会增加 1

参数名	类型	是否必选	描述
`element`	任意类型	是	要添加到列表末尾的元素。

len()：Python 的内置函数，用于返回对象的长度（或元素个数），可以用于字符串、列表、元组、字典、集合等可迭代对象

参数名	类型	是否必选	描述
`object`	可迭代对象	是	需要计算长度的对象，例如列表、字符串等。

class MovingAverage:

    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self.queue = []
        self.front = 0
        self.len = size
        self.sum = 0

    # 当前队列的元素个数   
    def getSize(self):
        # 当前队列的大小 - 头指针所在的位置
        return len(self.queue) - self.front


    def next(self, val: int) -> float:
        self.queue.append(val)
        self.sum += val
        # 判断是否当前元素的个数 大于 滑动窗口的长度，由于题目中要求最后size个值的平均值，所以直接将超过size长度部分元素出队即可
        while self.getSize() > self.len:
            self.sum -= self.queue[self.front]
            self.front += 1
        # 经过循环后，队列里的元素个数恰好等于滑动窗口的长度，直接返回滑动窗口内的元素 / 滑动窗口内的元素个数即可
        return self.sum / self.getSize()




# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)