[循環隊列]使用原因與注意事項

問題描述：循環隊列是一般隊列的變種吧，就是将隊列首尾相連了，貌似這樣就不必考慮隊列滿而無法使用了，因為到了隊列尾又會循環回到隊列首。在嵌入式底層代碼實作中，一些串行端口資料特别是序列槽，用到循環隊列的情況還是蠻多的。當然，這隻是一種資料結構，用在哪裡都得看具體用途和是否能帶來好處。為了更深一步的對這一結構的了解，進行了下整理和學習。

循環隊列：将向量空間想象為一個首尾相接的圓環，并稱這種向量為循環向量。存儲在其中的隊列稱為循環隊列（Circular Queue）。這個應當是比較成熟的定義了，簡潔了當。像是一條蛇咬住自己的尾巴，而且蛇腔裡面可以填充東西的感覺。

為什麼用循環隊列：主要是為了克服“假溢出”情況，

系統作為隊列用的存儲區還沒有滿,但隊列卻發生了溢出,我們把這種現象稱為"假溢出"。其實就是因為隊列的first in first out特質所引起的，隊列為獲得

first in first out特質，一般需要兩個指針，一個稱為“頭指針”，一個稱為“尾指針”，

頭指針用于在隊列頭部

讀出元素

，

尾指針用于在隊列尾部

插入新元素

，先進去隊列的元素位于隊列的頭部。對于使用順序隊列情況，随着隊列尾部不斷插入新元素，尾指針最終會指向配置設定給隊列的最後的記憶體位址，當再有新元素要插入時，此時隊列尾部已經無法插入新元素了。而頭指針由于有元素出隊列，隊列記憶體空間的前面一部分其實還是空的，是以就造成了“假溢出

”這種情況。循環隊列就是為解決該問題的。（當然，解決假溢出還可以将隊列元素做平移，但感覺使用循環隊列會有更高的效率）。

  循環隊列弊端：循環隊列空和滿時都是頭指針等于尾指針，是以對于隊列空和滿的判斷需要在代碼中加以差別，有三種方式：一是另設一布爾變量來差別隊列的空和滿。二是少用一個元素的空間,每次入隊前測試入隊後頭尾指針是否會重合，如果會重合就認為隊列已滿。三是設定一計數器記錄隊列中元素總數，不僅可判别空或滿，還可以得到隊列中元素的個數。

  循環隊列類型定義：

#define QueueSize 100 //應根據具體情況定義該值
  
 
  

    typedef char DataType; //DataType的類型依賴于具體的應用
  
 
  

    typedef struct{
  
 
  

   int front; //頭指針，隊非空時指向隊頭元素
  
 
  

   int rear; //尾指針，隊非空時指向隊尾元素的下一位置
  
 
  

   int count;//計數器，記錄隊中元素總數
  
 
  

    DataType data[QueueSize];
  
 
  

    }CirQueue;
  
 
 

 
 
 1. 隊列置空：
 
 
 void InitQueue(CirQueue *Q)
 
  

   {
  
 
  

   Q->front=Q->rear=0;
  
 
  

   Q->count=0; //計數器置0
  
 
  

   }
  
 
 
 2. 隊列判空：
 
 
 int QueueEmpty(CirQueue *Q)
 
  

   {
  
 
  

   return Q->count==0; //隊列無元素為空
  
 
  

   }
  
 
 
 3. 判斷隊列是否滿：
 
 
 int QueueFull(CirQueue *Q)
 
  

   {
  
 
  

   return Q->count==QueueSize; //隊中元素個數等于QueueSize時隊滿
  
 
  

   }
  
 
 
 4. 元素隊列尾部入隊：
 
 
 void EnQueue(CirQueue *Q,DataType x)
 
  

   {
  
 
  

   if(QueueFull(Q))
  
 
  

   Error("Queue overflow"); //隊滿上溢
  
 
  

   Q->count ++; //隊列元素個數加1
  
 
  

   Q->data[Q->rear]=x; //新元素插入隊尾
  
 
  

   Q->rear=(Q->rear+1)%QueueSize; //循環意義下将尾指針加1
  
 
  

   }
  
 
 
 5. 元素從隊列頭部出隊列：
 
 
 DataType DeQueue(CirQueue *Q)
 
  

   {
  
 
  

   DataType temp;
  
 
  

   if(QueueEmpty(Q))
  
 
  

   Error("Queue underflow"); //隊空下溢
  
 
  

   temp=Q->data[Q->front];
  
 
  

   Q->count--; //隊列元素個數減1
  
 
  

   Q->front=(Q->front+1)%QueueSize; //循環意義下的頭指針加1
  
 
  

   return temp;
  
 
  

   }