前面的文章中,我们简单介绍过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在并发环境中支持的线程安全的几种队列的具体实现。
感谢您的拨冗阅读,希望对您有所帮助。