隊列（queue）
隊列是先進先出（FIFO, First-In-First-Out）的線性表，在具體應用中通常用鏈表或者數組來實現，隊列只允許在后端（稱為rear）進行插入操作，在前端（稱為front）進行刪除操作，隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加（摘錄維基百科）。
如圖所示
隊列的接口
一個隊列至少需要如下接口：
| 接口 | 描述 |
|---|---|
| add(x) | 入隊 |
| delete() | 出隊 |
| clear() | 清空隊列 |
| isEmpty() | 判斷隊列是否為空 |
| isFull() | 判斷隊列是否未滿 |
| length() | 隊列的當前長度 |
| capability() | 隊列的容量 |
然而在Python中，可以使用collections模塊下的deque函數，deque函數提供了隊列所有的接口，那么先讓我門看看隊列deque函數提供了那些API把：
collections.deque是雙端隊列，即左右兩邊都是可進可出的
| 方法 | 描述 |
|---|---|
| append(x) | 在隊列的右邊添加一個元素 |
| appendleft(x) | 在隊列的左邊添加一個元素 |
| clear() | 從隊列中刪除所有元素 |
| copy() | 返回一個淺拷貝的副本 |
| count(value) | 返回值在隊列中出現的次數 |
| extend([x..]) | 使用可迭代的元素擴展隊列的右側 |
| extendleft([x..]) | 使用可迭代的元素擴展隊列的右側 |
| index(value, [start, [stop]]) | 返回值的第一個索引，如果值不存在，則引發ValueError。 |
| insert(index, object) | 在索引之前插入對象 |
| maxlen | 獲取隊列的最大長度 |
| pop() | 刪除并返回最右側的元素 |
| popleft() | 刪除并返回最左側的元素 |
| remove(value) | 刪除查找到的第一個值 |
| reverse() | 隊列中的所有元素進行翻轉 |
| rotate() | 向右旋轉隊列n步（默認n = 1），如果n為負，向左旋轉。 |
現在我們在Python中測試下這些個API的使用吧。
入隊操作
>>> from collections import deque# 創建一個隊列>>> q = deque([1])>>> qdeque([1])# 往隊列中添加一個元素>>> q.append(2)>>> qdeque([1, 2])# 往隊列最左邊添加一個元素>>> q.appendleft(3)>>> qdeque([3, 1, 2])# 同時入隊多個元素>>> q.extend([4,5,6])>>> qdeque([3, 1, 2, 4, 5, 6])# 在最左邊同時入隊多個元素>>> q.extendleft([7,8,9])>>> qdeque([9, 8, 7, 3, 1, 2, 4, 5, 6])
出隊操作
# 刪除隊列中最后一個>>> q.pop()6>>> qdeque([9, 8, 7, 3, 1, 2, 4, 5])# 刪除隊列中最左邊的一個元素>>> q.popleft()9>>> qdeque([8, 7, 3, 1, 2, 4, 5])
其他的API
# 清空隊列>>> qdeque([8, 7, 3, 1, 2, 4, 5])>>> q.clear()>>> qdeque([])# 判斷隊列是否為空>>> not qTrue# 獲取隊列最大長度>>> q = deque([1,2], 10)>>> q.maxlen10# 查看某個元素出現的次數>>> q.extend([1,2,1,1])>>> q.count(1)4# 查看當前隊列長度>>> len(q)6# 判斷隊列是否滿了>>> q.maxlen == len(q)False# 隊列元素反轉>>> q = deque([1,2,3,4,5],5)>>> q.reverse()>>> qdeque([5, 4, 3, 2, 1], maxlen=5)# 查看元素對應的索引>>> q.index(1)4# 刪除匹配到的第一個元素>>> qdeque([5, 4, 3, 2, 1], maxlen=5)>>> q.remove(5)>>> qdeque([4, 3, 2, 1], maxlen=5)# 元素位置進行旋轉>>> qdeque([4, 3, 2, 1], maxlen=5)>>> q.rotate(2)>>> qdeque([2, 1, 4, 3], maxlen=5)>>> q.rotate(1)>>> qdeque([3, 2, 1, 4], maxlen=5)# 使用負數>>> q.rotate(-1)>>> qdeque([2, 1, 4, 3], maxlen=5)
實例
二項式系數
題目
編寫程序，求二項式系數表中(楊輝三角)第K層系列數
1 1 1 1 2 11 3 3 1......
思路
解決代碼
#!/use/bin/env python# _*_ coding:utf-8 _*_from collections import dequedef yanghui(k): """ :param k: 楊輝三角中第幾層 :return: 第K層的系數 """ q = deque([1]) # 創建一個隊列，默認從1開始 for i in range(k): # 迭代要查找的層數 for _ in range(i): # 循環需要出隊多少次 q.append(q.popleft() + q[0]) # 第一個數加上隊列中第二個數并賦值到隊列末尾 q.append(1) # 每次查找結束后都需要在隊列最右邊添加個1 return list(q)result = yanghui(3)print(result)
劃分無沖突子集
題目
某動物園搬家，要運走N種動物，老虎與獅子放在一起會大家，大象與犀牛放在一個籠子會打架，野豬和野狗放在一個籠子里會打架，現在需要我們設計一個算法，使得裝進同一個籠子的動物互相不打架。
思路
解決代碼
#!/use/bin/env python# _*_ coding:utf-8 _*_from collections import dequedef division(m, n): """ :param m: 沖突關系矩陣 :param n: 幾種動物 :return: 返回一個棧，棧內包含了所有的籠子 """ res = [] # 創建一個棧 q = deque(range(n)) # 初始化隊列，里面放著動物的序號 pre = n # 前一個動物的下標 while q: cur = q.popleft() # 從隊頭出隊一個動物 if pre >= cur: # 是否需要創建籠子 res.append([]) # 創建一個籠子 # 當前的動物是否與籠子內的動物有沖突 for a in res[-1]: # 迭代棧中最頂層的籠子 if m[cur][a]: # 有沖突 q.append(cur) # 重新放入隊列的尾部 break else: # 當前動物和當前籠子中的所有動物沒沖突 res[-1].append(cur) # 當前動物放入最上面的籠子中 pre = cur # 當前變成之前的 return resN = 9R = { # 沖突對應關系表 (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),}M = [[0] * N for _ in range(N)] # 沖洗關系矩陣M，0代表不沖突for i, j in R: M[i][j] = M[j][i] = 1 # 1代表沖突result = division(M, N)print(result)數字變換
題目
對于一對正整數a,b,對a只能進行加1，減1，乘2操作，問最少對a進行幾次操作能得到b？
例如：
思路
本題用廣度優先搜索，尋找a到b狀態遷移最短路徑，對于每個狀態s，可以轉換到撞到s+1,s-1,s*2:
解決代碼
#!/use/bin/env python# _*_ coding:utf-8 _*_from collections import dequedef atob(a, b): """ :param a: 開始的數字 :param b: 最終轉換之后的數字 :return: 最小匹配的次數 """ q = deque([(a, 0)]) # a=當前數字，0=操作的次數 checked = {a} # 已經檢查過的數據 while True: s, c = q.popleft() if s == b: break if s < b: # 要計算的數小于計算之后的數字 if s + 1 not in checked: # 如果要計算的數字+1不在已檢查過的數據集合中 q.append((s + 1, c + 1)) # 要計算的數+1，轉換次數+1 checked.add(s + 1) # 把計算過的數添加到checked集合中 if s * 2 not in checked: q.append((s * 2, c + 1)) checked.add(s * 2) if s > 0: # 要計算的數大于0 if s - 1 not in checked: q.append((s - 1, c + 1)) checked.add(s - 1) return q.popleft()[-1]result = atob(3, 11)print(result)總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。
新聞熱點
疑難解答
圖片精選
