3.4.6 链式队列

顺序队列插入和删除操作需要大量移动元素，这样就会严重影响算法的效率，为了避免以上问题，可以采用链式存储结构表示队列。采用链式存储的队列被称为链式队列或链队列。

1.链式队列

一个链式队列通常用链表实现。同时，使用两个指针分别指示链表中存放的第一个元素和最后一个元素的位置。其中指向第一个元素的指针被称为队头指针front，指向最后一个元素的指针被称为队尾指针rear。链式队列的表示如图3.33所示。

有时，为了操作上的方便，在链式队列的第一个结点之前添加一个头结点，并让队头指针指向头结点。其中，头结点的数据域可以存放队列元素的个数信息，指针域指向链式队列的第一个结点。带头结点的链式队列如图3.34所示。

在带头结点的链式队列中，当队列为空时，队头指针front和队尾指针rear都指向头结点。如图3.35所示。

在链式队列中，最基本的操作是插入和删除操作。链式队列的插入和删除操作只需要移动队头指针和队尾指针，图3.36表示在队列中插入元素a的情况，图3.37表示队列中插入了元素a，b，c之后的情况，图3.38表示元素a出队的情况。

链式队列的类型描述如下：

2.链式循环队列

链式队列也可以构成循环队列，如图3.39所示。在这种链式循环队列中，可以只设置队尾指针，在这种情况下，队列LQ为空的判断条件为LQ.rear->next==LQ.rear，队空情况如图3.40所示。