4.1《隊(duì)列結(jié)構(gòu)及其實(shí)現(xiàn)》

4.1隊(duì)列結(jié)構(gòu)及其實(shí)現(xiàn)高中信息技術(shù)/教科版/選擇性必修1目錄1.情景導(dǎo)入，引入新課2.體驗(yàn)活動(dòng)，初識(shí)隊(duì)列3.探究隊(duì)列抽象數(shù)據(jù)類型及其應(yīng)用4.用順序存儲(chǔ)實(shí)現(xiàn)隊(duì)列5.用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列6.課堂小結(jié)1.情景導(dǎo)入，引入新課”利用假期時(shí)間去游覽祖國(guó)各地的名讀萬(wàn)卷書(shū)，行萬(wàn)里路。'勝古跡，既可以放松緊張的心情，又可以學(xué)到很多知識(shí)。在旅游風(fēng)景區(qū)，排隊(duì)是不可避免的現(xiàn)象。本節(jié)圍繞“排隊(duì)買票”項(xiàng)目展開(kāi)學(xué)習(xí)，通過(guò)項(xiàng)目活動(dòng)認(rèn)識(shí)生活中的隊(duì)列，學(xué)習(xí)利用抽象數(shù)據(jù)類型定義隊(duì)列，編寫(xiě)代碼實(shí)現(xiàn)隊(duì)列的基本操作。本節(jié)主要包含“體驗(yàn)排隊(duì)買票”和“編程實(shí)現(xiàn)排隊(duì)買票”兩個(gè)任務(wù)。2.體驗(yàn)活動(dòng)，初識(shí)隊(duì)列

任務(wù)一體驗(yàn)排隊(duì)買票

活動(dòng)1認(rèn)識(shí)生活中的隊(duì)列如果我們將排隊(duì)買票的人抽象成一個(gè)數(shù)據(jù)元素a，那么排隊(duì)買票的隊(duì)列可以用圖4.1.2表示。隊(duì)首隊(duì)尾a1a2a3……an

排隊(duì)買票

任務(wù)一體驗(yàn)排隊(duì)買票

活動(dòng)1認(rèn)識(shí)生活中的隊(duì)列根據(jù)圖4.1.2所示，分析排隊(duì)買票的情況，完成以下問(wèn)題。(1)購(gòu)票的行為發(fā)生在隊(duì)列的

，完成購(gòu)票的人離開(kāi)隊(duì)列后，隊(duì)列有什么變化?(2)新來(lái)的買票人排在隊(duì)列的

購(gòu)票的人增加后，隊(duì)列有什么變化?填一填隊(duì)首隊(duì)尾隊(duì)列是一種操作受限制的線性結(jié)構(gòu)，只允許在表的前端(隊(duì)首)進(jìn)行數(shù)據(jù)元素刪除操作，在表的后端(隊(duì)尾)進(jìn)行插入操作在隊(duì)列中插入一個(gè)數(shù)據(jù)元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)數(shù)據(jù)元素稱為出隊(duì)。因?yàn)殛?duì)列只允許在隊(duì)尾插入、在隊(duì)首刪除，所以先進(jìn)入隊(duì)列的元素先從隊(duì)列中刪除，故隊(duì)列又稱為先進(jìn)先出線性表。隊(duì)列3.探究隊(duì)列抽象數(shù)據(jù)類型及其應(yīng)用

任務(wù)一體驗(yàn)排隊(duì)買票

活動(dòng)2觀察排隊(duì)買票(1)7:50，售票窗口前沒(méi)有人排隊(duì)。(2)7:55，售票窗口前有5個(gè)人(用p1，p2，p3，p4，p5表示)依次在排隊(duì)。(3)8:00，開(kāi)始售票，有3個(gè)人(pl，p2，p3)陸續(xù)買票離開(kāi)又來(lái)了4個(gè)人(p6，p7，p8，p9)依次排入隊(duì)中根據(jù)上述觀察，思考并回答下面的問(wèn)題。(1)最先進(jìn)入隊(duì)列的是

.(2)p3買完票離開(kāi)后，排在隊(duì)首的人是

，隊(duì)列里有

個(gè)人在排隊(duì)。p1p46任務(wù)一體驗(yàn)排隊(duì)買票

活動(dòng)2觀察排隊(duì)買票ADTQueue:Queue（）：創(chuàng)建一個(gè)空隊(duì)列，返回值是一個(gè)空的隊(duì)列。enQueue(item)：將數(shù)據(jù)元素item添加到隊(duì)尾，無(wú)返回值deQueu（）：從隊(duì)首刪除數(shù)據(jù)元素，返回隊(duì)首數(shù)據(jù)元素siz（）：返回隊(duì)列中數(shù)據(jù)元素的個(gè)數(shù)。isEmpty（）：判斷是否為空隊(duì)列，返回布爾值隊(duì)列抽象數(shù)據(jù)類型任務(wù)一體驗(yàn)排隊(duì)買票

