3.3.3　队列的链式存储结构及其基本运算的实现

链式存储的队列称为链队列。和链栈类似，用单链表来实现链队，根据队的FIFO原则，为了操作上的方便，我们分别需要一个头指针和尾指针，如图3－15所示。

图3－15 链队示意图

图3－15中头指针front和尾指针rear是两个独立的指针变量，从结构性上考虑，通常将二者封装在一个结构中。

链队的描述如下：

按这种思想建立的带头结点的链队如图3－16所示。

图3－16 头尾指针封装在一起的链队

链队列的基本运算与单链表相似，只是在操作上有特殊的地方，算法如下。

算法3.9 链队列的基本运算

顺序循环队列和链队列在算法实现上时间复杂度都是O（1）；在存储空间上，若之前固定了存储的长度，适合使用顺序循环队列；若长度不确定，适合使用链队列。