一、用链表实现队列，在元素入列和出列时为什么需要判断链表是否为空

结合《算法》这本书之前代码可知已初始化表尾，元素入列如果为空，则用表尾结点初始化表头结点；出列时，操作的是表头结点，当表中元素为空时，first节点中内容正确，last节点仍存有之前内容，需将其置为空。

链式队列

链式队列 ： 用链表形式实现的队列。链表结点为队列数据存储区，链表结点包括两部分数据存储区和指针存储区。

数据存储区 ：存放真实有效数据的区域。

指针存储区 ：存放下一个链表结点的地址。

注意：

1. 链式队列不存在队列已满的情况。在内存足够大的情况下，每次动态申请链表结点内存都会成功，即不会出现队列已满的情况，除非数据量超大内存不够。

2. 链式队列只存在队列为空的情况，在刚创建队列成功时队列为空，或者队列数据已全部出队，则此时队列为空。

3.在链式队列中头结点的数据域不存放有效数据，指针域存放名列前茅个有效数据域的结点地址，头结点的作用是方便对链式队列的操作。

延伸阅读：

二、链式队列数据出队

1.只有在链式队列非空时出队数据才有效。

2.若只有一个有效结点时，需将队尾指针指向头结点，头结点指针域为空。

3.头结点指针指向下下个有效结点。

4.结点数据出队。

5.释放出队结点数据内存。

如下图所示：

//链式队列数据出队

void OutLinkQueue(pLinkQueue queue, int * value)

{

    pNode queNode = 0;//队列结点指针

    if (IsEmptyLinkQueue(queue))

    {

       printf(“链式队列为空，出队失败……\r\n”);

       *value = 0;

       return;

    }

    if (queue->qFront->pNext == queue->qRear)//只有一个有效结点

       queue->qRear = queue->qFront;//队尾指针等于队首指针

    queNode = queue->qFront->pNext;//结点指针指向队首有效结点

    queue->qFront->pNext = queNode->pNext;//队首结点指针指向下个结点

    *value = queNode->dat;//出队结点值

    free(queNode);//释放内存

    printf(“出队成功！出队值:%d  —->  “, *value);

    printf(“队首结点指针:0x%08X    队尾指针:0x%08X\r\n”, queue->qFront->pNext, queue->qRear);

}

上一篇

堆内存和数据结构堆之间的关系是什么?

下一篇

oa系统怎么注册?