队列的链式存储及其基本操作

队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。 头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序存储的 不同）。队列的链式存储如图3-8所示。 

图3-8  不带头结点的链式队列

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

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

当Q.front==NULL且Q.rear==NULL时，链式队列为空。

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

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

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

图3-9  带头结点的链式队列

链式队列的基本操作

1) 初始化

void InitQueue(LinkQueue &Q){
    Q.front = Q.rear=(LinkNode*) malloc(sizeof(LinkNode));  //建立头结点
    Q.front->next=NULL;  //初始为空
}

2) 判队空

bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear) return true;
    else return false;
}

3) 入队

void EnQueue(LinkQueue &Q, ElemType x){
    s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x; s->next=NULL;  //创建新结点，插入到链尾
    Q.rear->next=s;
    Q.rear=s;
}

4) 出队

bool DeQueue(LinkQueue &Q, ElemType &x){
    if (Q.front == Q.rear) return false; //空队
    p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;  //若原队列中只有一个结点，删除后变空
    free(p);
    return true;
}