隊列的建立和實現(xiàn)PPT課件

1、第1頁/共24頁001 002 003 00n front rear 第2頁/共24頁隊列示意圖 an a2 a1隊頭(Front)隊尾(Rear) 第3頁/共24頁1.定義隊列 (Queue)是僅在表尾進行插入操作，在表頭進行刪除操作的線性表。表尾即an端，稱為隊尾；表頭即a1端，稱為隊頭。例如：隊列 Q= (a1, a2, a3 , , an-1, an )隊頭隊尾第4頁/共24頁與同線性表相同，仍為一對一關(guān)系。順序隊或鏈隊，以循環(huán)順序隊更常見。表尾插入元素稱為入隊；表頭刪除元素稱為出隊；訪問結(jié)點時依照先進先出（FIFO）的原則。 3.存儲結(jié)構(gòu)4.運算規(guī)則2.邏輯結(jié)構(gòu)第5頁/共24頁v頭、

2、尾指針和隊列中元素之間的關(guān)系frontfronta1a4a3a2(2) a1入隊入隊rear3210rearfrontrear新建空隊列時，令front=rear=0在隊尾插入新元素，“尾指針增1”刪除隊列頭元素，“頭指針增1”在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置。32103210(1) 空隊列空隊列(3) a2, a3, a4入隊入隊, a1出隊，隊滿出隊，隊滿第6頁/共24頁v順序隊列操作可能出現(xiàn)的問題rearfront初態(tài)fronta1a2a3reara1,a2,a3入隊rearfronta4a5a6rearfrontrearfront再有元素再

3、有元素進隊會怎進隊會怎樣？樣？a1,a2,a3出隊a4,a5,a6入隊a4,a5,a6出隊第7頁/共24頁順序隊列的出隊和入隊操作第8頁/共24頁v隊滿的三種情況1、所有單元都有元素；2、部分單元有元素；3、所有單元均無元素。當(dāng)隊滿時再要插入元素，稱為上溢。假溢出:隊空間中還有存儲單元未使用，但不能再插入元素;假溢出原因:頭、尾指針值總是不斷增加，已使用過的單元無法再使用。第9頁/共24頁v解決假溢出的方法1.將隊中元素依次向隊頭方向移動。 缺點：浪費時間。每移動一次，隊中元素都要移動。2.將隊空間設(shè)想成一個循環(huán)的表，即分配給隊列的個存儲單元可以循環(huán)使用，當(dāng)rear為m時，若向量的開始端空著，

4、又可從頭使用空著的空間。當(dāng)front為m時，也是一樣。fronta1a2anrear刪除刪除插入插入第10頁/共24頁循環(huán)隊列的入隊和出隊操作演示第11頁/共24頁使用循環(huán)隊列應(yīng)注意的問題：front012345rear空循環(huán)隊列a6a7a8a5a4a3012345frontrear滿循環(huán)隊列隊空條件：front = rear;隊滿條件：(1) 規(guī)定隊列中還有一個空的存儲單元時為隊滿，即為 front=(rear+1)MOD maxsize(MOD為取余運算符）(2) 設(shè)置一個計數(shù)器size記錄隊列中元素的個數(shù)。 size = 0 隊空 size = maxsize 隊滿第12頁/共24頁實現(xiàn)

5、方法：模(mod) 運算。插入元素： $L$rear = $e; $rear = ($rear+1) $ maxsize;刪除元素： $x = $L$front； $front=($front+1) $ maxsize；循環(huán)隊列：循環(huán)使用為隊列分配的存儲空間。 第13頁/共24頁第14頁/共24頁第15頁/共24頁第16頁/共24頁第17頁/共24頁第18頁/共24頁第19頁/共24頁 鏈隊列的概念鏈隊列-指用鏈表實現(xiàn)的隊列。通常用帶頭節(jié)點的單鏈表實現(xiàn)；并設(shè)置頭指針、尾指針，分別指向隊列的隊頭和隊尾。第20頁/共24頁空隊列：頭指針和尾指針均指向空的頭結(jié)點第21頁/共24頁鏈?zhǔn)疥犃腥腙牐海?）將隊尾rear的后繼設(shè)為新結(jié)點s;（2）將隊尾指針rear后移，即rear = rear-nex