【大话数据结构C语言】17 链式队列及其C语言实现

系列文章参考资料为《大话数据结构》，源码为个人私有，未经允许不得转载 技术交流群或资料添加微信号：CoderAllen，回复关键字即可

从上一篇可以知道，单是顺序存储，若不是循环队列，算法的时间性能是不高的，单是循环链表有面临数组可能会溢出的问题，就引出了链式队列

队列的链式存储结构，其实就是线性表的单链表， 只不过它只能尾进头出而已，叫做链队列

为了方便，将队头指针指向链队列的头结点，而队尾指针指向终端结点

空队列的时候，front和rear都指向头结点

链队列的结构为：

typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

typedef struct QNode    /* 结点结构 */
{
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct          /* 队列的链表结构 */
{
   QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

入队操作：入队操作，其实就是在链表的尾部插入结点

其代码如下：

/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q,QElemType e)
{ 
    QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    if(!s) /* 存储分配失败 */
        exit(OVERFLOW);
    s->data=e;
    s->next=NULL;
    Q->rear->next=s;    /* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
    Q->rear=s;      /* 把当前的s设置为队尾结点，rear指向s，见图中② */
    return OK;
}

对应的出队操作： 出队操作，就是头结点的后继结点出队，将头结点的后继改为它后边的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点

其代码如下：

/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{
    QueuePtr p;
    if(Q->front==Q->rear)
        return ERROR;
    p=Q->front->next;       /* 将欲删除的队头结点暂存给p，见图中① */
    *e=p->data;             /* 将欲删除的队头结点的值赋值给e */
    Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
    if(Q->rear==p)      /* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
        Q->rear=Q->front;
    free(p);
    return OK;
}