文章目錄

• • • • 1 循環(huán)隊列定義
      • 2 循環(huán)隊列基本操作
      • 3 循環(huán)隊列代碼實現(xiàn)
      • 4 補充

1 循環(huán)隊列定義

循環(huán)隊列：即順序存儲的隊列，是為了避免“假溢出”而利用%運算符將隊列首尾相接連成一個環(huán)狀的隊列，稱為循環(huán)隊列。

引入循環(huán)隊列克服順序隊列中存在的“假上溢”現(xiàn)象。

假上溢：

因為在入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠(yuǎn)無法重新利用。因此，盡管隊列中實際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現(xiàn)象稱為“假上溢”。
簡而言之就是數(shù)組中有空位置卻不能再做入隊，出隊操作

2 循環(huán)隊列基本操作

隊空與隊滿
為什么要分析隊空隊滿的條件？

循環(huán)隊列是順序存儲的隊列，而順序隊列在做入隊時要先判斷隊列是否已滿，即是否已經(jīng)用完預(yù)分配的空間，出隊時要判斷隊列是否已空。

約定：

front指向隊列中實際頭元素的位置
rear 指向隊列中實際尾元素的后一位置

入隊

rear=（rear+1）%MAXSIZE queue[rear]=x

出隊

front=（front+1）%MAXSIZE x=queue[front]

隊空：front==rear

隊滿：front==(rear+1)% MAXSIZE

3 循環(huán)隊列代碼實現(xiàn)

#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAXSZIE (20)typedef int ElementType; typedef struct SqQueue {ElementType data[MAXSZIE];int front;int rear; } *Queue;Queue InitQueue(void) {Queue Q = (Queue)malloc(sizeof(struct SqQueue));Q->front = 0;Q->rear = 0;return Q; }int IsEmpty(Queue Q) {return Q->front == Q->rear; }int IsFull(Queue Q) {return (Q->rear + 1) % MAXSZIE == Q->front; }void EnQueue(Queue Q, ElementType e) {if (IsFull(Q)) {return;}Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAXSZIE; }void DeQueue(Queue Q, ElementType *e) {if (IsEmpty(Q)) {return;}*e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXSZIE; }int main(void) {ElementType e;Queue Q = InitQueue();srand((unsigned)time(NULL));for (int i = 0; i < 10; i++) {e = rand() % 100;EnQueue(Q, e);}while (!IsEmpty(Q)) {DeQueue(Q, &e);printf("%d ", e);} }

4 補充

為什么要設(shè)計堆棧？它有什么獨特用途？

① 調(diào)用函數(shù)或子程序非它莫屬；
② 遞歸運算的有力工具；
③ 用于保護現(xiàn)場和恢復(fù)現(xiàn)場；
④ 簡化了程序設(shè)計的問題。

為什么要設(shè)計隊列？它有什么獨特用途？

① 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU芯片中的指令譯碼隊列）；
② 操作系統(tǒng)中的作業(yè)調(diào)度（一個CPU執(zhí)行多個作業(yè)）；
③ 簡化程序設(shè)計。

什么叫“假溢出” ？如何解決？

答：在順序隊中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。
解決假溢出的途徑———采用循環(huán)隊列。

線性表、棧、隊的異同點：

相同點：

邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運算加以限制）。

不同點：

① 運算規(guī)則不同：線性表為隨機存取；
而棧是只允許在一端進行插入和刪除運算，因而是后進先出表LIFO；
隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。
② 用途不同：線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計等；隊列用于離散事件模擬、OS作業(yè)調(diào)度和簡化設(shè)計等。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的循环队列的介绍与实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。