队列（Queue）是一种常见的数据结构，它遵循先进先出（FIFO - First In First Out）的原则。
队列的基本操作
- 入队（Enqueue）：在队列的尾部添加一个元素。
- 出队（Dequeue）：从队列的头部移除一个元素。
- 查看队首元素（Peek）：获取队列头部的元素，但不移除它。
- 判断队列是否为空（IsEmpty）：检查队列中是否有元素。
队列的应用场景
- 广度优先搜索（BFS）：在图的广度优先搜索算法中，队列用于存储待访问的节点。
- 任务调度：操作系统中的任务调度，例如按照先来先服务的原则处理进程。
- 消息传递系统：在消息队列中间件中，消息按照发送的先后顺序排队等待接收者处理。
Python中的queue模块
在 Python 中，queue模块提供了同步的队列类，这些队列类可用于在多线程编程中安全地传递数据。以下是queue模块中主要的队列类及其基本用法：
- Queue类
Queue类实现了一个基本的先进先出（FIFO）队列。
代码语言：javascript复制>>> 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/
代码语言：javascript复制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
