3.3.2 队列的存储表示和操作的实现

　一、链队列
　　链队列是队列的链式存储结构，其结构示意图如下所示：

　
　		  
　　和线性表类似，队列也有两种存储表示方法。

　　从结构图可见，链队列和单链表一样，也附加一个头结点，链表中的指针方向也和线性表一致，链队列中设有两个指针，其一为"队尾指针(Q.rear)"，指向链队列中的队尾元素结点，其二为"队头指针(Q.front)"，指向链表的头结点，这表明真正的队头元素并非在"队头指针"所指的结点中，而在队头指针所指结点的"后继"结点中。
　　"空队列"中只含一个其指针域为空的头结点，并且头、尾指针都指向头结点而不为空。
　		  
  链队列的类型定义：
// 结构定义
　typedef SLink QueuePtr; // 链队列的结点结构和单链表相同
　typedef struct{
　　QueuePtr front;// 队列的头指针
　　QueuePtr rear; // 队列的尾指针
　　int length;　 // 队列元素个数
　} Queue;　 　　　// 链队列
　		   　　
　
　
　
　
　　和链栈类似，在链队列类型的定义中设置"元素个数"的成员目的为便于求得链表长度。 		 
  // 基本操作接口（函数声明）
　void InitQueue (Queue &Q);
　//　构造一个空队列 Q

　void DestroyQueue (Queue &Q);
　//　销毁队列Q，Q 不再存在

　void ClearQueue (Queue &Q);
　//　将 Q 置为空队列

　bool QueueEmpty (Queue Q);
　//　若队列 Q 为空队列，则返回TRUE，否则返回FALSE

　int QueueLength (Queue Q);
　//　返回队列 Q 中元素个数，即队列的长度

　bool GetHead (Queue Q, ElemType &e);
　//　若队列不空，则用 e 返回Q的队列头元素，并返回TRUE；否则返回FALSE

　void EnQueue (Queue &Q, ElemType e);
　//　在当前队列的尾元素之后插入元素 e 为新的队列尾元素

　bool DeQueue (Queue &Q, ElemType &e);
　//　若队列不空，则删除当前队列Q中的头元素，用 e 返回其值，并返回TRUE；
　//　否则返回 FALSE

　void QueueTraverse(Queue Q, void (*visit(ElemType ))
　//　依次对Q的每个元素调用函数visit( )，一旦visit( )失败，则操作失败。 		 

　　学习了第二章之后，相信你对链表的操作都已经很熟悉了。不难写出链队列的这些操作的定义，下页中我们将列出其中三个主要操作的定义。