數據結構（三）：隊列

隊列：先入先出（FIFO）表。

常用操作：

• Enqueue：入隊，即將數據寫入隊列末尾
• Dequeue：出隊，即將隊列開頭的元素從隊列中刪除並返回

應用場景：

　　隊列通常用來實現消息（任務）的快速讀寫，即消息隊列。消息隊列的常用來解決如下問題：

• 提升系統的吞吐量：通過引入消息隊列，將不是必須的業務邏輯非同步處理，用戶請求寫入消息隊列後即返迴響應，而不必等待全部的業務邏輯完成，提高了cpu利用效率。
• 實現應用解耦：用戶請求通常是由一系列子業務系統配合完成，引入消息隊列，可以避免業務系統間直接的相互調用，從而實現應用解耦，各子系統間相互獨立，降低系統複雜度。
• 流量削峰：類似秒殺的活動中，可以通過消息隊列控制活動人數，消息隊列滿後，直接拋棄用戶請求，緩解短時間內的高流量對伺服器的壓力。
• 消息通訊：利用消息隊列高效的通訊機制，實現點對點通訊或聊天室。
• 日誌處理：日誌採集客戶端將日誌寫入消息隊列，日誌處理伺服器從讀取消息隊列中的日誌，解決大量日誌傳輸問題。

實現方式：

• 鏈表實現：比較簡單，不再贅述
• 數組實現：用數組實現一個隊列，需要考慮元素出隊後，數組位置單元迴圈利用的問題，即隊列的迴圈數組實現

使用迴圈數組實現一個隊列：

 1 from array import array
 2 
 3 class arr_queue(object):
 4     def __init__(self, maxsize):
 5         self._array = array('i', range(maxsize))
 6         self._head = 0
 7         self._tail = 0
 8         self._length = 0
 9         self._maxsize = maxsize
10 
11     def enqueue(self, value):
12         if self._length >= self._maxsize:
13             raise Exception('queue is full')
14         self._array[self._tail] = value
15         self._length += 1
16         self._tail += 1
17         if self._tail >= self._maxsize:
18             self._tail = 0
19 
20     def dequeue(self):
21         if self._length <= 0:
22             raise Exception('queue is empty')
23         value = self._array[self._head]
24         self._length -= 1
25         self._head += 1
26         if self._head >= self._maxsize:
27             self._head = 0
28         return value
29 
30     def __len__(self):
31         return self._length