数据结构（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) {
	//-----构造一个空队列Q
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front)exit(OVERFLOW);//存储分配失败
	Q.front->next = NULL;
	return OK;
}

Status DestroyQueue(LinkQueue& Q) {
	//销毁队列Q
	while (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，否则返回FALSE
	if (Q.front == Q.rear)
		return TRUE;
	else
		return 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；
	//否则返回ERROR
	if (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");
	else
		printf("队列未清空！\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) {
	//构造一个空队列Q
	Q.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);
		else
			printf("队列已满！\n");
	}
	for (int j = MAXQSIZE;j > 0;j--)
	{
		i = DeQueue(Q, e);
		if (i)
			printf("元素%c已成功出队列！\n",e);
		else
			printf("队列已空！\n");
	}
	free(Q.base);
	return 0;
}