數(shù)據(jù)的排序與查找迭代與遞歸數(shù)據(jù)的排序數(shù)據(jù)的查找迭代的概念迭代的基本要點遞歸的概念遞歸的基本要點排序的概念冒泡排序法直接插入排序法查找的概念順序查找二分查找sortbubblesortstraightinsertionsortsearchsequentialsearchbinarysearch復習第三單元第4單元隊列及其應用

隊列是一種操作受限的線性結構，數(shù)據(jù)元素只能在一端進，在另一端出，且具有“先進先出”的特征。隊列出現(xiàn)在日常生活各類“排隊”活動中，如影院排隊入場、商店排隊付款和餐廳排除就餐就時都會形成隊列。另外，計算機科學中的很多功能，如打印隊列、進程調度和鍵盤緩沖等也都是利用隊列結構來實現(xiàn)的。

1.本單元通過“排隊買票”項目，理解隊列結構的基本概念及特征，學習隊列的兩種實現(xiàn)方法2.通過“基數(shù)排序”和“餐館排隊取號模擬系統(tǒng)”項目學習并親歷利用隊列解決問題的一般方法和過程，體驗迭代思想在問題解決中的應用。第4單元隊列及其應用4.1隊列結構及其實現(xiàn)4.2基數(shù)排序4.3排隊取號模擬系統(tǒng)4.1隊列結構及其實現(xiàn)日常生活中，同學們都有哪些排隊的經(jīng)歷？1.食堂排隊買飯2.電影院排隊買票3.超市排隊結賬…………

排隊的過程會形成一個隊列，排在隊列最前面的優(yōu)先處理，后來的必須排在隊尾。計算機在解決問題的過程中也經(jīng)常會用到隊列。4.1隊列結構及其實現(xiàn)1.理解隊列的概念及特征。2.掌握隊列抽象數(shù)據(jù)類型的定義。3.掌握隊列的兩種實現(xiàn)方法。學習目標4.1隊列結構及其實現(xiàn)隊列的概念

隊列（queue）是一種操作受限制的線性結構，只允許在表的前端（隊首）進行數(shù)據(jù)元素刪除操作，在表的后端（隊尾）進行插入操作。

在隊列中插入一個數(shù)據(jù)元素稱為入隊，從隊列中刪除一個數(shù)據(jù)元素稱為出隊。因為隊列只允許在隊尾插入、在隊首刪除，所以先進入隊列的元素先從隊列中刪除，故隊列又稱為先進先出（FirstInFirstOut,FIFO）線性表。4.1隊列結構及其實現(xiàn)隊列的概念任務一體驗排隊買票如果我們將排隊買票的人抽象成一個數(shù)據(jù)元素a，那么排隊買票的隊列可以用圖4.1.2表示。隊首隊尾a4………ana1a2a3圖4.1.2買票隊列根據(jù)圖4.1.2所示，分析排隊買票的情況，完成以下問題。（1）購票的行為發(fā)生在隊列的

；完成購票的人離開隊列后，隊列有什么變化？（2）新來的買票人排在隊列的

；購票的人增加后，隊列有什么變化？隊首隊尾活動1認識生活中的隊列4.1隊列結構及其實現(xiàn)隊列的概念任務一體驗排隊買票活動2觀察排隊買票

暑假期間，小明擔任了天文館售票處的志愿者工作，工作內(nèi)容是維持游客的買票秩序，在開始售票前后的一段時間內(nèi)（7：50~8：00），他觀察到排隊買票的隊列發(fā)生了以下變化。4.1隊列結構及其實現(xiàn)隊列的概念任務一體驗排隊買票活動2觀察排隊買票（1）7：50，售票窗口前沒有人排隊。7:50（2）7：55，售票窗口前有5個人（用p1,p2,p3,p4,p5表示）依次在排隊。p1p2p3p4p57:554.1隊列結構及其實現(xiàn)（3）8：00，開始售票，有3個人（p1,p2,p3）陸續(xù)買票離開，又來了4個人（p6,p7,p8,p9）依次排入隊中。p4p5p6p7p88:00p9任務一體驗排隊買票活動2觀察排隊買票根據(jù)上述觀察，思考并回答下面的問題。（1）最先進入隊列的是

。（2）p3買完票離開后，排在隊首的人是

，隊列里有

個人在排列。p1,p2,p3,p4,p5p46隊列的概念4.1隊列結構及其實現(xiàn)隊列抽象數(shù)據(jù)類型

為了在程序中使用隊列結構來解決問題，我們需要定義隊列數(shù)據(jù)類型（ADTQueue）。根據(jù)問題解決需要，我們?yōu)殛犃袛?shù)據(jù)類型定義了如下接口。ADTQueue:Queue():創(chuàng)建一個空隊列，返回值是一個空的隊列。enQueue(item):將數(shù)據(jù)元素item添加到隊尾，無返回值。deQueue():從隊首刪除數(shù)據(jù)元素，返回隊首數(shù)據(jù)元素。size():返回隊列中數(shù)據(jù)元素的個數(shù)。isEmpty():判斷是否為空隊列，返回布爾值。4.1隊列結構及其實現(xiàn)編程實現(xiàn)任務一體驗排隊買票活動3實現(xiàn)排隊買票

有了隊列抽象數(shù)據(jù)類型，我們就可以用程序來實現(xiàn)買票人的入隊、出隊以及統(tǒng)計排隊人數(shù)的操作了。

