链队列

链队列的实质就是只限制在表头做添加，表尾做删除的单链表

一 链队列示意图

注：增加指向链表的队尾指针，便于在表尾做插入操作；其中Q为LinkQueue型的指针。

二 链队列基本运算

[cpp] view plain copy

1. //置空队  
2.      void InitQueue(LinkQueue *Q)  
3.      {  
4.            Q->front=Q->rear=NULL;  
5.      }  

[cpp] view plain copy

1. //判队空  
2.      intQueueEmpty(LinkQueue *Q)  
3.      {  
4.            return Q->front==NULL&&Q->rear==Null;  
5.            //实际上只须判断队头指针是否为空即可  
6.      }  

[cpp] view plain copy

1. //入队  
2. void EnQueue(LinkQueue *Q,DataType x)  
3. {  
4.     QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));//申请新节点  
5.     p->data = x;  
6.     p->next = NULL;  
7.     if(QueueEmpty(Q))  
8.         Q->front = Q->rear = p;//将x插入到空队列  
9.     else  
10.     {  
11.         //x插入到非空队列的尾  
12.         Q->rear->next = p;//*p链到原队尾节点后  
13.         Q->rear = p;//队尾指针指向性的队尾  
14.     }  
15. }  

[cpp] view plain copy

1. //出队  
2. DataType DeQueue(LinkQueue *Q)  
3. {  
4.     DataType x;  
5.     QueueNode *p;  
6.     if(QueueEmpty(Q))  
7.         Error("Queue undefflow");//下溢  
8.     p = Q->front;//指向对头结点  
9.     x = p->data;//保存头结点的数据  
10.     Q->front = p->next;//将对头从节点上摘下来  
11.     if(Q->rear=p)//原队中只有一个节点，删去后队列变空此时的头指针已为空  
12.         Q->rear = NULL;  
13.     free(p);  
14.     return x;  
15.   
16. }  

转载：http://blog.csdn.net/xsf50717/article/details/39938553