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

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

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

3、隊尾元素：elementsrear 隊首元素：elements (front+1) % maxSize 2022-2-1322循環(huán)隊列：滿隊列示意圖Queue012maxSize-1maxSize-2front 隊首指針rear 隊尾指針front=(rear+1) % maxSize本圖滿足上述隊滿條件。由圖可知：隊滿時隊首指針所指的單元不能利用，此時再入列會使隊列變成空隊列 ( front=rear )隊尾元素 elementsrear 隊首元素2022-2-1323循環(huán)隊列的類定義：2022-2-1324循環(huán)隊列入列操作算法：2022-2-13254.3.3 鏈隊列利用鏈式存貯結(jié)構(gòu)實現(xiàn)的

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

5、2-2-1335仿真算法思路：2022-2-1336仿真運行函數(shù)設(shè)計：2022-2-1337進門事件處理函數(shù)2022-2-1338e.serviceTime2022-2-1339服務(wù)完畢事件處理函數(shù)定義：2022-2-1340目標計算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