數(shù)據(jù)結(jié)構(gòu)課件隊(duì)列ppt課件(已修改)
2025-05-11 02:57 本頁(yè)面
【正文】 ?棧 ?棧的應(yīng)用 ?隊(duì)列 ?隊(duì)列的應(yīng)用 隊(duì)列 抽象數(shù)據(jù)類型隊(duì)列的定義 隊(duì)列 (Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為 隊(duì)頭 (front)，允許插入的一端稱為 隊(duì)尾 (rear)。 （ a0, a1, ... , ai 1, ai , ai+1, …, a n1 ） 插入 刪除 例如：排隊(duì)購(gòu)物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開(kāi)隊(duì)列。因此隊(duì)列亦稱作 先進(jìn)先出 (First In First Out)的線性表，簡(jiǎn)稱 FIFO表。 a0 a1 a2 …… an1 rear 隊(duì)頭 隊(duì)尾 front 隊(duì) 列 的 示 意 圖 隊(duì)列的特點(diǎn) 先進(jìn)先出 說(shuō)明： 第一個(gè)入隊(duì)的元素在隊(duì)頭， 最后一個(gè)入隊(duì)的元素在隊(duì)尾， 第一個(gè)出隊(duì)的元素為隊(duì)頭元素， 最后一個(gè)出隊(duì)的元素為隊(duì)尾元素 隊(duì)列的抽象數(shù)據(jù)定義見(jiàn)書(shū)Ｐ 59 隊(duì)列的基本運(yùn)算 隊(duì)列可定義如下五種基本運(yùn)算： 1． 初始化隊(duì)列 InitQueue(amp。Q) 將隊(duì)列 Q設(shè)置成一個(gè)空隊(duì)列 。 2． 入隊(duì)列 EnQueue(amp。Q,X) 將元素 X插入到隊(duì)尾中 ， 也稱 “ 進(jìn)隊(duì) ” ， “ 插入 ” 。 3． 出隊(duì)列 DeQueue(amp。Q,amp。e) 將隊(duì)列 Q的隊(duì)頭元素刪除 ， 并用 e返回其值 ， 也稱 “ 退隊(duì) ” 、“ 刪除 ” 。 4． 取隊(duì)頭元素 GetHead(Q,amp。e) 得到隊(duì)列 Q的隊(duì)頭元素之值 ， 并用 e返回其值 。 5． 判隊(duì)空 QueueEmpty(Q) 判斷隊(duì)列 Q是否為空 ， 若為空返回 1， 否則返回 0。 非循環(huán)隊(duì)列和循環(huán)隊(duì)列 分配一塊連續(xù)的存儲(chǔ)區(qū)域來(lái)存放隊(duì)列里的元素。由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，因而要設(shè)兩個(gè)指針和分別指示隊(duì)頭和隊(duì)尾元素在隊(duì)列中的位置。 它們的初始值在隊(duì)列初始化時(shí)均應(yīng)置為０。入隊(duì)時(shí)將新元素插入所指的位置，然后尾指針加１。出隊(duì)時(shí)，刪去所指的元素，然后頭指針加１并返回被刪元素。由此可見(jiàn)， 當(dāng)頭尾指針相等時(shí)隊(duì)列為空 。 在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素的下一位置。 ０ １ ２ ３ 0 1 2 3 Front rear a b c Front rear (a)隊(duì)列初始為空 （ b） A,B,C入隊(duì) ０ １ ２ ３ ０ １ ２ ３ b c front rear front rear
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1