棧與隊列(編輯修改稿)
2024-11-16 16:13 本頁面
【文章內(nèi)容簡介】 輸出 1 3 ( + 1 +進(jìn)棧 4 ( + 1 2 輸出 2 5 1 2 + +退棧輸出，退棧到（止 6 * 1 2 + *進(jìn)棧 7 * ( 1 2 + （進(jìn)棧 8 * ( ( 1 2 + （進(jìn)棧 9 * ( ( 1 2 + 8 輸出 8 10 * ( ( 1 2 + 8 進(jìn)棧 將中綴表達(dá)式 (1+2)*((82)/(74))變成等價的后綴表達(dá)式。 現(xiàn)在用棧來實(shí)現(xiàn)該運(yùn)算，棧的變化及輸出結(jié)果如下： 17/36 11 * ( ( 1 2 + 8 2 輸出 2 12 * ( 1 2 + 8 2 退棧輸出，退棧到（止 13 * ( / 1 2 + 8 2 / 進(jìn)棧 14 * ( / ( 1 2 + 8 2 （ 進(jìn)棧 15 * ( / ( 1 2 + 8 2 7 輸出 7 16 * ( / ( 1 2 + 8 2 7 進(jìn)棧 17 * ( / ( 1 2 + 8 2 7 4 輸出 4 18 * ( / 1 2 + 8 2 7 4 退棧輸出，退棧到（止 19 * 1 2 + 8 2 7 4 / /退棧輸出，退棧到（止 20 1 2 + 8 2 7 4 / * *退棧并輸出 18/36 隊列定義 隊列是只能在表的一端進(jìn)行插入、在另一端進(jìn)行刪除操作的線性表。允許刪除元素的一端稱為隊頭，允許插入元素的一端稱為隊尾。 顯然不論元素按何種順序進(jìn)入隊列，也必然按這種順序出隊列，所以隊列又稱為先進(jìn)先出（ FIFO）表。隊列有兩個活動端，所以設(shè)置了對頭和隊尾兩個位置指針。一般隊頭指針記作 front，隊尾指針記作 rear。 a b c front rear 入隊 出隊 隊列示意圖 19/36 循環(huán)隊列 — 隊列順序存儲 順序存儲的隊列中，每次出隊列的元素必定是隊頭元素，因此如果采取與普通順序表同樣的操作方式，則每次出隊操作必然將整個隊列向前移動，這使得效率大大降低。 因此 在順序存儲的隊列中，出隊和入隊操作都不移動元素而是移動指針。 20/36 為方便起見，這里規(guī)定隊頭指針 front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素所在位置。這樣，入隊和出隊操作的執(zhí)行步驟都是首先執(zhí)行指針移動，再進(jìn)行元素讀寫。 對空隊列而言，可假定 front和 rear的值為 1 21/36 假溢出 A B C front rear front rear (a) A?B?C入 隊 (b) A?B出隊 , D?E入 隊 (c)隊列假溢出 隊列假溢出示意圖 C D E front rear 隨著元素不斷入隊列、出隊列， rear和 front指針會不斷向后移動（如圖 (b)所示），最終會指向數(shù)組的最大下標(biāo)位置（如圖 (c)所示）。由于 rear和 front指針只能單方向移動，這時元素?zé)o法入隊列，但是隊列中仍有大量空閑位
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1