探索電子排隊(duì)預(yù)定功能的實(shí)現(xiàn)-隊(duì)列的應(yīng)用-高中信息技術(shù)同步精品課堂（滬科版2019選擇性必修1）

項(xiàng)目四探索電子排隊(duì)預(yù)定功能的實(shí)現(xiàn)

—隊(duì)列的應(yīng)用010203熟練使用python程序設(shè)計(jì)算法使用隊(duì)列數(shù)據(jù)結(jié)構(gòu)完成預(yù)定程序。了解電子排隊(duì)預(yù)訂系統(tǒng)，并理解排隊(duì)預(yù)定遵循的規(guī)律。學(xué)習(xí)目標(biāo)知道隊(duì)列的定義，并掌握隊(duì)列遵循的原則。01問題導(dǎo)入導(dǎo)入日常生活中，商品和服務(wù)需求大于供給的情況時(shí)有發(fā)生，例如限量商品發(fā)售、醫(yī)院專家門診號(hào)等。為了避免商場、醫(yī)院或營業(yè)廳里人潮擁擠，等候的客戶排起長龍，一些企事業(yè)單位在相應(yīng)網(wǎng)站或手機(jī)App上提供了預(yù)約服務(wù)，如圖3-1所示。客戶輸入身份、賬號(hào)信息提交后自動(dòng)進(jìn)入電子排隊(duì)預(yù)訂系統(tǒng)。你知道電子排隊(duì)預(yù)訂系統(tǒng)是如何實(shí)現(xiàn)排隊(duì)預(yù)約的嗎？圖3-1電子排隊(duì)預(yù)訂系統(tǒng)1.分析問題電子排隊(duì)預(yù)訂系統(tǒng)是計(jì)算機(jī)自動(dòng)控制的排隊(duì)系統(tǒng)，排隊(duì)的特點(diǎn)是先來先服務(wù)，那計(jì)算機(jī)是怎么實(shí)現(xiàn)自動(dòng)排隊(duì)的呢？當(dāng)客戶在電子排隊(duì)預(yù)訂系統(tǒng)提交信息后，客戶的預(yù)訂數(shù)據(jù)就進(jìn)入隊(duì)列，稱為進(jìn)隊(duì)（也稱入隊(duì)），即在隊(duì)尾（rear）插入一個(gè)客戶賬號(hào)數(shù)據(jù)；當(dāng)正式購買商品時(shí)就到隊(duì)列中取出客戶賬號(hào)數(shù)據(jù)，稱為出隊(duì)，即在隊(duì)首（front）取出一個(gè)客戶賬號(hào)數(shù)（客戶賬號(hào)數(shù)據(jù)暫用A0001形式替代），如圖3-2所示。圖3-2預(yù)訂—購買隊(duì)列用先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)排隊(duì)的客戶賬號(hào)數(shù)據(jù)，就可以方便地實(shí)現(xiàn)先來先服務(wù)，這種數(shù)據(jù)結(jié)構(gòu)稱為隊(duì)列?；?動(dòng)4.1假設(shè)排隊(duì)預(yù)訂客戶賬號(hào)數(shù)據(jù)為A0001、A0002、A0003、A0004，下面空的隊(duì)列中依次A0001進(jìn)隊(duì)，A0002進(jìn)隊(duì)，A0003進(jìn)隊(duì)，叫號(hào)出隊(duì)，A0004進(jìn)隊(duì)，叫號(hào)出隊(duì)，叫號(hào)出隊(duì)，叫號(hào)出隊(duì)，畫出隊(duì)列的變化過程。4.2請(qǐng)嘗試寫出隊(duì)列的抽象數(shù)據(jù)類型定義。排隊(duì)預(yù)訂的隊(duì)列變化過程如圖3-3所示（為圖示方便，暫定圖中隊(duì)列空間只有4個(gè)）?？蛻纛A(yù)訂即為進(jìn)隊(duì)，假設(shè)A0001表示第一個(gè)客戶賬號(hào)數(shù)據(jù)，購買即為隊(duì)首出隊(duì)。圖中rear指向隊(duì)列的尾端，圖中front指向隊(duì)列的首端。隊(duì)列在計(jì)算機(jī)里怎樣表示呢？隊(duì)列是操作上有限制的線性表，既可以用數(shù)組表示一個(gè)隊(duì)列，也可以用鏈表表示一個(gè)隊(duì)列。一般若問題規(guī)模已知，即總的進(jìn)隊(duì)元素個(gè)數(shù)已知的話，隊(duì)列可以用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，即用數(shù)組表示隊(duì)列；若進(jìn)隊(duì)元素個(gè)數(shù)無法預(yù)計(jì)，則隊(duì)列可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)，即用鏈表表示隊(duì)列。2.設(shè)計(jì)算法根據(jù)上述算法，可以利用學(xué)過的編程知識(shí)來編程實(shí)現(xiàn)排隊(duì)預(yù)訂。首先要定義隊(duì)列的類型并進(jìn)行初始化（即置空）操作，指針變量要設(shè)定初始值。用列表表示隊(duì)列的類型定義如下：classSqQueue:def__init__(self,size):#隊(duì)列初始化self.size=size#定義隊(duì)列長度self.queue=['']*size#存儲(chǔ)隊(duì)列元素的列表self.front=0#頭指針self.rear=0#尾指針self.number=0#計(jì)數(shù)器3.程序?qū)崿F(xiàn)4.4打開配套資源中“循環(huán)順序隊(duì)列.py”程序，補(bǔ)充完整以下代碼，并進(jìn)行運(yùn)行測試，模擬實(shí)現(xiàn)排隊(duì)預(yù)訂功能。defEnQueue(self,e):#進(jìn)隊(duì)程序if(self.number==self.size):print（"隊(duì)滿，不能進(jìn)"）else:self.queue[self.rear]=eself.number=self.number+1defOutQueue(self):#出隊(duì)程序ifself.number==0:print（"隊(duì)空"）return-1else:e=self.queue[self.front]self.number=self.number-1returne活?動(dòng)02知識(shí)鏈接排隊(duì)的隊(duì)伍在計(jì)算機(jī)中稱為隊(duì)列，隊(duì)列是一種只能在表的首端取出數(shù)據(jù)，在表的尾端添加數(shù)據(jù)的線性表，即隊(duì)列是操作上有限制的線性表，隊(duì)列是一種先進(jìn)先出數(shù)據(jù)結(jié)構(gòu)。隊(duì)列的抽象數(shù)據(jù)類型表示如下：1.隊(duì)列隊(duì)列有兩種存儲(chǔ)方式，一種是用數(shù)組存儲(chǔ)，這種方式存儲(chǔ)的隊(duì)列稱為順序隊(duì)列；另一種用鏈表存儲(chǔ)，這種方式存儲(chǔ)的隊(duì)列稱為鏈隊(duì)列，如圖3-4所示。元素插入隊(duì)尾稱為進(jìn)隊(duì)，隊(duì)首元素取出稱為出隊(duì)。隊(duì)首用front指針指示，隊(duì)尾用rear指針指示。用數(shù)組存儲(chǔ)隊(duì)列元素時(shí)，會(huì)遇到指針溢出問題。即當(dāng)隊(duì)滿時(shí)，再有元素進(jìn)隊(duì)，就會(huì)產(chǎn)生指針的溢出（上溢出）；當(dāng)隊(duì)空時(shí)，再要取出元素，也會(huì)產(chǎn)生指針的溢出（下溢出）。另外，還有“假溢出”問題。隨著元素的進(jìn)隊(duì)和出隊(duì)，整個(gè)隊(duì)列是向數(shù)組下標(biāo)較大的位置移動(dòng)。當(dāng)移動(dòng)到數(shù)組中下標(biāo)最大的位置后，隊(duì)列的空間就用盡了。此時(shí)，即使數(shù)組下標(biāo)較小的位置處還有空閑空間，元素也無法進(jìn)隊(duì)了，這種現(xiàn)象就叫“假溢出”。解決以上問題可以有兩種方法：一是每次隊(duì)首元素出隊(duì)，后面的元素都向前移動(dòng)一次。但這種做法會(huì)使出隊(duì)效率較低。另一種方法是采用循環(huán)隊(duì)列，即把隊(duì)列的首尾相連，當(dāng)隊(duì)尾指針超出數(shù)組長度時(shí)，就將其設(shè)回到最初的隊(duì)首位置（數(shù)組下標(biāo)為0）。如圖3-5所示，圖中為8個(gè)空間的隊(duì)列形成的循環(huán)。為了能實(shí)現(xiàn)循環(huán)，可以采用指針加1除隊(duì)列空間數(shù)后取余，替代指針加1的方法，即rear=(rear+1)%size（隊(duì)尾指針循環(huán)），front=(front+1)%size（隊(duì)首指針循環(huán)），其中，%就是取余運(yùn)算，size為隊(duì)列的空間數(shù)。圖3-5循環(huán)隊(duì)列1.進(jìn)隊(duì)進(jìn)隊(duì)就是從隊(duì)尾添加數(shù)據(jù)的操作。順序隊(duì)列進(jìn)隊(duì)的算法思想：若隊(duì)列不滿，則將進(jìn)隊(duì)的元素送入尾指針rear所指空間，元素個(gè)數(shù)計(jì)數(shù)器增1，然后將尾指針rear往尾部方向移動(dòng)一位即指向新的隊(duì)尾。隊(duì)列的常用基本操作defEnQueue(self,e):if(self.number==self.size):print("隊(duì)滿，不能進(jìn)")else:self.queue[self.rear]=eself.rear=(self.rear+1)%self.sizeself.number=self.number+1return出隊(duì)就是在隊(duì)首取出數(shù)據(jù)的操作。順序隊(duì)列出隊(duì)的算法思想：若隊(duì)列不空，則將隊(duì)首指針front所指空間的內(nèi)容取出賦予變量，元素個(gè)數(shù)計(jì)數(shù)器減1，然后將首指針front往后移動(dòng)一位即指向新的首端。defOutQueue(self):if(self.n