实现链式存储结构的队列

一、何为链式存储结构的队列即使用单链表来实现队列可以通过带头结点的单链表实现队列也可以通过不带头结点的单链表实现队列。二、实现链式存储结构的队列(带头结点的版本)Queue.h#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h// 实现链式存储结构的队列(带头结点的版本)// 定义结点的结构结点用于存储队列中的元素typedefintElemType;typedefstructLinkNode{ElemType data;structLinkNode*next;}LinkNode;// 定义队列的结构typedefstructLinkQueue{LinkNode*front;// 指向头结点的指针千万注意不是指向队头元素的指针LinkNode*rear;// 指向队尾元素的指针}LinkQueue;// 队列的初始化voidInitQueue(LinkQueueQ);// 队列是否为空。若为空返回true否则返回falseboolIsEmpty(LinkQueue Q);// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueueQ,ElemType x);// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueueQ,ElemTypex);Queue.cpp#define_CRT_SECURE_NO_WARNINGS1#includeQueue.h// 队列的初始化voidInitQueue(LinkQueueQ){// 先申请一个头结点的空间// 初始化时指向头结点的指针与指向队尾元素的指针均指向头结点Q.frontQ.rear(LinkNode*)malloc(sizeof(LinkNode));Q.front-nextNULL;// 头结点中的next指针置为NULL}// 队列是否为空。若为空返回true否则返回falseboolIsEmpty(LinkQueue Q){if(Q.frontQ.rear)// 队列为空的条件既可以是Q.front Q.rear也可以是Q.front-next NULLreturntrue;elsereturnfalse;}// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueueQ,ElemType x){// 新元素x入队前先申请一个结点的空间用于存储新元素LinkNode*s(LinkNode*)malloc(sizeof(LinkNode));// s指向新结点s-datax;s-nextNULL;Q.rear-nexts;Q.rears;// 不要忘了让rear指针指向新的队尾元素}// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueueQ,ElemTypex){if(Q.frontQ.rear)// 若队列为空则无法执行出队操作returnfalse;LinkNode*pQ.front-next;// p指向待出队的元素Q.front-nextp-next;if(pQ.rear)// 注意如果待出队的元素是队尾的元素则需要修改队尾指针的值Q.rearQ.front;free(p);// 回收待出队元素的空间pNULL;returntrue;}Test.cpp#define_CRT_SECURE_NO_WARNINGS1#includeQueue.hvoidtest(){// 创建一个队列LinkQueue q;// 测试队列的初始化InitQueue(q);}intmain(){test();return0;}三、实现链式存储结构的队列(不带头结点的版本)Queue.h#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h// 实现链式存储结构的队列(不带头结点的版本)// 定义结点的结构结点用于存储队列中的元素typedefintElemType;typedefstructLinkNode{ElemType data;structLinkNode*next;}LinkNode;// 定义队列的结构typedefstructLinkQueue{LinkNode*front;// 指向队头元素的指针LinkNode*rear;// 指向队尾元素的指针}LinkQueue;// 队列的初始化voidInitQueue(LinkQueueQ);// 队列是否为空。若为空返回true否则返回falseboolIsEmpty(LinkQueue Q);// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueueQ,ElemType x);// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueueQ,ElemTypex);Queue.cpp#define_CRT_SECURE_NO_WARNINGS1#includeQueue.h// 队列的初始化voidInitQueue(LinkQueueQ){Q.frontQ.rearNULL;}// 队列是否为空。若为空返回true否则返回falseboolIsEmpty(LinkQueue Q){if(Q.frontNULL)// 队列为空的条件是Q.front NULLreturntrue;elsereturnfalse;}// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueueQ,ElemType x){// 新元素x入队前先申请一个结点的空间用于存储新元素LinkNode*s(LinkNode*)malloc(sizeof(LinkNode));// s指向新结点s-datax;s-nextNULL;if(Q.frontNULL)// 若队列为空则指向队头元素的指针和指向队尾元素的指针均指向新元素{Q.frontQ.rears;}else// 队列不为空{Q.rear-nexts;Q.rears;// 不要忘了让rear指针指向新的队尾元素}}// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueueQ,ElemTypex){if(Q.frontNULL)// 若队列为空则无法执行出队操作returnfalse;xQ.front-data;// 将待出队的元素的值赋给变量xif(Q.front-nextNULL)// 若队列中只有一个有效数据。则出队时需要修改队头元素的指针和指向队尾元素的指针的值{free(Q.front);Q.frontQ.rearNULL;}else// 队列中有效数据的个数大于1{LinkNode*pQ.front-next;// p指向第二个存储有效数据的结点free(Q.front);Q.frontp;// 不要忘记让指向队头元素的指针指向新的队头元素}returntrue;}Test.cpp#define_CRT_SECURE_NO_WARNINGS1#includeQueue.hvoidtest(){// 创建一个队列LinkQueue q;// 测试队列的初始化InitQueue(q);}intmain(){test();return0;}