你好,我是悦创。

我们来看一下群友的问题:

那我来分享一下,队列的基本知识。

1. 队列的基本知识

先进先出队列(或简称队列)是一种基于先进先出(FIFO)策略的集合类型.

队列的最简单的例子是我们平时碰到的:

  • 比如排队等待电影;
  • 在杂货店的收营台等待;
  • 在自助餐厅排队等待(这样我们可以弹出托盘栈)。

行为良好的线或队列是有限制的,因为它只有一条路,只有一条出路。不能插队,也不能离开。你只有等待了一定的时间才能到前面。下图展示了一个简单的 Python 对象队列。

队列是有序数据集合,队列的特点,删除数据项是在头部,称为前端(front),增加数据在尾部,称为后端(rear)

2. Queue

# 导入队列
from queue import Queue

# 最多接收3个数据,设置队列长度
q = Queue(3)

# put 向队列中添加数据
q.put(1)
q.put(2)
q.put(3)

# 获取当前队列长度
print(q.qsize())

# 取出最前面的一个数据 1 , 还剩两个
print(q.get())

# 再加入数据
q.put(4)

#超过三个了.如果没有 timeout 参数会处于阻塞状态,卡在那边.若设置 2秒,2秒后会 raise 一个 FULL 的报错
q.put(5, timeout=2))

# 当然,也可以直接给个 block=False,强制设置为不阻塞(默认为会阻塞的),一旦超出队列长度,立即抛出异常
q.put(6, block=False)

# 同样的,当取值(get)的次数大于队列的长度的时候就会产生阻塞,设置超时时间意为最多等待x秒,队列中再没有数据,就抛出异常.也可以使用block参数,跟上面一样

其他常用方法:

empty: 检查队列是否为空,为空返回True,不为空返回False
full : 判断队列是否已经满了

join & task_done :
#举例
from queue import Queue
q = queue.Queue(2)
q.put('a')
q.put('b')
# 程序会一直卡在下面这一行,只要队列中还有值,程序就不会退出
q.join()
-------------------------------------------------------------
q = queue.Queue(2)
q.put('a')
q.put('b')

q.get() 
q.get()
# 插入两个元素之后再取出两个元素,执行后发现,程序还是卡在下面的那个join代码
q.join()
-------------------------------------------------------------
q = queue.Queue(2)
q.put('a')
q.put('b')

q.get()
# get取完队列中的一个值后,使用task_done方法告诉队列,我已经取出了一个值并处理完毕,下同
q.task_done() 
q.get()
#在每次get取值之后,还需要在跟队列声明一下,我已经取出了数据并处理完毕,这样执行到join代码的时候才不会被卡住
q.task_done()
q.join()

3. 双向队列

但是删除列表的第一个元素(抑或是在第一个元素之前添加一个元素)之类的操作是很耗时的,因为这些操作会牵扯
到移动列表里的所有元素。

4. deque

collections.deque 类(双向队列)是一个线程安全、可以快速从两端添加或者删除元素的数据类型。而且如果想要有一种数据类型来存放“最近用到的几个元素”,deque 也是一个很好的选择。这是因为在新建一个双向队列的时候,你可以指定这个队列的大小,如果这个队列满员了,还可以从反向端删除过期的元素,然后在尾端添加新的元素。使用示例如下:

>>> from collections import deque
>>> dq = deque(range(10), maxlen=10) ➊
>>> dq
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.rotate(3) ➋
>>> dq
deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)
>>> dq.rotate(-4)
>>> dq
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)
>>> dq.appendleft(-1) ➌
>>> dq
deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.extend([11, 22, 33]) ➍
>>> dq
deque([3, 4, 5, 6, 7, 8, 9, 11, 22, 33], maxlen=10)
>>> dq.extendleft([10, 20, 30, 40]) ➎
>>> dq
deque([40, 30, 20, 10, 3, 4, 5, 6, 7, 8], maxlen=10)

❶ maxlen 是一个可选参数,代表这个队列可以容纳的元素的数量,而且一旦设定,这个
属性就不能修改了。

