chapter3：棧、隊(duì)列-wenkub.com
2024-09-25 21:59 本頁(yè)面
【正文】 ? =(+1)%MaxQsize。 ? } ? Status DeQueue (SqQueue amp。Q,QElemType e){ ? if ((+1)%MaxQsize= = ) reture Error。 ? if (!) exit(Overflow)。 ? int rear。在這種情況下，隊(duì)空與隊(duì)滿的條件分別為：隊(duì)空：尾指示器等于頭指示器；隊(duì)滿：尾指示器前進(jìn)一步后（即按模 QueneSize加 1后）與頭指示器相等 Circular Array ? E F D ? ? 1 2 4 5 6 3 ? ? ? D F E rear = 6 ? 1 entry front = 4 1 4 2 5 6 3 G entry If we view the array as a circle, the cell after the 6th cell is the 1st cell. What is a circular array? To implement queue, it is best to view arrays as circular structure. front rear A B C D E F G 0 1 7 8 9 2 3 4 5 6 0 1 7 8 9 2 3 4 5 6 A B C D E F G front rear Circular view of arrays. Checking for Full/Empty Queue rear front c d e rear front Need to distinguish between full and empty cases: Empty case : rear=front Full Case : (rear+1) MOD QueueSize=front Deliberate of one gap. Why?) c d e rear front Reason: f possible confusion with the empty case. 進(jìn)隊(duì)： (rear ++) MOD QueueSize ； //按模加 room[rear]=x。另一種方法是，對(duì)頭尾指針加 1后是否大于（ QueneSize1）， 若是則置其為 0。 Array implementation, 1st trial A B C D ? E rear = 5 entry front = 1 A B C D E ? ? ? D F E rear = 6 entry front = 4 D E F G We cannot enqueue ‘G’ because the rear has reached the end of the array. deQ A,B,C, then enQ F and G.. 循環(huán)隊(duì)列 所謂循環(huán)隊(duì)列，就是指將隊(duì)列的存貯區(qū)域作循環(huán)結(jié)構(gòu)處理，隊(duì)列的頭尾指針的移動(dòng)均可回繞，將存貯區(qū)的第 1個(gè)元素視為最后一個(gè)元素的后繼， （同樣將最后元素視為第 1個(gè)元素的前趨），按這種方式處理的隊(duì)列，稱為循環(huán)隊(duì)列。這是一個(gè)十分嚴(yán)重的問(wèn)題，若不解決，無(wú)論分配多大的空間，也不能保證不發(fā)生溢出。 ? 隊(duì)滿： rear= QueueSize 1。 進(jìn)隊(duì)操作要修改尾指針，而出隊(duì)操作修改指針、使它們向后繼方向移動(dòng)。 這里 front與 rear分別為隊(duì)頭和隊(duì)尾指示器。 ? free(p)。 ? p=next。 ? return OK。 ? pdata=e。 ? } ? return OK。} ? Status Destroyqueue(LinkQueue amp。Q) { ? //構(gòu)造一個(gè)空隊(duì)列 Q ? ==(QueuePtr)malloc(sizeof(QNode))。Q,QElemType e) ? //隊(duì)列 Q存在 ,插入元素 e為 Q的隊(duì)尾元素 ? Status DeQueue(LinkQueue amp。Q) ? //構(gòu)造一個(gè)空隊(duì)列 Q ? Status Destroyqueue(LinkQueue amp。 ? typedef struct{ ? QueuePtr front。一個(gè)鏈隊(duì)列顯然需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。Q,e) 隊(duì)列 Q存在 ,插入元素 e為 Q的隊(duì)尾元素 ? DeQueue(amp。Q) 構(gòu)造一個(gè)空隊(duì)列 Q ? Destroyqueue(amp。隊(duì)是一種先進(jìn)先出（ FIFO） 的結(jié)構(gòu)，元素出隊(duì)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1