主要學習內容1隊列的概念和性質隊列的順序實現23隊列的鏈式實現4隊列的應用6優先隊列5雙端隊列主要學習內容Python中的各種隊列結構78棧和隊列綜合應用隊列的概念和性質Aqueueisalistinwhichalladditionstothelistaremadeatoneend,andalldeletionsfromthelistaremadeattheotherend.Queuesarealsocalledfirst-in,first-outlists（先進先出表）,orFIFOforshort.Methodsappend（入隊）serve（出隊）empty(判空)retrieve(取隊首元素) len（求長度）init（構造方法）隊列的定義（Specification）frontrearAqueueisadatastructuremodeledafteralineofpeoplewaitingtobeserved.Alongwithstacks,queuesareoneofthesimplestkindsofdatastructures.Applicationswithinacomputersystem

therearequeuesoftaskswaitingfortheprinter,foraccesstodiskstorage,foruseoftheCPU.隊列隊列（queue）也是一種特殊的線性表。從邏輯結構角度看，隊列與普通線性表和棧沒有不同。將隊列定義為n（n≥0）個數據元素構成的有限序列。當n=0時，稱為空隊列。隊列非空時，可記為Q=(a0,a1,a2,…,ai,…,an-1)，其中每個元素有一個固定的位序號。隊列概念及性質隊列的特殊性是被限制在線性表的一端進行插入，另一端進行刪除，允許插入的一端稱為隊尾，允許刪除的一端稱為隊首或隊頭。插入操作稱為入隊或進隊，刪除操作稱為出隊或退隊。隊列概念及性質隊列的特點是最先入隊的元素最先出隊，即具有“先進先出”（FirstInFirstOut，簡稱FIFO）的特性，因此隊列也被稱為先進先出表。一隊人在游樂場門口等待檢票進入游樂場，最先來的人排在隊頭最先進入游樂場，而最后來的人排在隊尾最后進入游樂場。商店、食堂、影院等服務場所也都按照隊列先進先出的原則處理客戶請求。隊列性質及應用隊列廣泛應用于計算機系統的資源分配、數據緩沖和任務調度等場景中。比如，局域網用戶申請使用網絡打印機，多臺終端訪問Web服務器，鍵盤輸入緩沖，操作系統的作業調度等都基于隊列結構。在程序設計中，隊列也經常用于保存動態生成的多個任務或數據，以確保相應任務或數據按照先進先出的次序進行處理。隊列應用場合T類型元素構成的隊列是由T類型元素構成的有限序列，并且具有以下基本操作：（1）構造一個空隊列(init)（2）判斷一個隊列是否為空隊列(empty)（3）求隊列的長度(len)（4）入隊一個元素(append)（5）讀取隊首元素并出隊(serve)（6）讀取隊首元素(retrieve)隊列的抽象數據類型ADTPython有沒有內置的隊列類？Python標準庫queue模塊中，提供了FIFO隊列類Queue，SimpleQueue等Queue的存儲方法？雙向塊鏈結構，用雙端隊列deque實現問題

順序存儲鏈式存儲隊列的存儲隊列的順序存儲某同學方案采用Python的list容納Queue的數據元素將list首端作為隊列尾部list末端作為隊列首端append操作時間復雜度為O(n)serve操作時間復雜度為O(1)首尾倒過來的實現方案不夠合理物理模型法線性順序隊列循環隊列隊列的順序實現一、物理模型表示法入隊操作O(1)出隊操作O(n)物理模型表示法使用初始容量為capacity的Python列表entry依次存儲從隊首到隊尾的所有元素；設整型下標front和rear分別指示隊列的隊首位置和隊尾位置；二、線性順序隊列入隊元素a0、a1、a2出隊a0、a1線性順序隊列線性順序隊列實現隊空條件隊滿條件？入隊a3、a4、a5隊尾指示rear已到達數組尾部，無法再入隊新的元素，是一種滿的狀態，如果需再入隊，則會發生上溢出。表的前端還有空余位置（即front大于0），整個表并沒有占滿，但隊尾指示器rear已到達表的末端而無法在當前空間入隊新的元素，這種現象被稱為虛溢出或假溢出。每出隊一個元素，相應的空間就遭到丟棄無法再利用。假溢出舉例Job1Job2Job3Job4Job5Job61012345