活動(dòng)2觀察排隊(duì)買票假設(shè)有5個(gè)人(用p1，p2p3，p4，p5表示)依次前來(lái)排隊(duì)買票，完成排隊(duì)買票的過(guò)程如下。請(qǐng)根據(jù)操作描述補(bǔ)全下面的代碼。01.ticketLine=Queue()

#創(chuàng)建空隊(duì)列02.ticketLine.enQueue(p1)

#p1入隊(duì)03.ticketLine.enQueue(p2)

#p2入隊(duì)04.

.#p3入隊(duì)05.

.#p4入隊(duì)06.

.#p5入隊(duì)ticketLine.enQueue(p3)ticketLine.enQueue(p4)ticketLine.enQueue(p5)任務(wù)一體驗(yàn)排隊(duì)買票

活動(dòng)2觀察排隊(duì)買票假設(shè)有5個(gè)人(用p1，p2p3，p4，p5表示)依次前來(lái)排隊(duì)買票，完成排隊(duì)買票的過(guò)程如下。請(qǐng)根據(jù)操作描述補(bǔ)全下面的代碼。07.ticketLine.deQueue(

)

#p1出隊(duì)08.ticketLine.deQueue(

)

#p2出隊(duì)09.num=ticketLine.size(

)

#統(tǒng)計(jì)當(dāng)前排隊(duì)人數(shù)10.

#p3出隊(duì)11.

#p4出隊(duì)12.

#p5出隊(duì)13.

#查看隊(duì)列是否為空ticketLine.deQueue(

)

ticketLine.deQueue(

)

ticketLine.deQueue(

)

ticketLine.deQueue(

)

4.用順序存儲(chǔ)實(shí)現(xiàn)隊(duì)列

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)1用順序存儲(chǔ)實(shí)現(xiàn)隊(duì)列隊(duì)列抽象數(shù)據(jù)類型主要包括創(chuàng)建隊(duì)列、入隊(duì)、出隊(duì)、統(tǒng)計(jì)隊(duì)列數(shù)據(jù)元素個(gè)數(shù)、判斷隊(duì)列是否為空等操作接口。隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)可以用Python列表數(shù)據(jù)類型來(lái)實(shí)現(xiàn)。(1)創(chuàng)建隊(duì)列。創(chuàng)建空隊(duì)列，就是建立一個(gè)空的列表，用屬性items來(lái)保存隊(duì)列中的數(shù)據(jù)元素。請(qǐng)補(bǔ)全下面的代碼。01.classQueue:02.def__init__(self):

#創(chuàng)建隊(duì)列03.self.items=

#空列表[]

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)1用順序存儲(chǔ)實(shí)現(xiàn)隊(duì)列(2)入隊(duì)。入隊(duì)操作就是在列表items的最后添加一個(gè)新的數(shù)據(jù)元素item。例如，p6入隊(duì)的過(guò)程如圖4.1.3所示。p1p2p3p3p4p5隊(duì)首原隊(duì)尾新隊(duì)尾根據(jù)圖4.1.3所示，補(bǔ)全enQueue方法的實(shí)現(xiàn)代碼。04.defenQueue(self,item):

#入隊(duì)05.self.items.append(

）#隊(duì)尾增加一個(gè)數(shù)據(jù)元素

p6入隊(duì)item

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)1用順序存儲(chǔ)實(shí)現(xiàn)隊(duì)列(3)出隊(duì)。出隊(duì)操作就是移除并返回列表items中的第一個(gè)數(shù)據(jù)元素。例如，p1出隊(duì)的過(guò)程如圖4.1.4所示。p1p2p3p3p4p5原隊(duì)首隊(duì)尾根據(jù)圖4.1.4所示，補(bǔ)全deQueue方法的實(shí)現(xiàn)代碼06.defdeQueue(self):

#出隊(duì)07.returnself.items.pop(

）#移除隊(duì)首元素并返回圖4.1.4p1出隊(duì)新隊(duì)首0

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)1用順序存儲(chǔ)實(shí)現(xiàn)隊(duì)列（4）統(tǒng)計(jì)隊(duì)列數(shù)據(jù)元素個(gè)數(shù)。08.defsize(self):09.returnlen(self.items)

#返回隊(duì)列的數(shù)據(jù)元素個(gè)數(shù)(5)判斷隊(duì)列是否為空。10.defisEmpty(self):11.returnself.items==[]

#返回隊(duì)列是否為空的判斷值

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)1用順序存儲(chǔ)實(shí)現(xiàn)隊(duì)列隊(duì)列是一種要求先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，需要在表的一端插入數(shù)據(jù)元素，在另一端刪除數(shù)據(jù)元素。用列表實(shí)現(xiàn)隊(duì)列存在兩種情況:一種情況是隊(duì)首放在列表頭;另一種情況是隊(duì)首放在列表尾。兩種不同的情況，在實(shí)現(xiàn)入隊(duì)和出隊(duì)的操作中也存在差別，如表所示。列表實(shí)現(xiàn)的不同方案

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)1用順序存儲(chǔ)實(shí)現(xiàn)隊(duì)列將隊(duì)列抽象數(shù)據(jù)類型的順序存儲(chǔ)實(shí)現(xiàn)代碼輸入到文件中，保存為queue.py，利用排隊(duì)買票測(cè)試各個(gè)接口的效果。例如，小明和小梅來(lái)排隊(duì)買票，小明買到票出隊(duì)，統(tǒng)計(jì)當(dāng)前隊(duì)列中的排隊(duì)總?cè)藬?shù)。請(qǐng)補(bǔ)全下面的代碼。01.fromqueueimportQueue

