小朋友们好，大朋友们好！

我是猫妹，一名爱上Python编程的小学生。

和猫妹学Python，一起趣味学编程。

今日主题

什么是队列？

队列有哪些接口(api)？

在Python中如何表示队列？

什么是队列

队列是一个特殊的有序表，其插入操作在表的一端进行，而删除操作在表的另一端进行，插入的端叫队尾，删除的端叫队首。

队列有先进先出的特性。

在我们的生活中，有很多都属于队列，比如排队买票，排队安检等。

队列有哪些接口

add(x)：入队，加入队列

delete()：出队，从队列中出来

clear()：清空队列

isEmpty()：判断队列是否为空

isFull()：判断队列是否为满

length()：队列的当前长度

capability()：队列的容量，也就是队列满时的长度

Python中的双端队列deque

在Python中的标准库collections中，包含了一个模块：双端队列deque。

队列是在一端入队，另一端出队。

双端队列呢？

就是在两个端口都可以入队和出队。

双端队列的导入

导入deque:

from collections import deque

双端队列的创建

创建空的双端队列：

q=deque()

创建一个非空双端队列，可以传入一个可迭代对象：

q=deque([1,2,3])

可以指定双端队列的容量。如上不指定容量，表示可以无限入队。

q=deque([1,2,3],10)

入队操作

q.append(4)：右端入队一个元素

q.appendleft(5)：左端入队一个元素

q.extend([a,b,x])：右端入队多个元素，相当于多次q.append

q.extendleft([x,y,z])：左端入队多个元素，相当于多次q.appendleft

出队操作

q.pop()：右端出队

q.popleft()：左端出队

清空队列

q.clear()：清空队列

队列容量

q.maxlen：队列的最大容量。

如果初始化队列时未指定队列最大容量，那么它是None。

队列当前长度

len(q)：用函数len测量双端队列q的长度

队列是否满

q.maxlen == q.popleft()：当前长度等于最大长度，双端队列满

队列为空

not q：True表示队列为空，否则非空。

其他接口之count

它可以统计相同元素的个数

q=deque([1,2,2,3,4,5,6])

print(q.count(2))#2

其他接口之remove

删除指定元素

q=deque([1,2,2,3,4,5,6])

print(q.remove(2))

print(q)#deque([1,2,3,4,5,6)]

其他接口之reverse

翻转顺序

q=deque([1,2,3,4,5,6])

print(q.reverse())#deque([6,5,4,3,2,1)]

其他接口之rotate

转动，循环

q=deque([1,2,3,4,5,6])

print(q.rotate(1))#deque([6,1,2,3,4,5)]

q=deque([1,2,3,4,5,6])

print(q.rotate(2))#deque([5,6,1,2,3,4)]

q=deque([1,2,3,4,5,6])

print(q.rotate(-1))#deque([2,3,4,5,6,1)]

q=deque([1,2,3,4,5,6])

print(q.rotate(-2))#deque([3,4,5,6,1,2)]

几道编程思考题

看得出来，双端队列deque，功能强大，api全面。

在解决实际问题中，队列经常使用。

这里抛砖引玉，引出几道编程思考题目，你可以用队列知识搞定它吗？

杨辉三角

杨辉三角是中国数学史上的一个伟大成就，如下图。

它每层的数据都很有规律，首尾都是1。除第一、二层外，其他层的非边缘数据都来源于上层两个数据的和。

第n层数据是怎样的？

划分无冲突子集问题

某动物园搬家，要运走N种动物，老虎与狮子放进一个笼子打架，大象与犀牛放一个笼子打架，野猪与猎狗放在一个笼子里打架…设计算法，使得装进同一个笼子的动物互相不打架。

A={0,1,2,3,4,5,6,7,8}#代表N种动物的集合，

R={(1,4),(4,8),(1,8),(1,7),(8,3),(1,0),(0,5),(1,5),(3,4),(5,6),(5,2),(6,2),(6,4)}#冲突关系集合

数字变换

对于一对正整数a和b，对a只能进行加1，减1，乘2操作，问最小对a进行几次操作能得到b？

例如：

a=3,b=11，可通过3*2*2-1，3次操作得到11

a=5,b=8，可通过(5-1)*2，2次操作得到8

上述三个应用，都可以通过Python用队列编程来解决问题哦！

猫妹也会持续更新的，敬请关注！

好了，我们今天就学到这里吧！

如果遇到什么问题，咱们多多交流，共同解决。

我是猫妹，咱们下次见！