什么是隊列谭胚？

隊列（queue）懈费，是先進先出（FIFO, First-In-First-Out）的線性表捞蛋。在具體應用中通常用鏈表或者數組來實現。隊列只允許在后端（稱為rear）進行插入操作洋幻，在前端（稱為front）進行刪除操作。

這是維基百科上對隊列的解釋翅娶，隊列和棧一樣文留，也是一種受限的線性表結構好唯。隊列有兩個操作，入隊和出隊燥翅，隊列可以用數組和鏈表來實現骑篙，用數組實現的稱為順序隊列，用鏈表實現的稱為鏈式隊列森书。

入隊和出隊操作

與棧不同的是靶端，隊列中有兩個指針，分別為隊列頭指針 head 和隊列尾指針 tail 凛膏。當 head == tail 時杨名，隊為空；當 tail == n 時猖毫，隊滿台谍，不能再加入新的元素。當元素出隊時吁断， head + 1趁蕊，當元素入隊時，tail + 1仔役。假設用數組實現隊的操作介衔，下面用一段Python代碼描述一下具體過程(自己寫的代碼，可能有不對的地方)骂因。

class Queue(object):

    def __init__ (self,head,tail,arr):
        self.head = head   #傳入的頭指針
        self.tail = tail   #傳入的尾指針
        self.arr = arr    #傳入的隊列
        self.len = len(arr)

    def enqueue (self,element):
        if (self.tail == self.len-1):  #判斷隊列是否滿
            print ("The queue is full!")
            return self.arr,self.head,self.tail
        self.arr[self.tail] = element  #在隊尾插入新的元素
        self.tail += 1#尾指針加 1
        print ("The element entered")
        return self.arr,self.head,self.tail  #返回新的隊列
    def dequeue (self):
        if (self.head == self.tail):  #判斷隊列是否為空
            print ("The queue is empty!")
            return self.arr,self.head,self.tail 
        headData = self.arr[self.head]
        print ("The head data is %d"%(headData))  #輸出隊頭元素
        self.head += 1#頭指針加 1
        return self.arr,self.head,self.tail  #返回新的隊列 

work = Queue(0,1,[1,2,0])
Arrin,Hin,Tin = work.enqueue(5)
for i in range(Tin-Hin):
    print (Arrin[Hin+i])   #打印入隊后新的隊列
#Arrout,Hout,Tout = work.dequeue()
#for j in range(Tout-Hout):
#   print (Arrout[Hout+j])  #打印出隊后新的隊列

仔細看一下炎咖，會發(fā)現。入隊和出隊寒波，head 指針和tail 指針不斷移動的乘盼，當 tail == n 時 ，不管數組有沒有存儲空間俄烁，就不能再有新元素入隊了绸栅。前面學習數組的時候，遇到這種問題页屠，需要用數據搬移來解決粹胯，但是每一次搬移，時間復雜度都是 O(n)辰企，為了降低平均時間復雜度风纠，只有在tail ==n & head !=0 的情況下，才觸發(fā)一次數據搬移牢贸，具體代碼就不寫了竹观，畫張圖看一下就很清晰了。

隊列數據搬移.jpg

循環(huán)隊列

還有一種不需要數據搬移的隊列臭增，叫做循環(huán)隊列懂酱，它將隊列轉變成一種抽象的環(huán)形結構，如圖所示誊抛。

循環(huán)隊列.jpg

class Queue(object):

    def __init__ (self,head,tail,arr):
        self.head = head
        self.tail = tail
        self.arr = arr
        self.len = len(arr)

    def enqueue (self,element):
        if ((self.tail+1)%self.len == self.head):  #判斷隊列是否滿
            print ("The queue is full!")
            return self.arr,self.head,self.tail,self.len
        if (self.tail == self.len-1):
            self.arr[self.tail] = element
            self.tail = 0
        else :
            self.tail += 1
        print ("The element entered")
        return self.arr,self.head,self.tail,self.len
    def dequeue (self):
        if (self.head == self.tail):  #判斷隊列是否為空
            print ("The queue is empty!")
            return self.arr,self.head,self.tail,self.len
        headData = self.arr[self.head]
        print ("The head data is %d"%(headData))
        if (self.head == self.len-1):
            self.head = 0
        else:
            self.head += 1
        return self.arr,self.head,self.tail,self.len 

work = Queue(4,7,[1,2,3,4,5,6,7,8])
#Arrin,Hin,Tin,Lin = work.enqueue(5)
#for i in range(Lin-Hin+Tin):
#    if (Hin+i >=  Lin):
#        print (Arrin[Hin+i-Lin])
#    else:
#        print (Arrin[Hin+i])

Arrout,Hout,Tout,Lout = work.dequeue()
if (Tout < Hout):
    for j in range(Lout-Hout+Tout):
        if (Hout+j >= Lout):
            print (Arrout[Hout+j-Lout])
        else:
            print (Arrout[Hout+j])
else:
    for j in range(Tout-Hout):
        print (Arrout[Hout+j])

阻塞隊列和并發(fā)隊列

阻塞隊列 就是在阻塞的基礎上加入了阻塞操作癌瘾。就是觅丰，當隊為空時，出隊阻塞妨退，當有數據時阻塞才結束妇萄。當隊滿時，入隊阻塞咬荷，當隊列中有空閑位置時阻塞才結束冠句。

這就相當于定義了一個生產者-消費者模型，需要協調生產者和消費者的個數幸乒，來提高數據處理的效率。

例如罕扎，可以配置多個消費者來應對一個生產者聚唐，這樣會涉及到多線程的問題，多線程操作腔召，需要在數據入隊或出隊時加鎖杆查，同一時刻只允許一個存或者取操作。實際上宴咧，基于數組的循環(huán)隊列根灯，利用 CAS 原子操作，可以實現非常高效的并發(fā)隊列掺栅。

小結

隊列是一種先進先出的數據結構烙肺，可以用鏈表和數組實現，針對響應時間比較敏感的系統(tǒng)氧卧，數組更合適桃笙，但要設計好隊列的大小。對于大部分資源有限的場景沙绝，當沒有空閑資源時搏明，基本上都可以通過“隊列”來實現請求排隊。