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

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

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

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

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

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