順序隊列

順序隊列

順序隊列
 （）順序隊列的定義
 　 隊列的順序存儲結構稱為順序隊列順序隊列實際上是運算受限的順序表

（） 順序隊列的表示
　　①和順序表一樣順序隊列用一個向量空間來存放當前隊列中的元素
　　②由於隊列的隊頭和隊尾的位置是變化的設置兩個指針front和rear分別指示隊頭元素和隊尾元素在向量空間中的位置它們的初值在隊列初始化時均應置為
  
（） 順序隊列的基本操作
　　①入隊時將新元素插入rear所指的位置然後將rear加
　　②出隊時刪去front所指的元素然後將front加並返回被刪元素
  注意
　　　①當頭尾指針相等時隊列為空
　　　②在非空隊列裡隊頭指針始終指向隊頭元素尾指針始終指向隊尾元素的下一位置
　　　順序隊列基本操作【參見動畫演示】

（）順序隊列中的溢出現象
　　① 下溢現象
    　當隊列為空時做出隊運算產生的溢出現象下溢是正常現象常用作程序控制轉移的條件
　　② 真上溢現象
    　當隊列滿時做進棧運算產生空間溢出的現象真上溢是一種出錯狀態應設法避免
　　③ 假上溢現象
　　由於入隊和出隊操作中頭尾指針只增加不減小致使被刪元素的空間永遠無法重新利用當隊列中實際的元素個數遠遠小於向量空間的規模時也可能由於尾指針已超越向量空間的上界而不能做入隊操作該現象稱為假上溢現象
　【例】假設下述操作序列作用在初始為空的順序隊列上
          EnQueueDeQueueEnQueueDeQueue…
　　盡管在任何時刻隊列元素的個數均不超過但是只要該序列足夠長事先定義的向量空間無論多大均會產生指針越界錯誤

循環隊列
　　為充分利用向量空間克服假上溢現象的方法是將向量空間想象為一個首尾相接的圓環並稱這種向量為循環向量存儲在其中的隊列稱為循環隊列（Circular Queue）
    

（） 循環隊列的基本操作
　　循環隊列中進行出隊入隊操作時頭尾指針仍要加朝前移動只不過當頭尾指針指向向量上界（QueueSize）時其加操作的結果是指向向量的下界這種循環意義下的加操作可以描述為
① 方法一
    if(i+==QueueSize) //i表示front或rear
        i=;
    else
        i++;
② 方法二利用模運算
    i=(i+)%QueueSize

（） 循環隊列邊界條件處理
　　循環隊列中由於入隊時尾指針向前追趕頭指針出隊時頭指針向前追趕尾指針造成隊空和隊滿時頭尾指針均相等因此無法通過條件front==rear來判別隊列是空還是滿 【參見動畫演示】
　　解決這個問題的方法至少有三種
　　① 另設一布爾變量以區別隊列的空和滿
　　② 少用一個元素的空間約定入隊前測試尾指針在循環意義下加後是否等於頭指針若相等則認為隊滿（注意rear所指的單元始終為空）
　　③使用一個計數器記錄隊列中元素的總數（即隊列長度）

（） 循環隊列的類型定義
     #define Queur Size    //應根據具體情況定義該值
     typedef char Queue DataType;  //DataType的類型依賴於具體的應用
     typedef Sturet{               //頭指針隊非空時指向隊頭元素
           int front;              //尾指針隊非空時指向隊尾元素的下一位置
           int rear;               //計數器記錄隊中元素總數
           DataType data[QueueSize]
     }CirQueue;

（） 循環隊列的基本運算
　　用第三種方法循環隊列的六種基本運算
　① 置隊空
      void InitQueue(CirQueue *Q)
      {
              Q>front=Q>rear=;
              Q>count=;     //計數器置
       }

　② 判隊空
       int QueueEmpty(CirQueue *Q)
       {
            return Q>count==;  //隊列無元素為空
        }
　③ 判隊滿
int QueueFull(CirQueue *Q)
        {
            return Q>count==QueueSize;  //隊中元素個數等於QueueSize時隊滿
         }
　④ 入隊
void EnQueue(CirQueuq *QDataType x)
         {
            if(QueueFull((Q))                  
                   Error(Queue overflow);     //隊滿上溢
            Q>count ++;                        //隊列元素個數加
            Q>data[Q>rear]=x;                 //新元素插入隊尾
            Q>rear=(Q>rear+)%QueueSize;      //循環意義下將尾指針加
　⑤ 出隊
DataType DeQueue(CirQueue *Q)
          {
              DataType temp;
              if(QueueEmpty((Q))
                   Error(Queue underflow);     //隊空下溢
              temp=Q>data[Q>front];
              Q>count;                        //隊列元素個數減
              Q>front=(Q>front+)&QueueSize;   //循環意義下的頭指針加
              return temp;
           }            
　⑥取隊頭元素
DataType QueueFront(CirQueue *Q)
            {
                if(QueueEmpty(Q))
                    Error(Queue if empty);
                return Q>data[Q>front];
          &nbs
From:http://tw.wingwit.com/Article/program/sjjg/201311/22688.html