Python数据结构-队列与广度优先搜索（Queue）

队列（Queue） ：简称为队，一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。

成都创新互联公司 - 西信服务器托管，四川服务器租用，成都服务器租用，四川网通托管,绵阳服务器托管，德阳服务器托管，遂宁服务器托管，绵阳服务器托管，四川云主机，成都云主机，西南云主机，西信服务器托管，西南服务器托管，四川/成都大带宽，机柜大带宽，四川老牌ＩＤＣ服务商

我们把队列中允许插入的一端称为 「队尾（rear）」 ；把允许删除的另一端称为 「队头（front）」 。当表中没有任何数据元素时，称之为 「空队」 。

广度优先搜索算法（Breadth First Search） ：简称为 BFS，又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着树的宽度遍历树或图的节点。如果所有节点均被访问，则算法中止。

广度优先遍历 类似于树的层次遍历过程 。呈现出一层一层向外扩张的特点。先看到的节点先访问，后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点，所以广度优先搜索可以通过「队列」来实现。

力扣933

游戏时，队首始终是持有土豆的人

模拟游戏开始，队首的人出队，之后再到队尾（类似于循环队列）

传递了num次之后，将队首的人移除

如此反复，直到队列中剩余一人

多人共用一台打印机，采取“先到先服务”的队列策略来执行打印任务

需要解决的问题：1 打印系统的容量是多少？2 在能够接受的等待时间内，系统可容纳多少用户以多高的频率提交打印任务？

输入：abba

输出：False

思路：1 先将需要判定的词从队尾加入 deque; 2从两端同时移除字符并判断是否相同，直到deque中剩余0个（偶数）或1个字符（奇数）

内容参考：

python_队列

1.队列是先进先出，列表可以读取某个指定数据

2.队列如果将储存的数据都读完就结束，列表可以反复读取

例如：

二、具体介绍一下queue

在使用queue的时候要先引入queue模块，创建对象~

其中queue可以创建出三种对象分别是

1.先进先出行Queue（maxsize = ？）

通过上面的例子我们能发现，put 方法是往队列放数据，但是队列跟列表不同取完之后数据就没有了，如果取的数据大于列表存放的数据就会卡住这时候有两种解决办法，第一种调用get_nowait（）方法，这时候就会报异常queue.Empty，第二种就是从get自身解决，get(block = False),默认的时候block是True。

2.后进先出LifeQueue()是个缩写是Last in first out

3.priorityQueue可以理解成vip，看你的心情让那先出就先出

三、利用queue和多线程写一个生产者消费者

python如何定义和调用函数

1、函数定义

①使用def关键字定义函数

②

def 函数名(参数1.参数2.参数3...):

"""文档字符串，docstring，用来说明函数的作用"""

#函数体

return 表达式

注释的作用：说明函数是做什么的，函数有什么功能。

③遇到冒号要缩进，冒号后面所有的缩进的代码块构成了函数体，描述了函数是做什么的，即函数的功能是什么。Python函数的本质与数学中的函数的本质是一致的。

2、函数调用

①函数必须先定义，才能调用，否则会报错。

②无参数时函数的调用：函数名()，有参数时函数的调用：函数名(参数1.参数2.……)

③不要在定义函数的时候在函数体里面调用本身，否则会出不来，陷入循环调用。

④函数需要调用函数体才会被执行，单纯的只是定义函数是不会被执行的。

⑤Debug工具中Step into进入到调用的函数里，Step Into My Code进入到调用的模块里函数。

Python Queue 入门

Queue 叫队列，是数据结构中的一种，基本上所有成熟的编程语言都内置了对 Queue 的支持。

Python 中的 Queue 模块实现了多生产者和多消费者模型，当需要在多线程编程中非常实用。而且该模块中的 Queue 类实现了锁原语，不需要再考虑多线程安全问题。

该模块内置了三种类型的 Queue，分别是 class queue.Queue(maxsize=0) ， class queue.LifoQueue(maxsize=0) 和 class queue.PriorityQueue(maxsize=0) 。它们三个的区别仅仅是取出时的顺序不一致而已。

Queue 是一个 FIFO 队列，任务按照添加的顺序被取出。

LifoQueue 是一个 LIFO 队列，类似堆栈，后添加的任务先被取出。

