棧和隊(duì)列--清華大學(xué)課程講義-數(shù)據(jù)結(jié)構(gòu)(PPT)

1、2022-2-131第四章 棧和隊(duì)列en-1e0e1en-2進(jìn)棧（Push） 出棧（Pop）棧頂 top棧底 2022-2-132棧的基本操作： （參見P104）2022-2-1334.1.1 順序棧在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)的棧2022-2-134順序棧的基本操作（算法）2022-2-1352022-2-1364.1.3 鏈棧利用鏈?zhǔn)酱尜A結(jié)構(gòu)實(shí)現(xiàn)的棧top棧頂元素 棧底元素2022-2-137鏈棧的定義：datalink鏈棧結(jié)點(diǎn)結(jié)構(gòu)2022-2-138鏈棧類的定義：2022-2-139鏈棧的入棧算法： top 原棧頂新棧頂item(1)(2)2022-2-1310比較與思考：2022-2-1311

2、棧應(yīng)用舉例迷宮問題入口(i,j)出口 墻通道2022-2-13122022-2-1313( i , j )東南西北2022-2-1314011001102022-2-13152022-2-13162022-2-1317作業(yè)：2022-2-13184.3 隊(duì)列e0e1 en-2en-12022-2-1319隊(duì)列的基本操作2022-2-1320隊(duì)列的順序存儲結(jié)構(gòu)循環(huán)隊(duì)列（環(huán)型隊(duì)列）2022-2-1321循環(huán)隊(duì)列：逆時(shí)針運(yùn)行示意圖Queue012maxSize-1maxSize-2front隊(duì)首指針rear隊(duì)尾指針規(guī)定：隊(duì)空：front=rear隊(duì)滿：front=(rear+1) % maxSize

3、隊(duì)尾元素：elementsrear 隊(duì)首元素：elements (front+1) % maxSize 2022-2-1322循環(huán)隊(duì)列：滿隊(duì)列示意圖Queue012maxSize-1maxSize-2front 隊(duì)首指針rear 隊(duì)尾指針front=(rear+1) % maxSize本圖滿足上述隊(duì)滿條件。由圖可知：隊(duì)滿時(shí)隊(duì)首指針?biāo)傅膯卧荒芾?，此時(shí)再入列會使隊(duì)列變成空隊(duì)列 ( front=rear )隊(duì)尾元素 elementsrear 隊(duì)首元素2022-2-1323循環(huán)隊(duì)列的類定義：2022-2-1324循環(huán)隊(duì)列入列操作算法：2022-2-13254.3.3 鏈隊(duì)列利用鏈?zhǔn)酱尜A結(jié)構(gòu)實(shí)現(xiàn)的

4、隊(duì)列front隊(duì)首指針 隊(duì)首 隊(duì)尾 rear隊(duì)尾指針2022-2-1326鏈隊(duì)列的類定義2022-2-1327鏈隊(duì)列類的成員函數(shù)：2022-2-1328鏈隊(duì)列成員函數(shù)定義：front rear p front ( 1 )( 2 )2022-2-1329置空隊(duì)列操作： rear rearp(1)(2)原隊(duì)尾 新隊(duì)尾item2022-2-1330鏈隊(duì)列出列操作：front p front(1)(2)2022-2-13314.5 事件驅(qū)動(dòng)模擬（ Event-Driven Simulation ）2022-2-1332仿真模型：2022-2-1333事件分析：2022-2-1334數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：202

5、2-2-1335仿真算法思路：2022-2-1336仿真運(yùn)行函數(shù)設(shè)計(jì)：2022-2-1337進(jìn)門事件處理函數(shù)2022-2-1338e.serviceTime2022-2-1339服務(wù)完畢事件處理函數(shù)定義：2022-2-1340目標(biāo)計(jì)算2022-2-1341主程序2022-2-13422022-2-13432022-2-13442022-2-13452022-2-13462022-2-13472022-2-13482022-2-13492022-2-13502022-2-13512022-2-13522022-2-13532022-2-13542022-2-13552022-2-13562022-2-13572022-2-13582022-2-1