鏈隊列

鏈隊列

鏈隊列的定義
　　隊列的鏈式存儲結構簡稱為鏈隊列它是限制僅在表頭刪除和表尾插入的單鏈表

鏈隊列的結構類型說明

　注意
　　增加指向鏈表上的最後一個結點的尾指針便於在表尾做插入操作
　　鏈隊列示意圖見上圖圖中Q為LinkQueue型的指針

鏈隊列的基本運算
（） 置空隊
      void InitQueue(LinkQueue *Q)
      {
            Q>front=Q>rear=NULL;
      }
（） 判隊空
      intQueueEmpty(LinkQueue *Q)
      {
            return Q>front==NULL&&Q>rear==Null;
            //實際上只須判斷隊頭指針是否為空即可
      }

（） 入隊
       void EnQueue(LinkQueue *QDataType x)
       {//將元素x插入鏈隊列尾部
             QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申請新結點
             p>data=x;   p>next=NULL;
             if(QueueEmpty(Q))
                 Q>front=Q>rear=p;  //將x插入空隊列
             else { //x插入非空隊列的尾
                 Q>rear>next=p;     //*p鏈到原隊尾結點後
                 Q>rear=p;           //隊尾指針指向新的尾
              }
        }

（） 出隊
      DataType DeQueue (LinkQueue *Q)
      {
             DataType x;
             QueueNode *p;
             if(QueueEmpty(Q))
                  Error(Queue underflow);//下溢
             p=Q>front;                   //指向對頭結點
             x=p>data;                    //保存對頭結點的數據
             Q>front=p>next;             //將對頭結點從鏈上摘下
             if(Q>rear==p)//原隊中只有一個結點刪去後隊列變空此時隊頭指針已為空
                  Q>rear=NULL;
             free(p);   //釋放被刪隊頭結點
             return x;  //返回原隊頭數據
       }

（） 取隊頭元素
       DataType QueueFront(LinkQueue *Q)
       {
             if(QueueEmpty(Q))
                  Error(Queue if empty);
              return Q>front>data;
        }
　注意
　　①和鏈棧類似無須考慮判隊滿的運算及上溢
　　②在出隊算法中一般只需修改隊頭指針但當原隊中只有一個結點時該結點既是隊頭也是隊尾故刪去此結點時亦需修改尾指針且刪去此結點後隊列變空
　　③以上討論的是無頭結點鏈隊列的基本運算和單鏈表類似為了簡化邊界條件的處理在隊頭結點前也可附加一個頭結點增加頭結點的鏈隊列的基本運算【參見練習】
 

From:http://tw.wingwit.com/Article/program/sjjg/201311/22680.html