详解Python数据结构之队列 (Queue)

在计算机科学中，队列（Queue）是一种数据结构，可以用于按顺序存储和访问元素。该数据结构遵循先进先出（FIFO）原则，人们可以从队列的前面插入元素，从队列的后面删除元素。Python内置了队列模块（queue），这个模块实现了多线程安全队列、同步机制及相关数据结构。Queue模块提供了三种队列类型：

• FIFO队列 - 先进先出队列
• LIFO队列 - 后进先出队列
• 优先级队列 - 带优先级的队列

1. FIFO队列

FIFO队列即先进先出队列。在这种类型的队列中，最先加入队列的元素总是率先删除。

1.1 创建队列和入队出队操作

在Python中，您可以使用Queue.Queue类创建一个空的FIFO队列。以下代码片段说明了如何创建一个FIFO队列，然后将一些元素添加到队列中并将它们推出。

import queue  # 引入queue模块

# 创建一个FIFO队列
my_queue = queue.Queue()

# 将元素添加到队列中
my_queue.put('hello')
my_queue.put('world')

# 从队列中弹出元素
print(my_queue.get())  # Output: 'hello'
print(my_queue.get())  # Output: 'world'

Python队列提供了以下方法：

• Queue.qsize() 返回队列的大小
• Queue.empty() 如果队列为空，则返回True；否则返回False。
• Queue.full() 如果队列已满，则返回True；否则返回False。
• Queue.put(item) 将item添加到队列中
• Queue.put(item, block=True, timeout=None) 将item添加到队列中，等待指定时间
• Queue.get() 从队列中删除并返回一个项。
• Queue.get(block=True, timeout=None) 从队列中删除并返回一个项，等待指定时间。

1.2 线程安全的FIFO队列

Python队列提供了一种名为queue.Queue的线程安全实现。在多线程应用程序中使用队列通常是安全的，并且可以避免使用锁，条件变量或其他同步机制。

以下代码段说明了如何使用queue.Queue在多线程应用程序中实现线程安全的FIFO队列：

import queue
import threading

def worker(q):
    while True:
        item = q.get()
        if item is None:
            break
        print(item)
        q.task_done()

my_queue = queue.Queue()
num_worker_threads = 4

# 创建并启动线程
threads = []
for i in range(num_worker_threads):
    t = threading.Thread(target=worker, args=(my_queue,))
    t.start()
    threads.append(t)

# 将元素添加到队列中
for item in range(10):
    my_queue.put(item)

# 队列中每个元素处理完成
my_queue.join()

# 关闭线程
for i in range(num_worker_threads):
    my_queue.put(None)
for t in threads:
    t.join()

上述代码启动四个工作线程（4个线程），将10个元素添加到一个FIFO队列中，并将它们全部删除。

2. LIFO队列

LIFO队列即后进先出队列。在这种类型的队列中，最后加入队列的元素总是率先删除。

2.1 创建LIFO队列和入队出队操作

Python队列模块还提供了一种名为LifoQueue的后进先出（LIFO）队列。以下代码片段演示如何使用Queue.LifoQueue创建一个LIFO队列，然后将一些元素添加到队列中并将它们推出。

import queue  # 引入队列模块

# 创建一个LIFO队列
my_lifo_queue = queue.LifoQueue()

# 将元素添加到队列中
my_lifo_queue.put('hello')
my_lifo_queue.put('world')

# 从队列中弹出元素
print(my_lifo_queue.get())  # Output: 'world'
print(my_lifo_queue.get())  # Output: 'hello'

此代码示例创建了一个后进先出队列并添加了两个元素，并使用Queue.get()方法从队列中删除元素从而实现后进先出的效果。

2.2 线程安全的LIFO队列

Queue模块还提供了一种名为queue.LifoQueue的线程安全实现的后进先出（LIFO）队列类型。以下是如何使用queue.LifoQueue在多线程应用程序中实现线程安全的LIFO队列的示例代码片段：

import queue
import threading

def worker(q):
    while True:
        item = q.get()
        if item is None:
            break
        print(item)
        q.task_done()

my_lifo_queue = queue.LifoQueue()
num_worker_threads = 4

# 创建和启动线程
threads = []
for i in range(num_worker_threads):
    t = threading.Thread(target=worker, args=(my_lifo_queue,))
    t.start()
    threads.append(t)

# 将元素添加到队列中
for item in range(10):
    my_lifo_queue.put(item)

# 队列中每个元素处理完成
my_lifo_queue.join()

# 关闭线程
for i in range(num_worker_threads):
    my_lifo_queue.put(None)
for t in threads:
    t.join()

3. 优先级队列

优先级队列是一种独特的队列，具有优先级概念。队列中的每个元素都具有优先级值，并且较高优先级的元素在相同条件下排在队列的前面。

3.1 创建优先级队列和入队出队操作

Python的优先级队列由Queue.PriorityQueue类实现。 在Queue.PriorityQueue内部，元素的优先级是作为元组（值，优先级）中的值提供的，其中优先级值较低的元素优先级较高（在特定值之间）。

import queue

# 创建一个优先级队列
my_priority_queue = queue.PriorityQueue()

# 将元素添加到队列中
my_priority_queue.put((2, "world"))
my_priority_queue.put((1, "hello"))

# 从队列中弹出元素
print(my_priority_queue.get()[1])  # Output: 'hello'
print(my_priority_queue.get()[1])  # Output: 'world'

此示例说明了如何使用queue.PriorityQueue类创建一个优先级队列，并定义了两个元素，然后将它们添加到队列中。然后，使用Queue.get()方法从队列中删除这些元素。在此示例中，由于“hello”元素的优先级低于“world”元素，因此“hello”元素将在“world”元素之前弹出。

3.2 线程安全的优先级队列

Queue模块还提供了一种名为queue.PriorityQueue的线程安全实现的优先级队列类型。 在多线程应用程序中使用此类实现线程安全的优先级队列非常安全。

import queue
import threading

def worker(q):
    while True:
        item = q.get()
        if item is None:
            break
        print(item)
        q.task_done()

my_priority_queue = queue.PriorityQueue()
num_worker_threads = 4

# 创建和启动线程
threads = []
for i in range(num_worker_threads):
    t = threading.Thread(target=worker, args=(my_priority_queue,))
    t.start()
    threads.append(t)

# 向队列添加更重要的任务
my_priority_queue.put((1, "hello"))

# 向队列添加不那么重要的任务
my_priority_queue.put((2, "world"))

# 等待队列中的所有元素都被处理完
my_priority_queue.join()

# 关闭线程
for i in range(num_worker_threads):
    my_priority_queue.put(None)
for t in threads:
    t.join()

此示例说明了如何使用queue.PriorityQueue类创建一个线程安全的优先级队列，并启动一个多线程应用程序。 然后，代码向优先级队列添加两个元素。次优先级的任务被放置在队列的顶部，优先级较低的任务被放置在队列的底部。程序最后等待队列被处理完并结束线程。