队列（Queue）是一种常见的数据结构，它遵循先进先出（FIFO - First In First Out）的原则。

队列的基本操作

  • 入队（Enqueue）：在队列的尾部添加一个元素。
  • 出队（Dequeue）：从队列的头部移除一个元素。
  • 查看队首元素（Peek）：获取队列头部的元素，但不移除它。
  • 判断队列是否为空（IsEmpty）：检查队列中是否有元素。

队列的应用场景

  • 广度优先搜索（BFS）：在图的广度优先搜索算法中，队列用于存储待访问的节点。
  • 任务调度：操作系统中的任务调度，例如按照先来先服务的原则处理进程。
  • 消息传递系统：在消息队列中间件中，消息按照发送的先后顺序排队等待接收者处理。

Python中的queue模块

在 Python 中，queue模块提供了同步的队列类，这些队列类可用于在多线程编程中安全地传递数据。以下是queue模块中主要的队列类及其基本用法：

  1. Queue类

Queue类实现了一个基本的先进先出（FIFO）队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>> import queue
>>> q = queue.Queue()
>>> q.put(1)
>>> q.put(2)
>>> q.put(3)
>>> q.empty()
False
>>> q.
q.all_tasks_done   q.full()           q.get_nowait()     q.maxsize          q.not_empty        q.put(             q.qsize()          q.task_done()
q.empty()          q.get(             q.join()           q.mutex            q.not_full         q.put_nowait(      q.queue            q.unfinished_tasks
>>> q.qsize()
3
>>> q.get()
1
>>> q.get()
2
>>> q.get()
3
>>> q.get()

求滑动窗口的中位数：https://leetcode.cn/problems/sliding-window-median/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import heapq

def deleteItem(heap, num):
    idx = heap.index(num)
    last = heap.pop()
    if idx < len(heap):
        heap[idx] = last
        heapq._siftup(heap, idx)
        heapq._siftdown(heap, 0, idx)

def getMiddle(heap, k):
    sortedList = heapq.nsmallest(k, heap)
    idx, left = divmod(k, 2)
    if not left:
        if idx > 0:
            return (sortedList[idx - 1] + sortedList[idx]) / 2
    else:
        return int(sortedList[idx])


class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        middles = []
        heap = []
        for i, num in enumerate(nums):
            if i < k:
                heapq.heappush(heap, num)
            else:
                middles.append(getMiddle(heap, k))
                numOut = nums[i - k]
                deleteItem(heap, numOut)
                heapq.heappush(heap, num)
        middles.append(getMiddle(heap, k))
        return middles