队列的链式存储结构

队列的链式存储

队列的链式表示称为链式队列，它实际上是一个同时有队首指针和队尾指针的单链表，如图所示。队首指针指向队头结点，队尾指针指向队尾结点，即单链表的最后一个结点。

队列的链式存储类型可描述为：

typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{ //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
} LinkQueue;

不带头结点时，当 Q.front==NULL 且 Q.rear==NULL 时，链式队列为空。

入队时，建立一个新结点，将新结点插入到链表的尾部，并让 Q.rear 指向这个新插入的结点（若原队列为空队，则令 Q.front 也指向该结点）。出队时，首先判断队是否为空，若不空，则取出队首元素，将其从链表中删除，并让 Q.front 指向下一个结点（若该结点为最后一个结点，则置 Q.front 和 Q.rear 都为 NULL）。

不难看出，不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了，如图所示。

用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和“溢出”的问题。

链式队列的基本操作

初始化

判队空

入队

出队