小朋友們好，大朋友們好！

我是貓妹，一名愛上Python編程的小學生。

和貓妹學Python，一起趣味學編程。

今日主題

什么是隊列？

隊列有哪些接口(api)？

在Python中如何表示隊列？

什么是隊列

隊列是一個特殊的有序表，其插入操作在表的一端進行，而刪除操作在表的另一端進行，插入的端叫隊尾，刪除的端叫隊首。

隊列有先進先出的特性。

在我們的生活中，有很多都屬于隊列，比如排隊買票，排隊安檢等。

隊列有哪些接口

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

delete()：出隊，從隊列中出來

clear()：清空隊列

isEmpty()：判斷隊列是否為空

isFull()：判斷隊列是否為滿

length()：隊列的當前長度

capability()：隊列的容量，也就是隊列滿時的長度

Python中的雙端隊列deque

在Python中的標準庫collections中，包含了一個模塊：雙端隊列deque。

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

雙端隊列呢？

就是在兩個端口都可以入隊和出隊。

雙端隊列的導(dǎo)入

導(dǎo)入deque:

from collections import deque

雙端隊列的創(chuàng)建

創(chuàng)建空的雙端隊列：

q=deque()

創(chuàng)建一個非空雙端隊列，可以傳入一個可迭代對象：

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)：用函數(shù)len測量雙端隊列q的長度

隊列是否滿

q.maxlen ==?q.popleft()：當前長度等于最大長度，雙端隊列滿

隊列為空

not q：True表示隊列為空，否則非空。

其他接口之count

它可以統(tǒng)計相同元素的個數(shù)

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

翻轉(zhuǎn)順序

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

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

其他接口之rotate

轉(zhuǎn)動，循環(huán)

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全面。

在解決實際問題中，隊列經(jīng)常使用。

這里拋磚引玉，引出幾道編程思考題目，你可以用隊列知識搞定它嗎？

楊輝三角

楊輝三角是中國數(shù)學史上的一個偉大成就，如下圖。

它每層的數(shù)據(jù)都很有規(guī)律，首尾都是1。除第一、二層外，其他層的非邊緣數(shù)據(jù)都來源于上層兩個數(shù)據(jù)的和。

第n層數(shù)據(jù)是怎樣的？

劃分無沖突子集問題

某動物園搬家，要運走N種動物，老虎與獅子放進一個籠子打架，大象與犀牛放一個籠子打架，野豬與獵狗放在一個籠子里打架…設(shè)計算法，使得裝進同一個籠子的動物互相不打架。

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)}#沖突關(guān)系集合

數(shù)字變換

對于一對正整數(shù)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

上述三個應(yīng)用，都可以通過Python用隊列編程來解決問題哦！

貓妹也會持續(xù)更新的，敬請關(guān)注！

好了，我們今天就學到這里吧！

如果遇到什么問題，咱們多多交流，共同解決。

我是貓妹，咱們下次見！