栈与队列 Part 7

队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列

为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点，如图所示。

空队列时，front和rear都指向头结点，如图所示。

链队列的结构为：

    typedef int QElemType;  /* QElemType类型根据实际情况而定，这里假设为int */typedef struct QNode    /* 结点结构 */{QElemType data;struct QNode *next;}QNode,*QueuePtr;typedef struct           /* 队列的链表结构 */{QueuePtr front,rear; /* 队头、队尾指针 */}LinkQueue;

队列的链式存储结构—入队操作

入队操作时，其实就是在链表尾部插入结点，如图所示。

其代码如下：

队列的链式存储结构—出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点，如图所示。

代码如下：

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

---

总结回顾

又到了总结回顾的时间。我们这一章讲的是栈和队列，它们都是特殊的线性表，只不过对插入和删除操作做了限制。

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

它们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。因此它们各自有各自的技巧来解决这个问题。

对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。

对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是O(n)的时间复杂度变成了O(1)。

它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同如图所示。