队列的链式存储及其基本操作
队列的链式存储
队列的链式表示称为链队列,它实际上是一个同时带有队头指针和队尾指针的单链表。 头指针指向队头结点,尾指针指向队尾结点,即单链表的最后一个结点(注意与顺序存储的 不同)。队列的链式存储如图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; }