数据结构（C语言）代码实现（十）—

数据结构（C语言）代码实现（十）——链队列循环队列

参考资料

链队列的实现

LinkQueue.h

LinkQueue.cpp

测试函数test.cpp

测试结果

循环队列的实现（最小操作子集）

完整代码

测试结果

参考资料

数据结构严蔚敏版

链队列的实现

LinkQueue.h

#pragma once
#include <cstdio>
#include <cstdlib>
#include <cstring>#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型，其值是函数结果状态代码
typedef char QElemType;//-----ADT Queue的表示与实现-----
//-----单链队列——队列的链式存储结构-----
typedef struct QNode{QElemType data;struct QNode* next;
}QNode,*QueuePtr;
typedef struct {QueuePtr front;//队头指针QueuePtr rear;//队尾指针
}LinkQueue;//-----基本操作的函数原型说明-----
Status InitQueue(LinkQueue& Q);
//构造一个空队列Q
Status DestroyQueue(LinkQueue& Q);
//销毁队列Q，Q不再存在
Status ClearQueue(LinkQueue& Q);
//将Q清为空队列
Status QueueEmpty(LinkQueue Q);
//若队列Q为空队列，则返回TRUE，否则返回FALSE
int QueueLength(LinkQueue Q);
//返回Q的元素个数，即为队列的长度
Status GetHead(LinkQueue Q, QElemType& e);
//若队列不空，则用e返回Q的队头元素,并返回OK；
//否则返回ERROR
Status EnQueue(LinkQueue& Q, QElemType e);
//插入元素e为Q的新的队尾元素
Status DeQueue(LinkQueue& Q, QElemType& e);
//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；
//否则返回ERROR
Status QueueTraverse(LinkQueue Q, Status visit(QElemType));
//从队头到队尾依次对队列Q中每个元素调用函数visit()。一旦visit失败，则操作失败。

LinkQueue.cpp

#include "LinkQueue.h"//-----基本操作的算法描述-----
Status InitQueue(LinkQueue& Q) {//-----构造一个空队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if (!Q.front)exit(OVERFLOW);//存储分配失败Q.front->next = NULL;return OK;
}Status DestroyQueue(LinkQueue& Q) {//销毁队列Qwhile (Q.front) {Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;}return OK;
}Status ClearQueue(LinkQueue& Q) {//将Q清为空队列QElemType e;while(DeQueue(Q,e)==OK){}return OK;
}Status QueueEmpty(LinkQueue Q) {//若队列Q为空队列，则返回TRUE，否则返回FALSEif (Q.front == Q.rear)return TRUE;elsereturn FALSE;
}int QueueLength(LinkQueue Q) {//返回队列长度int n = 0;QueuePtr p = Q.front;while (p != Q.rear) {p = p->next;n++;}return n;
}Status GetHead(LinkQueue Q, QElemType& e) {if (Q.front == Q.rear)return ERROR;e = Q.front->next->data;return OK;
}Status EnQueue(LinkQueue& Q, QElemType e) {//插入元素e为Q的新的队尾元素QueuePtr p = (QueuePtr)malloc(sizeof(QNode));if (!p)exit(OVERFLOW);p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;
}Status DeQueue(LinkQueue& Q, QElemType& e) {//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；//否则返回ERRORif (Q.front == Q.rear)return ERROR;//Q.front->next==NULL;也行QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if (Q.rear == p)Q.rear = Q.front;//队列为空时将尾指针重置free(p);return OK;
}Status QueueTraverse(LinkQueue Q, Status visit(QElemType)) {if (Q.front == Q.rear) {printf("队列为空\n");return OK;}QueuePtr p = Q.front->next;while (p) {visit(p->data);p = p->next;}printf("\n");return OK;
}

测试函数test.cpp

#include "LinkQueue.h"Status visit(QElemType m) {printf(" %c", m);return OK;
}int main()
{LinkQueue Q;QElemType e;Status i;int w = 65;i = InitQueue(Q);if (i)printf("已创建队列！\n");for (int j = 0;j <= 5;j++)EnQueue(Q, w + j);QueueTraverse(Q, visit);GetHead(Q,e);printf("队列头元素：%c\n", e);ClearQueue(Q);if (QueueEmpty(Q) == TRUE)printf("队列已清空！\n");elseprintf("队列未清空！\n");DestroyQueue(Q);return 0;
}

测试结果

循环队列的实现（最小操作子集）

完整代码

#include <cstdio>
#include <cstdlib>
#include <cstring>#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型，其值是函数结果状态代码
typedef char QElemType;//-----循环队列——队列的顺序存储结构-----
#define MAXQSIZE 5 //最大队列长度，便于测试
typedef struct {QElemType* base;//初始化的动态分配存储空间int front;      //头指针，若队列不空，指向队列头元素int rear;       //尾指针。若队列不空，指向队列尾元素的下一个位置
}SqQueue;//-----循环队列的基本操作的算法描述-----
Status InitQueue(SqQueue& Q) {//构造一个空队列QQ.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));if (!Q.base)exit(OVERFLOW);//存储分配失败Q.front = Q.rear = 0;return OK;
}int QueueLength(SqQueue Q) {//返回Q的元素个数，即队列长度return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}Status EnQueue(SqQueue& Q, QElemType e) {//插入元素e为Q的新的队尾元素if ((Q.rear + 1) % MAXQSIZE == Q.front)return ERROR;//队列满Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK;
}Status DeQueue(SqQueue& Q, QElemType& e) {//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;//否则返回ERROR。if (Q.front == Q.rear)return ERROR;e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXQSIZE;return OK;
}int main()
{SqQueue Q;QElemType e=65;Status i;InitQueue(Q);for (int j = 0;j < 7;j++){i = EnQueue(Q, e + j);if (i)printf("元素%c已成功入队列！\n",e + j);elseprintf("队列已满！\n");}for (int j = MAXQSIZE;j > 0;j--){i = DeQueue(Q, e);if (i)printf("元素%c已成功出队列！\n",e);elseprintf("队列已空！\n");}free(Q.base);return 0;
}