#導(dǎo)入隊(duì)列02.ticketLine=

#創(chuàng)建隊(duì)列對(duì)象03.ticketLine.enQueue("小明")

#小明入隊(duì)04.

#小梅入隊(duì)05.

#小明出隊(duì)06.print(ticketLine.size())

#顯示當(dāng)前排隊(duì)總?cè)藬?shù)Queue()ticketLine.enQueue("小梅")

ticketLine.deQueue(

)

5.用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)2用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列(1)創(chuàng)建空隊(duì)列。創(chuàng)建空隊(duì)列，也可以稱為隊(duì)列的初始化，將隊(duì)首節(jié)點(diǎn)引用和隊(duì)尾節(jié)點(diǎn)引用都指向空，如圖4.1.5所示。圖4.1.5隊(duì)列初始化^headrear根據(jù)圖4.1.5的提示，補(bǔ)全隊(duì)列初始化代碼。01.classQueue():02.def__init__(self):03.self.head=None

#隊(duì)首指向空節(jié)點(diǎn)04.self.rear=

#隊(duì)尾指向空節(jié)點(diǎn)None

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)2用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列(2)入隊(duì)。入隊(duì)操作就是在鏈表的隊(duì)尾插入一個(gè)節(jié)點(diǎn)。例如，p5入隊(duì)的過(guò)程如圖4.1.6和圖4.1.7所示。p1p2p3p4^rearhead隊(duì)首隊(duì)尾圖4.1.6插入節(jié)點(diǎn)前p1p2p3p4rearhead隊(duì)首原隊(duì)尾p5^新隊(duì)尾圖4.1.7插入節(jié)點(diǎn)后

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)2用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列根據(jù)圖4.1.6和圖4.1.7的提示，補(bǔ)全enQueue方法的實(shí)現(xiàn)代碼。05.defenQueue(self，item):

#將元素item加入隊(duì)列，入隊(duì)06.p=Node(

)#生成新節(jié)點(diǎn)07.ifself.head==None:

#判斷隊(duì)首節(jié)點(diǎn)是否為空08.self.head=p

#隊(duì)首指向新節(jié)點(diǎn)09.self.rear=

#隊(duì)尾指向新節(jié)點(diǎn)10.else:11.tp=self.rear

#獲取當(dāng)前隊(duì)尾節(jié)點(diǎn)12.tp.next=p

#當(dāng)前隊(duì)尾指向新節(jié)點(diǎn)13.self.rear=

#隊(duì)尾指向新節(jié)點(diǎn)itempp

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)2用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列(3)出隊(duì)。出隊(duì)操作就是在鏈表的首端刪除一個(gè)節(jié)點(diǎn)，修改頭節(jié)點(diǎn)引用。例如，p1出隊(duì)的過(guò)程如圖4.1.8所示。p1p2p3p4rearhead原隊(duì)首p5^隊(duì)尾新隊(duì)首圖4.1.8刪除節(jié)點(diǎn)

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)2用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列根據(jù)圖4.1.8的提示，補(bǔ)全deQueue方法的實(shí)現(xiàn)代碼。14.defdeQueue(self):

#刪除隊(duì)首元素，出隊(duì)15.ifself.head==None:

#判斷隊(duì)列是否為空16.returnNone

#返回空17.result=

#獲取隊(duì)首節(jié)點(diǎn)數(shù)據(jù)元素18.self.head=

#重新設(shè)置隊(duì)首節(jié)點(diǎn)19.returnresult

#返回節(jié)點(diǎn)數(shù)據(jù)

任務(wù)二編程實(shí)現(xiàn)排隊(duì)買票

活動(dòng)2用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)隊(duì)列(4)統(tǒng)計(jì)隊(duì)列數(shù)據(jù)元素個(gè)數(shù)。統(tǒng)計(jì)隊(duì)列數(shù)據(jù)元素個(gè)數(shù)，就是要遍歷鏈表中的每一個(gè)節(jié)點(diǎn)，補(bǔ)全size方法的實(shí)現(xiàn)代碼。20.defsize(self):

#統(tǒng)計(jì)隊(duì)列的數(shù)據(jù)元素個(gè)數(shù)21.current=self.head

#獲取隊(duì)首節(jié)點(diǎn)22.count=

#初始化數(shù)據(jù)元素個(gè)數(shù)統(tǒng)計(jì)變量23.whilecurrent!=None:

#判斷當(dāng)前節(jié)點(diǎn)不為空節(jié)點(diǎn)24.count=

#數(shù)據(jù)元素個(gè)數(shù)增加一個(gè)25.current=current.next

#獲取下一個(gè)節(jié)點(diǎn)26.returncount

#返回隊(duì)列的數(shù)據(jù)元素個(gè)數(shù)0count+