appendJob1

appendJob2

appendJob3

serveJob1

appendJob4

appendJob5

appendJob6

serveJob2

appendJob7假溢出在最壞情況下，隊列是空的，但仍然無法在當前隊列空間入隊元素。即使隊列存儲區可以像Python的list一樣自動增長，但list首端由于出隊浪費的空間也無法再利用，從而導致空間利用率低下。因此必須對線性順序隊列方案加以改進才能達到實用的目的，通常采用循環隊列。假溢出出隊a2、a3、a4、a5將線性順序隊列的數組空間看成首尾相連的空間；使用初始容量為capacity的數組entry依次存儲從隊首到隊尾的所有元素；整型下標front和rear分別指示隊列的隊首位置和隊尾位置；三、循環隊列Job1Job2a2a3a4a51012345a6

appenda6[5][4][3][2][1][0]a2a3a4a5a6front=2rear=0rear=5入隊示例入隊方法rear=(rear+1)%capacityfront=2rear=0

servea2

servea3

servea4

servea5Job1a1a2a3a4a5a6front=2rear=0front=31012345front=4front=5front=0出隊示例出隊方法：front=(front+1)%capacity初始化frontandrear?front=0rear=-1或front=0rear=capacity-1入隊方法？rear=(rear+1)%capacity入隊需判別隊滿出隊方法？front=(front+1)%capacity出隊需判別隊空初始化frontandrear?front=0rear=-1或者front=0rear=capacity-1循環隊列

severa0front=0[5][4][3][2][1][0]rear=0a0front=1

appenda1隊空時，rear和front相差1個位置。在這個例子中，front=1，rear=0；a1rear=1

appenda2，3，4，5a2a3a4a5rear=5

appenda6rear=0a6隊滿時，rear和front也相差1個位置。在這個例子中，front=1，rear=0；存在問題:隊空和隊滿時，都滿足：front==(rear+1)%capacity如何判讀隊空和隊滿引入變量，如count和flag隊空：count==0隊滿：count==capacity隊滿：flag==True隊空：flag==False&&front==(rear+1)%capacity解決方法一[5][4][3][2][1][0]front=1a1a2a3a4a5rear=5少用一個空間的方法人為將隊滿條件修改為：front==(rear+2)%capacity隊空條件

front==(rear+1)%capacity解決方法二循環隊列實現隊列的鏈式存儲33隊列的鏈式存儲表示—鏈隊列帶頭結點的單鏈表用front和rear兩個指針表示一個鏈隊列front指向頭結點，rear指向隊尾結點（空隊列時指向頭結點）a）非空隊列的鏈式結構b）空隊列的鏈式結構鏈隊列結點結構鏈隊列類實現∧item

new_rearfrontan-1a0a1rear×rear∧鏈隊列類入隊算法defappend(self,item):

new_rear=QueueNode(item)self._rear.next=new_rearself._rear=new_rearfront∧an-1a0a1rear×

old_first×defserve(self):

ifself.empty():

returnNone

else:

ifself._rear==old_first:

self._rear=self._frontfronta0∧rear

old_first×rear鏈隊列類出隊算法old_first=self._front.next

self._front.next=old_first.next

item=old_first.entrydelold_first

