实现链式存储结构的队列

一、何为链式存储结构的队列

即使用单链表来实现队列，可以通过带头结点的单链表实现队列，也可以通过不带头结点的单链表实现队列。

二、实现链式存储结构的队列(带头结点的版本)

Queue.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>// 实现链式存储结构的队列(带头结点的版本)// 定义结点的结构，结点用于存储队列中的元素typedefintElemType;typedefstructLinkNode{ElemType data;structLinkNode*next;}LinkNode;// 定义队列的结构typedefstructLinkQueue{LinkNode*front;// 指向头结点的指针，千万注意，不是指向队头元素的指针LinkNode*rear;// 指向队尾元素的指针}LinkQueue;// 队列的初始化voidInitQueue(LinkQueue&Q);// 队列是否为空。若为空返回true，否则返回falseboolIsEmpty(LinkQueue Q);// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueue&Q,ElemType x);// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueue&Q,ElemType&x);

Queue.cpp

#define_CRT_SECURE_NO_WARNINGS1#include"Queue.h"// 队列的初始化voidInitQueue(LinkQueue&Q){// 先申请一个头结点的空间// 初始化时，指向头结点的指针与指向队尾元素的指针均指向头结点Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next=NULL;// 头结点中的next指针置为NULL}// 队列是否为空。若为空返回true，否则返回falseboolIsEmpty(LinkQueue Q){if(Q.front==Q.rear)// 队列为空的条件既可以是Q.front == Q.rear，也可以是Q.front->next == NULLreturntrue;elsereturnfalse;}// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueue&Q,ElemType x){// 新元素x入队前，先申请一个结点的空间，用于存储新元素LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));// s指向新结点s->data=x;s->next=NULL;Q.rear->next=s;Q.rear=s;// 不要忘了让rear指针指向新的队尾元素}// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueue&Q,ElemType&x){if(Q.front==Q.rear)// 若队列为空，则无法执行出队操作returnfalse;LinkNode*p=Q.front->next;// p指向待出队的元素Q.front->next=p->next;if(p==Q.rear)// 注意，如果待出队的元素是队尾的元素，则需要修改队尾指针的值Q.rear=Q.front;free(p);// 回收待出队元素的空间p=NULL;returntrue;}

Test.cpp

#define_CRT_SECURE_NO_WARNINGS1#include"Queue.h"voidtest(){// 创建一个队列LinkQueue q;// 测试队列的初始化InitQueue(q);}intmain(){test();return0;}

三、实现链式存储结构的队列(不带头结点的版本)

Queue.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>// 实现链式存储结构的队列(不带头结点的版本)// 定义结点的结构，结点用于存储队列中的元素typedefintElemType;typedefstructLinkNode{ElemType data;structLinkNode*next;}LinkNode;// 定义队列的结构typedefstructLinkQueue{LinkNode*front;// 指向队头元素的指针LinkNode*rear;// 指向队尾元素的指针}LinkQueue;// 队列的初始化voidInitQueue(LinkQueue&Q);// 队列是否为空。若为空返回true，否则返回falseboolIsEmpty(LinkQueue Q);// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueue&Q,ElemType x);// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueue&Q,ElemType&x);

Queue.cpp

#define_CRT_SECURE_NO_WARNINGS1#include"Queue.h"// 队列的初始化voidInitQueue(LinkQueue&Q){Q.front=Q.rear=NULL;}// 队列是否为空。若为空返回true，否则返回falseboolIsEmpty(LinkQueue Q){if(Q.front==NULL)// 队列为空的条件是Q.front == NULLreturntrue;elsereturnfalse;}// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueue&Q,ElemType x){// 新元素x入队前，先申请一个结点的空间，用于存储新元素LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));// s指向新结点s->data=x;s->next=NULL;if(Q.front==NULL)// 若队列为空，则指向队头元素的指针和指向队尾元素的指针均指向新元素{Q.front=Q.rear=s;}else// 队列不为空{Q.rear->next=s;Q.rear=s;// 不要忘了让rear指针指向新的队尾元素}}// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueue&Q,ElemType&x){if(Q.front==NULL)// 若队列为空，则无法执行出队操作returnfalse;x=Q.front->data;// 将待出队的元素的值赋给变量xif(Q.front->next==NULL)// 若队列中只有一个有效数据。则出队时需要修改队头元素的指针和指向队尾元素的指针的值{free(Q.front);Q.front=Q.rear=NULL;}else// 队列中有效数据的个数大于1{LinkNode*p=Q.front->next;// p指向第二个存储有效数据的结点free(Q.front);Q.front=p;// 不要忘记让指向队头元素的指针指向新的队头元素}returntrue;}

Test.cpp

#define_CRT_SECURE_NO_WARNINGS1#include"Queue.h"voidtest(){// 创建一个队列LinkQueue q;// 测试队列的初始化InitQueue(q);}intmain(){test();return0;}