队列的链式实现

队列的链式存储结构实际上就是线性表的单链表，在这个基础上面加了只能尾进头出的限制。为了操作方便设置了一个头结点，头结点里面没有保存数据元素，然后设置了两个指针，front指向队列里面的头结点，其实在入队和出队过程中，front始终指向头结点，并没有发生改变。另外一个指针式rear,它初始时指向头结点，然后每入队一个元素，先使rear->next指向加入的结点，然后使rean=newnode,rear是移动的，每次都指向最后一个结点，在出队时如果是最后一个结点的话，还需要额外的一步操作，是rear指向head,回复初始化时候的状态。

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct QNode
{

    ElemType data;
    struct QNode *next;

}QNode,*QNodePtr;
typedef struct{

  QNodePtr front,rear;
}LinkQueue;
void Init(LinkQueue **Q)
{
    *Q=(LinkQueue*)malloc(sizeof(LinkQueue));
     QNode *head=(QNode *)malloc(sizeof(QNode));//创建一个头结点
     (*Q)->front=head;//注意一定要使front和rear指向一个确定地址，你也可以单独为它们malloc
     (*Q)->rear=head;
}
int EnQueue(LinkQueue *Q,ElemType e)//入队
{

    QNode *node;
    node=(QNode *)malloc(sizeof(QNode));
    if(!node)
        return 0;
    node->data=e;
    node->next=NULL;
    Q->rear->next=node;
    Q->rear=node;
    return 1;
}
int DeQueue(LinkQueue *Q,ElemType *e)//出队
{

    if(Q->front==Q->rear)
        return 0;
    QNode *p;
    p=Q->front->next;
    *e=p->data;
    Q->front->next=p->next;
    if(Q->rear==p)//删除的是最后一个结点
        Q->rear=Q->front;
    free(p);
    return 1;
}
void Print(LinkQueue *Q)
{
    QNode *p=Q->front->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;

    }
}
int main()
{
    LinkQueue *Q;
   Init(&Q);
   for(int i=0;i<=9;i++)
    EnQueue(Q,i);
    int x;
    for(int i=0;i<=4;i++)
        DeQueue(Q,&x);
     Print(Q);

    return 0;
}

首先入队了0 1 2 3 4 5 6 7 8 9一共10个元素，然后出队了前5个，最后输出5 6 7 8 9这剩余的5个元素。