returnitem∧順序結構，可能發生上溢出與下溢出鏈式結構，可能發生下溢出上溢出（overflow）與下溢出（underflow）隊列的應用迷宮求解打印楊輝三角形多項式運算打印隊列模擬應用舉例（1）假設目前到達下標為(i,j)的可通位置A，接著依次探索A位置的東南西北四個鄰居位置，假設為A0,A1,A2,A3，如該Ai鄰居位置已為出口，則找到路徑結束探索，輸出路徑；如該鄰居位置不通或已經走過，則跳過該位置；如所有Ai位置都不通或已經走過，則說明無法從A到達出口。（2）接著依次從A0,A1,A2,A3（假設都可通）位置開始重復步驟（1），即在還沒有找到終點并還有未探索位置的情況下，依次探索：A0的四個相鄰位置A00,A01,A02,A03；A1的四個相鄰位置A10,A11,A12,A13；A2的四個相鄰位置A20,A21,A22,A23；A3的四個相鄰位置A30A31,A32,A33。如果還沒有找到路徑并還有未探索位置，則再按剛才各探索位置Aij的次序探索各可通位置Aij的可通未走過鄰居位置，依次類推……，直到找到一條路徑位置或者所有可通位置都已探索過仍沒有找到路徑為止。基于隊列的迷宮求解42廣度優先搜索策略從(i,j)位置開始探測迷宮利用隊列先進先出的特性得到從上到下、從左到右的搜索次序。為了得到第i+1層的每個位置的坐標，可以在隊列中依次存放第i層的所有可通位置的坐標，然后逐個出隊各位置pos，同時生成pos位置的各個未走過可通鄰居并入隊，當i層位置全部出隊時，第i+1層的位置則全部入隊，重復出隊和入隊操作，直到遇到出口或隊列為空。如遇到出口，則輸出迷宮路徑。用字典precedent記錄每個可通位置的前驅位置，以方便最后輸出路徑。算法基本思想（1）如入口位置不通，找不到路徑，輸出相應信息，返回；（2）如入口位置即為出口位置，輸出相應信息，返回；（3）初始化字典precedent；小烏龜移動至入口位置，對該位置做已走過標記（黑色圓點）；將入口位置放入初始為空的隊列q中；（4）當隊列q非空時，循環（外層）執行：出隊當前位置pos，小烏龜移動至該位置（其運動軌跡不顯示）；循環（內層）檢查它的4個相鄰位置nextPos，如果nextPos可通且未走過，則：小烏龜從pos移動到nextPos，同時顯示出其運動軌跡；并對nextPos位置做已走過標記（黑色圓點）；如nextPos為出口，則調用buildPath顯示出路徑并結束。否則，將nextPos位置入隊，同時在precedent字典中設置nextPos的前驅為pos。并且為了能在可視化界面中能看清小烏龜將從pos走向下一個位置的，此時，將小烏龜再次定位到pos位置。（5）如隊列為空，則沒有找到路徑。算法步驟（1）如入口位置不通，找不到路徑，輸出相應信息，返回；（2）如入口位置即為出口位置，輸出相應信息，返回；（3）初始化字典precedent；小烏龜移動至入口位置，對該位置做已走過標記（黑色圓點）；將入口位置放入初始為空的隊列q中；算法（4）當隊列q非空時，循環（外層）執行：出隊當前位置pos，小烏龜移動至該位置（其運動軌跡不顯示）；循環（內層）檢查它的4個相鄰位置nextPos，如果nextPos可通且未走過，則：小烏龜從pos移動到nextPos，同時顯示出其運動軌跡；并對nextPos位置做已走過標記（黑色圓點）；如nextPos為出口，則調用buildPath顯示出路徑并結束。否則，將nextPos位置入隊，同時在precedent字典中設置nextPos的前驅為pos。并且為了能在可視化界面中能看清小烏龜將從pos走向下一個位置的，此時，將小烏龜再次定位到pos位置。（5）如隊列為空，則沒有找到路徑。算法分16組，每組5人，具體見雨課堂分組提交源程序、完整實驗報告組長和組員分工自行安排，實驗報告中注明分工情況迷宮求解分組實驗支持在線性表的兩端進行插入和刪除，這就是雙端隊列（Double-endedQueue或者deque，發音為Deck）。可以認為雙端隊列是棧和隊列的泛化，棧和隊列是雙端隊列的特例。雙端隊列T類型元素構成的雙端隊列是由T類型元素構成的有限序列，并且具有以下基本操作：1）構造一個空雙端隊列(init)2）判斷一個雙端隊列是否為空(empty)3）求雙端隊列的長度(len)4）在雙端隊列尾部入隊一個元素(append)5）在雙端隊列頭部入隊一個元素(appendleft)6）在雙端隊列尾部出隊一個元素(pop)7）在雙端隊列頭部出隊一個元素(popleft)8）讀取雙端隊列頭部元素(getleft)9）讀取雙端隊列尾部元素(getright)雙端隊列的抽象數據類型Python的標準模塊collection中提供雙端隊列類deque引入雙端隊列：fromcollectionsimportdeque內部實現采用雙向塊鏈表結構，即雙向鏈表中每個結點的數據域中存放多個元素，此時結點被稱為塊(block)。Python雙端隊列的塊結構：data域是長度為64的C底層數組，可存放64個元素（64個Python對象的指針）leftlink指針指向前驅塊，rightlink指針指向后繼塊。Python中的雙端隊列及實現雙向非循環鏈表主要包含leftblock、rightblock、leftindex和rightindex等數據成員leftblock指針指示的塊中，data[leftindex]位置的元素對應于a0；rightblock指針指示的塊中，data[rightindex]位置的元素對應于an-1。Python雙端隊列存儲結構含有多個塊的非空deque對象生成一個塊，leftblock和rightblock指針都指著該塊，并且初始leftindex和rightindex為data數組的中間相鄰位置。如在雙端隊列尾部入隊(append)，則rightindex增1，將元素放在data[rightindex]位置；當在雙端隊列頭部入隊(appendleft)時，leftindex減1后將元素放在該位置。當該塊的64個空間用完后，若需要尾部入隊(append)，即再生成新塊插入在rightblock的右邊；若需要頭部入隊(appendleft)，即再生成新塊插入在leftblock的左邊。初始空雙端隊列從基本操作的時間性能來看，雙向塊鏈表結構可以確保不管做哪個方向的append或pop操作，除了被操作的數據元素之外，任何其他元素都不會被移動，因此append、appendleft、pop和popleft算法的時間復雜度為O(1)。與順序存儲實現相比，鏈表結構可以完全避免順序結構在初始分配空間用完時需重新分配更大空間并進行元素復制（類似于resize函數的功能）的問題，從而提高了性能的可預測性。與普通的結點大小為1的雙鏈表相比，元素的存儲密度得到顯著提高，也減少了malloc()和free()函數的頻繁調用，提高了效率。deque雙向塊鏈表結構優點雖然list對象也支持兩端的插入和刪除操作，但由于采用順序存儲方案，其pop(0)和insert(0,v)操作會產生O(n)內存移動成本，且會改變底層其它數據的位置。因此，在使用Python語言編寫程序時，如需在表的兩端做插入刪除時，應優先選擇deque而不是list。與用list實現的比較Python的deque對象支持的主要方法len()返回元素個數clear()刪除deque中的所有元素，讓它的長度為0。append(x)在deque的右邊插入x。appendleft(x)在deque的左邊插入x。pop()從deque的右側刪除并返回一個元素。如果不存在元素，則引發一個IndexError。popleft()從deque的左側刪除并返回一個元素。如果不存在元素，則引發一個IndexError。[0]訪問左端元素，O(1)[-1]訪問右端元素，O(1)[j]索引訪問在兩端都是O(1)，但在中間減慢到O(n)。對于快速隨機訪問，請使用列表代替。用雙端隊列實現普通隊列fromcollectionsimportdeque

classQueue(object):

def__init__(self):

self._deque=deque()

defempty(self):

returnlen(self._deque)==0

def__len__(self):

returnlen(self._deque)

defappend(self,value):

returnself._deque.append(value)

defserve(self):

ifnotself.empty():

returnself._deque.popleft()