链队列

1、 链队列的定义
  　队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。

typedef struct queuenode{
                    DataType data
                    struct queuenode *next
                     }QueueNode ;
    
       typedef struct{
             QueueNode  *front,*rear;  //对头和队尾
       }LinkQueue;

3、 链队列的基本运算
（1） 置空队
      void InitQueue(LinkQueue *Q)
      {
            Q->front=Q->rear=NULL;
      }
（2） 判队空
      intQueueEmpty(LinkQueue *Q)
      {
            return Q->front==NULL&&Q->rear==Null;
            //实际上只须判断队头指针是否为空即可
      }

（3） 入队
       void EnQueue(LinkQueue *Q,DataType x)
       {//将元素x插入链队列尾部
             QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点
             p->data=x;  

             p->next=NULL;//将x放入节点中
             if(QueueEmpty(Q))
                 Q->front=Q->rear=p;  //将x插入空队列
             else { //x插入非空队列的尾
                 Q->rear->next=p;     //*p链到原队尾结点后
                 Q->rear=p;           //队尾指针指向新的尾
              }
        }

（4） 出队
      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;  //返回原队头数据
       }

（5） 取队头元素
       DataType QueueFront(LinkQueue *Q)
       {
             if(QueueEmpty(Q))
                  Error("Queue if empty.");
              return Q->front->data;
        }
   注意：
    　①和链栈类似，无须考虑判队满的运算及上溢。
    　②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。