快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)與算法中的隊(duì)列詳解(1)

更新時(shí)間：2022年03月09日 16:50:43 作者：姜學(xué)遷

這篇文章主要為大家詳細(xì)介紹了Python的隊(duì)列，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助

什么是隊(duì)列？

隊(duì)列，與棧類似，是有序集合。添加操作發(fā)生在 “尾部”，移除操作只發(fā)生在 “頭部”。新元素只從尾部進(jìn)入隊(duì)列，然后一直向前移動到頭部，直到成為下一個(gè)被移除的元素。?

最新添加的元素必須在隊(duì)列的尾部等待，在隊(duì)列中時(shí)間最長的元素則排在最前面。這種排序原則被稱作FIFO（first-in first-out），即先進(jìn)先出，也稱先到先得。在日常生活中，我們經(jīng)常排隊(duì)，這便是最簡單的隊(duì)列例子。進(jìn)電影院要排隊(duì)，在超市結(jié)賬要排隊(duì)，買咖啡也要排隊(duì)。好的隊(duì)列只允許一頭進(jìn)，另一頭出，不可能發(fā)生插隊(duì)或者中途離開的情況。?

構(gòu)建一個(gè)隊(duì)列

如前所述，隊(duì)列是元素的有序集合，添加操作發(fā)生在其尾部，移除操作則發(fā)生在頭部。隊(duì)列的操作順序是 FIFO，它支持以下操作。

創(chuàng)建一個(gè)空隊(duì)列。它不需要參數(shù)，且會返回一個(gè)空隊(duì)列。Queue()
在隊(duì)列的尾部添加一個(gè)元素。它需要一個(gè)元素作為參數(shù)，不返回任何值。enqueue(item)
從隊(duì)列的頭部移除一個(gè)元素。它不需要參數(shù)，且會返回一個(gè)元素，并修改隊(duì)列的內(nèi)容。 dequeue()
檢查隊(duì)列是否為空。它不需要參數(shù)，且會返回一個(gè)布爾值。isEmpty()
返回隊(duì)列中元素的數(shù)目。它不需要參數(shù)，且會返回一個(gè)整數(shù)。 size()?

與構(gòu)建棧一樣，我們利用簡潔強(qiáng)大的列表來實(shí)現(xiàn)隊(duì)列。?

需要確定列表的哪一端是隊(duì)列的尾部，哪一端是頭部。我們假設(shè)隊(duì)列的尾部在列表的位置0處。如此一來，便可以使用 insert 函數(shù)向隊(duì)列的尾部添加新元素。pop 則可用于移除隊(duì)列頭部的元素（列表中的最后一個(gè)元素）。這意味著添加操作的時(shí)間復(fù)雜度是O(n)，移除操作則是O(1)。?

隊(duì)列實(shí)現(xiàn)代碼如下：

class Queue:
    def __init__(self):
        self.items = []            # 構(gòu)建空隊(duì)列
        print("你創(chuàng)建了一個(gè)隊(duì)列")
    def isEmpty(self):
        return self.items ==[]     # 判斷是否為空
    def enqueue(self,item):
        self.items.insert(0, item) # 在隊(duì)列尾部(列表左端)插入元素
        print("你在隊(duì)列尾部插入了一個(gè)%s" % item)
    def dequeue(self):
        print("你在隊(duì)列頭部移除了一個(gè)元素")
        return self.items.pop()    # 在隊(duì)列頭部(列表右端)移出元素
    def size(self):
        return len(self.items)     # 隊(duì)列(列表)長度
    def look(self):
        print(self.items)

下圖展示了隊(duì)列的操作及其返回結(jié)果：

在這里插入圖片描述