PriorityQueue 是一个优先级队列，队列里面的任务按照优先级排序，优先级高的先被取出。

如你所见，就是上面所说的三种不同类型的内置队列，其中 maxsize 是个整数，用于设置可以放入队列中的任务数的上限。当达到这个大小的时候，插入操作将阻塞至队列中的任务被消费掉。如果 maxsize 小于等于零，则队列尺寸为无限大。

向队列中添加任务，直接调用 put() 函数即可

put() 函数完整的函数签名如下 Queue.put(item, block=True, timeout=None) ，如你所见，该函数有两个可选参数。

默认情况下，在队列满时，该函数会一直阻塞，直到队列中有空余的位置可以添加任务为止。如果 timeout 是正数，则最多阻塞 timeout 秒，如果这段时间内还没有空余的位置出来，则会引发 Full 异常。

当 block 为 false 时，timeout 参数将失效。同时如果队列中没有空余的位置可添加任务则会引发 Full 异常，否则会直接把任务放入队列并返回，不会阻塞。

另外，还可以通过 Queue.put_nowait(item) 来添加任务，相当于 Queue.put(item, False) ，不再赘述。同样，在队列满时，该操作会引发 Full 异常。

从队列中获取任务，直接调用 get() 函数即可。

与 put() 函数一样， get() 函数也有两个可选参数，完整签名如下 Queue.get(block=True, timeout=None) 。

默认情况下，当队列空时调用该函数会一直阻塞，直到队列中有任务可获取为止。如果 timeout 是正数，则最多阻塞 timeout 秒，如果这段时间内还没有任务可获取，则会引发 Empty 异常。

当 block 为 false 时，timeout 参数将失效。同时如果队列中没有任务可获取则会立刻引发 Empty 异常，否则会直接获取一个任务并返回，不会阻塞。

另外，还可以通过 Queue.get_nowait() 来获取任务，相当于 Queue.get(False) ，不再赘述。同样，在队列为空时，该操作会引发 Empty 异常。

Queue.qsize() 函数返回队列的大小。注意这个大小不是精确的，qsize() 0 不保证后续的 get() 不被阻塞，同样 qsize() maxsize 也不保证 put() 不被阻塞。

如果队列为空，返回 True ，否则返回 False 。如果 empty() 返回 True ，不保证后续调用的 put() 不被阻塞。类似的，如果 empty() 返回 False ，也不保证后续调用的 get() 不被阻塞。

如果队列是满的返回 True ，否则返回 False 。如果 full() 返回 True 不保证后续调用的 get() 不被阻塞。类似的，如果 full() 返回 False 也不保证后续调用的 put() 不被阻塞。

queue.Queue() 是 FIFO 队列，出队顺序跟入队顺序是一致的。

queue.LifoQueue() 是 LIFO 队列，出队顺序跟入队顺序是完全相反的，类似于栈。

优先级队列中的任务顺序跟放入时的顺序是无关的，而是按照任务的大小来排序，最小值先被取出。那任务比较大小的规则是怎么样的呢。

注意，因为列表的比较对规则是按照下标顺序来比较的，所以在没有比较出大小之前 ，队列中所有列表对应下标位置的元素类型要一致。

好比 [2,1] 和 ["1","b"] 因为第一个位置的元素类型不一样，所以是没有办法比较大小的，所以也就放入不了优先级队列。

然而对于 [2,1] 和 [1,"b"] 来说即使第二个元素的类型不一致也是可以放入优先级队列的，因为只需要比较第一个位置元素的大小就可以比较出结果了，就不需要比较第二个位置元素的大小了。

但是对于 [2,1] 和 1 [2,"b"] 来说，则同样不可以放入优先级队列，因为需要比较第二个位置的元素才可以比较出结果，然而第二个位置的元素类型是不一致的，无法比较大小。

综上，也就是说， 直到在比较出结果之前，对应下标位置的元素类型都是需要一致的 。

下面我们自定义一个动物类型，希望按照年龄大小来做优先级排序。年龄越小优先级越高。

本章节介绍了队列以及其常用操作。因为队列默认实现了锁原语，因此在多线程编程中就不需要再考虑多线程安全问题了，对于程序员来说相当友好了。

分享名称：python队列函数定义 python队列和列表区别
网页路径：http://scyanting.com/article/doeojec.html