❷ 队列的旋转操作接受一个参数 n,当 n > 0 时,队列的最右边的 n 个元素会被移动到
队列的左边。当 n < 0 时,最左边的 n 个元素会被移动到右边。

❸ 当试图对一个已满(len(d) == d.maxlen)的队列做尾部添加操作的时候,它头部
的元素会被删除掉。注意在下一行里,元素 0 被删除了。

❹ 在尾部添加 3 个元素的操作会挤掉 -1、1 和 2。

❺ extendleft(iter) 方法会把迭代器里的元素逐个添加到双向队列的左边,因此迭代
器里的元素会逆序出现在队列里。

5. 其他队列

Python提供的所有队列类型 :

  1. 先进先出队列 queue.Queue
  2. 后进先出队列 queue.LifoQueue (Queue的基础上进行的封装)
  3. 优先级队列 queue.PriorityQueue (Queue的基础上进行的封装)
  4. 双向队列 queue.deque

除了上述提到的队列与双端队列,还有两个用的比较少的:后进先出队列与优先级队列

6. 自己队列实现

在实际编码中不会自己来实现一个队列.因为python本身就有自带的队列库.如果想自己实现可以利用列表的一些特性,比如.append或者.pop来实现.也可以抛开列表重新定义一个队列.这里有一个很好的例子来实现

6.1 数据结构-队列

队列是有序数据集合,队列的特点,删除数据项是在头部,称为前端(front),增加数据在尾部,称为后端(rear)。数据项总是开始排在队伍的后端,慢慢向前走,直到排到最前面,轮到它的时候离开队列。

刚进来的数据排在后端,待在队伍里时间最长的在前端,这种排列规则叫做FIFO(first-in first-out),意思是“先进先出”,或者叫做“先来先服务”(first-come first-served)

队列一般提供以下接口:

  1. Queue() 定义一个空队列,无参数,返回值是空队列
  2. enqueue(item) 在队列尾部加入一个数据项,参数是数据项,无返回值
  3. dequeue() 删除队列头部的数据项,不需要参数,返回值是被删除的数据,队列本身有变化。
  4. isEmpty() 检测队列是否为空。无参数,返回布尔值。
  5. size() 返回队列数据项的数量。无参数,返回一个整数。

用 python 的 list 数据类型能比较容易的实现队列数据模型,但这里不以list来实现。我们假设队列里的元素有一个指针,最先加进元素的指针指向它下一个元素,依次类推,最后一个元素的指针是指向 None。所以队列里的元素可以抽象出一个类来,同样像链表时的 Node 类一样,Node 类里有自己的数据和一个指向 None 的指针。一个 Node 对象如下示意图:

而队列里分为两端,一端叫前端,这一端做数据的删除操作,另一端叫后端,做数据的增加操作。数据只能从后端加入,并只能从前端删除。为了抽象这个Queue类,会创建两个指针,一个head,指向队头的元素,一个tail,指向队尾的元素。如果是一个空的队列,那headtail都指向None

一个空队列示意图:

当队列里有一个元素时,headtail两个指针都指向这个元素,示意图是这样的:

当队列再增加一个元素时,tail指针会移动到新增加的这个元素,前一个元素的next指针也会指向新元素,而head指针不会发生改变,如下图:

不断向队列增加元素时,各个指针移动方式如上。

当是删除元素时,直接把head指针移动到下一个元素,再把值弹出即可。

来看一个最简单队列的代码实现:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dequeue(self):
        if self.head is None:
            raise Exception('This is a empty queue')
        cur = self.head
        self.head = cur.next
        return cur.value

    def is_empty(self):
        return self.head is None

    def size(self):
        cur = self.head
        count = 0
        if cur is None:
            return count
        while cur.next is not None:
            count += 1
            cur = cur.next
        return count + 1


if __name__ == '__main__':
    q = Queue()
    for i in range(5):
        q.enqueue(i)
    for _ in range(5):
        print(q.dequeue())
    print(q.is_empty())
    print(q.size())

在实际编码中不会自己来实现一个队列,而是使用标准库中的queue,通过from queue import Queue来导入Queue类。

AI悦创·创造不同!
AI悦创 » Python中的队列

Leave a Reply