棧與隊列(編輯修改稿)
2024-10-07 10:12 本頁面
【文章內(nèi)容簡介】 3 ( + 1 +進棧 4 ( + 1 2 輸出 2 5 1 2 + +退棧輸出，退棧到（止 6 * 1 2 + *進棧 7 * ( 1 2 + （進棧 8 * ( ( 1 2 + （進棧 9 * ( ( 1 2 + 8 輸出 8 10 * ( ( 1 2 + 8 進棧 將中綴表達式 (1+2)*((82)/(74))變成等價的后綴表達式。 現(xiàn)在用棧來實現(xiàn)該運算，棧的變化及輸出結(jié)果如下： 11 * ( ( 1 2 + 8 2 輸出 2 12 * ( 1 2 + 8 2 退棧輸出，退棧到（止 13 * ( / 1 2 + 8 2 / 進棧 14 * ( / ( 1 2 + 8 2 （ 進棧 15 * ( / ( 1 2 + 8 2 7 輸出 7 16 * ( / ( 1 2 + 8 2 7 進棧 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 / * *退棧并輸出 隊列定義 隊列是只能在表的一端進行插入、在另一端進行刪除操作的線性表。允許刪除元素的一端稱為隊頭，允許插入元素的一端稱為隊尾。 顯然不論元素按何種順序進入隊列，也必然按這種順序出隊列，所以隊列又稱為先進先出（ FIFO）表。隊列有兩個活動端，所以設(shè)置了對頭和隊尾兩個位置指針。一般隊頭指針記作 front，隊尾指針記作 rear。 a b c front rear 入隊 出隊 隊列示意圖 循環(huán)隊列 — 隊列順序存儲 順序存儲的隊列中，每次出隊列的元素必定是隊頭元素，因此如果采取與普通順序表同樣的操作方式，則每次出隊操作必然將整個隊列向前移動，這使得效率大大降低。 因此 在順序存儲的隊列中，出隊和入隊操作都不移動元素而是移動指針。 為方便起見，這里規(guī)定隊頭指針 front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素所在位置。這樣，入隊和出隊操作的執(zhí)行步驟都是首先執(zhí)行指針移動，再進行元素讀寫。 對空隊列而言，可假定 front和 rear的值為 1 假溢出 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