循环队列

一、定义

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 队列最大长度
#define OVERFLOW 0
typedef int Status;
typedef int QElemType;

//类型定义
typedef struct {
	QElemType* base;//动态分配内存空间用
	int front;//头指针，若队列不空，只想队列头元素
	int rear;//尾指针，若队列不空，指向队尾元素的下一个位置
}SqQueue;

二、初始化

//初始化
Status InitQueue(SqQueue& Q) {
	Q.base = new QElemType[MAXSIZE];//分配数组空间
	//Q.base=malloc(MAXSIZE * sizeof(QElemType));
	if (Q.base) return(OVERFLOW);//存储分配失败
	Q.front = Q.rear = 0;//头尾指针置为0，队列为空
}

三、求队列长度

//求队列长度
int QueueLength(SqQueue Q) {
	return ((Q.rear - Q.front + MAXSIZE) % MAXSIZE);
}

image-20230411211446817

四、解决假上溢引入循环队列

image-20230411213905769

五、循环队列入队

//循环队列入队
Status EnQueue(SqQueue& Q, QElemType e) {
	if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;//队满
	Q.base[Q.rear] = e;//新元素队尾插入
	Q.rear = (Q.rear + 1) % MAXSIZE;//队尾指针+1
	return OK;
}

六、循环队列出队

//循环队列出队
Status DeQueue(SqQueue& Q, QElemType& e) {
	if (Q.front == Q.rear) return ERROR;//队空
	e = Q.base[Q.front];		//保存队头元素
	Q.front = (Q.front + 1) % MAXSIZE;//对头指针+1
}

七、取队头元素

//取队头元素
QElemType GetHead(SqQueue Q) {
	if (Q.rear != Q.front)//队列不为空
		return Q.base[Q.front];//返回头指针元素，队头指针不变
}

八、main实现


int main() {
	InitQueue(Q);
	QElemType e;
	printf("输入入队元素，输入-1结束：\n");
	scanf("%d", &e);
	while(e!=-1){
	EnQueue(Q, e);
	scanf("%d", &e);
	}
	QElemType a= GetHead(Q);
	printf("队头元素%d\n", a);
	int len=QueueLength(Q);
	printf("队长%d\n",len);
	printf("出队：");
	while (Q.front != Q.rear) {
		DeQueue(Q,e);
		printf("%d", e);
	}	
}

image-20230411220923080

九、完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 队列最大长度
#define OVERFLOW 0
#define ERROR 0
#define OK 1
typedef int Status;
typedef int QElemType;
//类型定义
typedef struct {
	QElemType* base;//动态分配内存空间用
	int front;//头指针，若队列不空，只想队列头元素
	int rear;//尾指针，若队列不空，指向队尾元素的下一个位置
}SqQueue;
SqQueue Q;
//初始化
Status InitQueue(SqQueue& Q) {
	Q.base = new QElemType[MAXSIZE];//分配数组空间
	//Q.base=malloc(MAXSIZE * sizeof(QElemType));
	if (Q.base) return(OVERFLOW);//存储分配失败
	Q.front = Q.rear = 0;//头尾指针置为0，队列为空
}
//求队列长度
int QueueLength(SqQueue Q) {
	return ((Q.rear - Q.front + MAXSIZE) % MAXSIZE);
}
//循环队列入队
Status EnQueue(SqQueue& Q, QElemType e) {
	if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;//队满
	Q.base[Q.rear] = e;//新元素队尾插入
	Q.rear = (Q.rear + 1) % MAXSIZE;//队尾指针+1
	return OK;
}
//循环队列出队
Status DeQueue(SqQueue& Q, QElemType& e) {
	if (Q.front == Q.rear) return ERROR;//队空
	e = Q.base[Q.front];		//保存队头元素
	Q.front = (Q.front + 1) % MAXSIZE;//对头指针+1
}
//取队头元素
QElemType GetHead(SqQueue Q) {
	if (Q.rear != Q.front)//队列不为空
		return Q.base[Q.front];//返回头指针元素，队头指针不变
}

int main() {
	InitQueue(Q);

	QElemType e;
	printf("输入入队元素，输入-1结束：\n");
	scanf("%d", &e);
	while(e!=-1){
	EnQueue(Q, e);
	scanf("%d", &e);
	}
	QElemType a= GetHead(Q);
	printf("队头元素%d\n", a);
	int len=QueueLength(Q);
	printf("队长%d\n",len);
	printf("出队：");
	while (Q.front != Q.rear) {
		DeQueue(Q,e);
		printf("%d", e);
	}
	
}