[C++知识库]队列(循环队列)的基本操作 （C语言实现）

说明：这里循环队列的实现方式是 少用一个元素空间

注意：队列时尾插头删

1.入队分析：

void EnQueue(SqQueue *Q, QElemType e)//循环队列入队
{
	if ((Q->rear+1) % MAXQSIZE == Q->front)//判断队满，当rear与front差一个空间的时候即为队满
	{
		printf("队列已满，无法插入\n");
		exit(-1);
	}
	printf("入队元素为:%d\n", e);
	Q->base[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXQSIZE;//队尾指针+1；
}

2.出队分析：

void DeQueue(SqQueue *Q)//循环队列出队（头出）
{
	if (Q->rear == Q->front)//判断是否队空，这里就不用考虑rear与front差一个空间（刚初始化时，Q->rear == Q->front）
	{
		printf("队列已空\n");
		exit(-1);
	}
	printf("出队元素为:%d\n", Q->base[Q->front]);
	Q->front = (Q->front +1) % MAXQSIZE;//队头指针+1
}

3.代码实现：

#include<stdio.h>
#include<stdlib.h>
#define MAXQSIZE 100
typedef int QElemType;
typedef struct
{
	QElemType *base;//初始化的动态分配内存空间
	int front;//头指针，若队列不空，指向队列头元素
	int rear;//尾指针，若队列不空，指向队列尾元素的下一个元素
}SqQueue;

void InitQueue(SqQueue *Q)//初始化
{
	Q->base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
	if (!Q->base)
		exit(-1);//内存分配失败
	Q->front = 0;//头指针 尾指针 置为0，队列为空
	Q->rear = 0;
}

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

void EnQueue(SqQueue *Q, QElemType e)//循环队列入队
{
	if ((Q->rear+1) % MAXQSIZE == Q->front)//队满
	{
		printf("队列已满，无法插入\n");
		exit(-1);
	}
	printf("入队元素为:%d\n", e);
	Q->base[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXQSIZE;//队尾指针+1；
}

void DeQueue(SqQueue *Q)//循环队列出队（头出）
{
	if (Q->rear == Q->front)//判断是否队空
	{
		printf("队列已空\n");
		exit(-1);
	}
	printf("出队元素为:%d\n", Q->base[Q->front]);
	Q->front = (Q->front +1) % MAXQSIZE;//队头指针+1
}

QElemType GetHead(SqQueue *Q)//获取队头元素
{
	if (Q->front != Q->rear)
		return Q->base[Q->front];
	else
		exit(-1);
}

void test1()
{
	SqQueue Q;
	InitQueue(&Q);

	EnQueue(&Q, 1);
	EnQueue(&Q, 2);
	EnQueue(&Q, 3);
	EnQueue(&Q, 4);
	int length=QueueLength(&Q);
	printf("队列长度尾%d\n\n", length);

	DeQueue(&Q);
	DeQueue(&Q);
	DeQueue(&Q);
	length = QueueLength(&Q);
	printf("队列长度尾%d\n\n", length);

	int head = GetHead(&Q);
	printf("队头元素为:%d\n", head);
}
int main()
{
	test1();
	return 0;
}