假設有5個人（用p1,p2,p3,p4,p5表示）依次前來排隊買票，完成排隊買票的過程如下。根據(jù)操作描述補全代碼。4.1隊列結構及其實現(xiàn)任務二編程實現(xiàn)排隊買票活動1用順序存儲實現(xiàn)隊列

隊列抽象數(shù)據(jù)類型主要包括創(chuàng)建隊列、入隊、出隊、統(tǒng)計隊列數(shù)據(jù)元素個數(shù)、判斷隊列是否為空等操作接口。隊列的順序存儲實現(xiàn)，可以用Python列表數(shù)據(jù)類型來實現(xiàn)。編程實現(xiàn)4.1隊列結構及其實現(xiàn)任務二編程實現(xiàn)排隊買票活動1用順序存儲實現(xiàn)隊列

（1）創(chuàng)建隊列創(chuàng)建空隊列，就是建立一個空的列表，用屬性items來保存隊列中的數(shù)據(jù)元素。請補全下面的代碼。編程實現(xiàn)classQueue():def__init__(self):#創(chuàng)建隊列self.items=[]#空列表第4單元隊列及其應用任務二編程實現(xiàn)排隊買票活動1用順序存儲實現(xiàn)隊列編程實現(xiàn)defenQueue(self,item):#入隊self.items.append(item)#隊尾增加一個數(shù)據(jù)元素

(2)入隊入隊操作就是在列表items的最后添加一個新的數(shù)據(jù)元素item。例如，p6入隊的過程如圖4.1.3所示。4.1隊列結構及其實現(xiàn)任務二編程實現(xiàn)排隊買票活動1用順序存儲實現(xiàn)隊列

（3）出隊出隊操作就是移除并返回列表items中的第一個數(shù)據(jù)元素。例如，p1出隊的過程如圖4.1.4所示。編程實現(xiàn)defdeQueue(self):#出隊returnself.items.pop(0)#移除隊首元素并返回移除后的隊首數(shù)據(jù)元素defsize(self):returnlen(self.items)#返回隊列的數(shù)據(jù)元素個數(shù)defisEmpty(self):returnself.items==[]#返回隊列是否為空的判斷值4.1隊列結構及其實現(xiàn)任務二編程實現(xiàn)排隊買票活動2用鏈式存儲實現(xiàn)隊列

除了利用順序存儲實現(xiàn)隊列以外，還可以使用另一種方法——基于節(jié)點引用的鏈表方式。（1）創(chuàng)建空隊列創(chuàng)建空隊列，也可以稱為隊列的初始化，將隊首節(jié)點引用和隊尾節(jié)點引用都指向空，如圖4.1.5所示。classQueue():def__init__(self):self.head=None

#隊首指向空節(jié)點self.rear=None

#隊尾指向空節(jié)點編程實現(xiàn)4.1隊列結構及其實現(xiàn)任務二編程實現(xiàn)排隊買票活動2用鏈式存儲實現(xiàn)隊列編程實現(xiàn)

(2)入隊入隊操作就是在鏈表的隊尾插入一個節(jié)點。例如，p5入隊的過程如圖4.1.6和圖4.1.7所示。defenQueue(self,item):#將元素item加入隊列，入隊p=Node(item)#生成節(jié)點ifself.head==None:#判斷隊首節(jié)點是否為空self.head=p#隊首指向新節(jié)點self.rear=p#隊尾指向新節(jié)點else:tp=self.reartp.next=p#隊首指向新節(jié)點self.rear=p#隊尾指向新節(jié)點4.1隊列結構及其實現(xiàn)任務二編程實現(xiàn)排隊買票活動2用鏈式存儲實現(xiàn)隊列編程實現(xiàn)

(3)出隊

出隊操作就是在鏈表的首端刪除一個節(jié)點，修改頭節(jié)點引用。例如，p1出隊的過程如圖4.1.8所示。defdeQueue(self):#刪除隊首元素，出隊ifself.head==None:returnNoneresult=self.head.data#獲取隊首節(jié)點數(shù)據(jù)元素self.head=self.head.next#重新設置頭節(jié)點returnresult#返回節(jié)點數(shù)據(jù)4.1隊列結構及其實現(xiàn)任務二編程實現(xiàn)排隊買票活動2用鏈式存儲實現(xiàn)隊列編程實現(xiàn)

(4)統(tǒng)計隊列數(shù)據(jù)元素個數(shù)

統(tǒng)計隊列數(shù)據(jù)元素個數(shù)，就是要遍歷鏈表中的每一個節(jié)點。defsize(self):#統(tǒng)計隊列的數(shù)據(jù)元素個數(shù)current=self.head#獲取到頭節(jié)點count=0#初始化數(shù)據(jù)元素個數(shù)統(tǒng)計變量whilecurrent!=None:#判斷當前節(jié)點不為空節(jié)點count=count+1#數(shù)據(jù)元素個數(shù)增加一個current=current.next#獲取下一個節(jié)點returncount#返回隊列的數(shù)據(jù)元素個數(shù)4.1隊列結構及其實現(xiàn)任務二編程實現(xiàn)排隊買票活動2用鏈式存儲實現(xiàn)隊列編程實現(xiàn)

(5)判斷隊列是否為空defisEmpty(self):#判斷隊列是否為空returnself.head==None4.1隊列結構及其實現(xiàn)列表實現(xiàn)的不同方案

隊列是一種要求先進先出的數(shù)據(jù)結構，需要在表的一端插入數(shù)據(jù)元素，在另一端刪除數(shù)據(jù)元素。用列表實現(xiàn)隊列存在兩種情況：一種情況是隊首放在列表頭