棧和隊(duì)列-隊(duì)列的表示與實(shí)現(xiàn)

1、3.2 棧的應(yīng)用舉例例1：括號(hào)匹配的檢驗(yàn)假設(shè)一個(gè)算法表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類型的括號(hào)，編寫(xiě)一個(gè)判別表達(dá)式中括號(hào)是否正確配對(duì)的函數(shù)。 設(shè)計(jì)思路：用棧暫存左括號(hào)1void ExpIsCorrect(char exp, int n)/判斷有n個(gè)字符的字符串exp左右括號(hào)是否配對(duì)正確 SeqStack myStack; int i;char c; StackInitiate(&myStack); for(i=0;i0 & rear=front 判隊(duì)空：count=0加設(shè)標(biāo)志位，出隊(duì)時(shí)置,入隊(duì)時(shí)置,則可識(shí)別當(dāng)前front=rear屬于何種情況判隊(duì)滿：tag=1 & rear=front

2、判隊(duì)空：tag=0 & rear=front 少用一個(gè)存儲(chǔ)單元判隊(duì)滿： front=(rear+1)%MaxQueueSize 判隊(duì)空： rear=front13例： 一循環(huán)隊(duì)列如下圖所示，若先刪除4個(gè)元素，接著再插入4個(gè)元素，請(qǐng)問(wèn)隊(duì)頭和隊(duì)尾指針?lè)謩e指向哪個(gè)位置? J2 J3J1 J4 J5front=1rear=0解：由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=1和rear=0。刪除4個(gè)元素后front=5；再插入4個(gè)元素后，r=(0+4)%6=4 front=5J6 J5J7J8 J9rear=4rear=0front=514、順序循環(huán)隊(duì)列的實(shí)現(xiàn)采用對(duì)順序循環(huán)隊(duì)列的分析，其結(jié)構(gòu)體定義為

3、：typedef structDataType queueMaxQueueSize;int rear;/*隊(duì)尾指針*/int front;/*隊(duì)頭指針*/int count;/*計(jì)數(shù)器*/ SeqCQueue; 15討論：循環(huán)隊(duì)列的基本操作如何實(shí)現(xiàn)？以建隊(duì)、入隊(duì)和出隊(duì)三種基本操作為例1）初始化一個(gè)順序循環(huán)隊(duì)列算法要求：生成一空隊(duì)列算法操作： 設(shè)置隊(duì)列為空隊(duì)列，其特征即： front=rear=0，count=016具體算法：void QueueInitiate(SeqCQueue *Q)/*初始化順序循環(huán)隊(duì)列Q*/ Q-rear = 0; /*定義初始隊(duì)尾指針下標(biāo)值*/ Q-front = 0

4、; /*定義初始隊(duì)頭指針下標(biāo)值*/ Q-count = 0; /*定義初始計(jì)數(shù)器值*/17算法說(shuō)明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素分 析：(1) 插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿？ if (Q-count0 & Q-rear=Q-front) return 0;(2）插入動(dòng)作 Q-queueQ-rear = x; Q-rear = (Q-rear + 1) % MaxQueueSize; Q-count+; return 1;2） 入隊(duì)操作隊(duì)列尺寸18int QueueAppend(SeqCQueue *Q, DataType x)if(Q-count 0 & Q-rear = Q-front)pri

5、ntf(隊(duì)列已滿無(wú)法插入! n);return 0;else Q-queueQ-rear = x;Q-rear = (Q-rear + 1) % MaxQueueSize;Q-count+;return 1;入隊(duì)操作完整算法193）出隊(duì)操作算法說(shuō)明：刪除隊(duì)頭元素，返回其值 e 分 析： （1） 在刪除前應(yīng)當(dāng)判斷隊(duì)列是否空？ if(Q-count = 0) return 0; （2）刪除動(dòng)作 m = Q-queueQ-front; Q-front = (Q-front + 1) % MaxQueueSize; Q-count-; front指針在元素出隊(duì)后再加20int QueueDelete(SeqCQueue *Q, DataType *d)if(Q-count = 0) printf(隊(duì)列已空無(wú)數(shù)據(jù)元素出隊(duì)列! n); return 0;else *d = Q-queueQ-front; Q-front = (Q-front + 1) % MaxQueueSize; Q-count-; return 1;出隊(duì)操作完整算法