108、Python并发编程:一文搞懂队列及Python中的线程安全队列

南宫理的日志录 2024-12-02 13:04:48
引言

前面的文章中,我们简单介绍过Python中通过Queue对象,实现生产者消费者的业务场景。但是,队列不止有Queue这一种,根据不同的排队调度算法,队列有不同的实现,比如先进先出、后进先出、带优先级的队列等。本文就来对队列的算法以及实现,作进一步的扩展介绍。

本文的主要内容有:

1、队列的详细介绍

2、队列的类型及使用场景

3、Python中主要的队列实现

队列的详细介绍

如果有科班出身的同学,一定曾经被本科的一门核心基础课程——《数据结构和算法》折磨过。读书期间,为了考试,也许只是死记硬背知识点了,不晓得实际上有什么用。但是,有了一定的工作实践之后,再回看哪些基础课程,一定会有更加深刻的体会。

队列的概念及设计理念

队列(Queue)是一种非常重要的数据结构,它提供一种先进先出(FIFO)的数据处理方式。队列再许多计算机科学和实际应用中都发挥着至关重要的作用。

队列的设计理念主要有:

1、先进先出(FIFO):队列遵循先进先出的原则,最先进入队列的元素最先被处理。这一特性,使得队列非常适合用于处理顺序操作。

2、状态管理:队列可以用于管理任务和状态,尤其是处理多个任务时,可以确保任务按照特定的顺序得到执行。

3、资源共享:在多线程或者分布式系统中,队列可以作为资源共享的载体,协调多个生产者和消费者之间的工作。

队列的基础操作

队列这种数据结构提供的基本操作主要有:

1、入队(Enqueue):将一个元素添加到队列的末尾。

2、出队(Dequeue):将队列的头部元素移除并返回该元素。

3、查看队头(Front/Peek):返回队列的头部元素,但不移除。

4、检查队列是否为空(IsEmpty):判断队列是否为空。

5、查看队列的大小(Size):返回队列中的元素的数量,同时通过该方法,可以间接实现判断队列是否满的功能。

队列的类型及使用场景

基于队列的核心设计理念,结合不同的算法,可以有不同的队列实现,其实,队列的实现更多的是对操作位置的不同限制,以及底层的存储结构存在差异。

队列的类型主要有:

1、基本队列

一般通过数组或者链表实现最基本的FIFO的队列结构。用于实现通常的任务排队、打印作业排队、消息的有序传递等。

2、双端队列

支持在队列的两端进行插入和删除操作的队列。通常用于支持需要两端操作的场景,比如回溯算法和滑动窗口的场景。这种队列,可以看做是队列和栈的结合体。用户在使用中,可以自行限制插入和删除的端,从而将双端队列演变为栈、FIFO队列、LIFO队列等。

3、优先队列

每个元素有一个优先级,出队操作根据优先级而不是根据插入顺序进行。常用于任务调度、图算法、事件驱动等。

4、循环队列

在一个固定大小的数组上实现的队列,避免了空间浪费。可以用于实现资源池、循环缓冲队列、缓存管理等。

5、阻塞队列

在多线程环境中使用的队列,消费者在队列为空时等待,生产者在队列满时等待。阻塞特性,避免了轮询所造成的CPU资源浪费及编码的复杂性。

队列根据具体的实现,有着不同的应用场景:

1、任务调度:在操作系统中,任务调度使用队列来管理待执行的任务,确保任务的有序调度执行。

2、事件驱动程序:在GUI程序中,用户的点击事件等,会被放入到队列中,按照顺序处理。

3、网络请求:在web服务器中,使用队列来管理来自不同客户端的访问请求,确保请求的有序处理。

4、缓冲区:在数据流处理中,队列可以作为缓冲区,用于平衡生产者和消费者之间的工作速率。

5、消息传递系统:在分布式系统中,可以通过消息队列来实现不同服务间的解耦、数据的复用等。典型的队列有RabbitMQ、Kafka等。

Python中主要的队列实现

Python中的collections模块,提供了deque组件,这是一个双端队列,支持两端进行插入和删除操作。但是,由于是非线程安全的,所以在非并发场景中使用比较多,这里就不展开介绍了。

Python中的queue模块,提供了多种线程安全的队列实现,前面已经介绍过的Queue就是其中的一种,具有阻塞特性的线程安全的队列。

下面对queue模块中的线程安全队列进行分别介绍:

1、Queue

Queue是一个标准的FIFO(First In First Out)队列,提供先进先出的逻辑支持。可以用于多线程的环境中,提供put()和get()方法,分别用于入队和出队操作。同时支持阻塞和非阻塞的操作模式。

通常可以用于生产者消费者模式中。

由于前面已经介绍过,这里就不再通过代码展开说明了。

2、LifoQueue

LifoQueue是一个支持后进先出操作的多线程安全的队列,类似于栈。

与Queue一样,同样通过put()和get()方法进行元素的入队和出队操作。

通常可以应用于最新任务需要最先处理的场合,比如某些回溯型的算法实现等。

通过具体代码演示一下LifoQueue的使用:

执行结果:

3、PriorityQueue

PriorityQueue是一个带优先级的队列,支持根据优先级进行出队操作。

队列中,每一个元素必须是一个可比较的对象,通常可以是元组(优先级,数据)的形式来表示。

当使用get()方法进行出队操作时,返回的是当前队列中优先级最高的元素。

通常可以用于带优先级的任务调度系统、图算法等的实现。

需要注意的是,优先级数字越小,表示优先级越搞。

下面,通过代码演示一个基于PriorityQueue实现的任务调度的场景模拟:

执行结果:

总结

本文简单介绍了计算机科学中非常核心的数据结构——队列,主要涉及到队列的设计理念和常用操作,以及队列的不同类型及适用场景。最后,介绍了Python在并发环境中支持的线程安全的几种队列的具体实现。

感谢您的拨冗阅读,希望对您有所帮助。

0 阅读:13

南宫理的日志录

简介:深耕IT科技,探索技术与人文的交集