队列之循环队列详解（C语言版）

---

前言

        大家好，越努力，越幸运。本篇文章小猿将跟您分享数据结构队列中的循环队列，希望对您有所帮助。

一、循环队列的定义

        顺序队列在使用过程中容易出现虚假的满状态， 为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”，可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。此处使用方法二来解决这个问题。

二、循环队列的结构

结构图

代码描述

//数据类型
#define ElemType int
//队列的最大空间
#define MAXSIZE 8
//队列的管理结构
typedef struct Queue
{
	ElemType *base; //指向队列空间的基址
	int       front; //头指针
	int       rear; //尾指针
}Queue;
1
2
3
4
5
6
7
8
9
10
11

三、循环队列的常用操作

初始化

//队列初始化
void InitQueue(Queue *Q)
{
	//为队列分配存储空间
	Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
	assert(Q->base != NULL);
	//初始时队列为空，头指针和尾指针都指向0位置
	Q->front = Q->rear = 0;
}
1
2
3
4
5
6
7
8
9

入队

//入队操作
void EnQueue(Queue *Q, ElemType x)
{
	//判断循环队列是否已满
	if(((Q->rear+1)%MAXSIZE) == Q->front)
		return;
	//队列未满，将数据入队
	Q->base[Q->rear] = x;
	//更改尾指针的指向
	Q->rear = (Q->rear+1)%MAXSIZE;
}
1
2
3
4
5
6
7
8
9
10
11

出队

//出队操作
void DeQueue(Queue *Q)
{
	//判断循环队列是否为空
	if(Q->front == Q->rear)
		return;
	//如果非空，实现可循环出队
	Q->front = (Q->front+1)%MAXSIZE;
}
1
2
3
4
5
6
7
8
9

打印队列数据

//打印循环队列中的数据
void ShowQueue(Queue *Q)
{
	//遍历循环队列中的元素，并将数据打印
	for(int i=Q->front; i!=Q->rear;)
	{
		printf("%d ",Q->base[i]);
		//此操作是为了实现循环遍历
		i = (i+1)%MAXSIZE;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

获取队头元素

//获取队头元素
void GetHdad(Queue *Q, ElemType *v)
{
	//判断循环队列是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列不为空，获取队头元素
	*v = Q->base[Q->front];
}
1
2
3
4
5
6
7
8
9

求队列长度

//获取队列长度（元素个数）
int Length(Queue *Q)
{
	//计算尾指针位置与头指针位置的差距
	int len= Q->rear - Q->front;
	//如果为正数，那么len就是队列的长度；如果为负数，那么MAXSIZE+len才是队列的长度
	len = (len>0) ? len : MAXSIZE+len;
	return len;
}
1
2
3
4
5
6
7
8
9

清空队列

//清空队列
void ClearQueue(Queue *Q)
{
	//将队头指针和队尾指针都置为0
	Q->front = Q->rear = 0;
}
1
2
3
4
5
6

销毁队列

//销毁队列
void DestroyQueue(Queue *Q)
{
	//释放队列的存储空间
	free(Q->base);
	//将队列基址置空
	Q->base = NULL;
}
1
2
3
4
5
6
7
8

结语

        对循环队列的介绍就到这里啦，希望这篇文章能给予你一些帮助，感谢各位人才的：点赞、收藏和评论，我们下次见。

附录

以下提供循环队列的测试代码

SeqQueue.h

#ifndef __SEQQUEUE_H__
#define __SEQQUEUE_H__

#include<stdio.h>
#include<malloc.h>
#include<assert.h>
//数据类型
#define ElemType int
//队列的最大空间
#define MAXSIZE 8
//队列的管理结构
typedef struct Queue
{
	ElemType *base; //指向队列空间的基址
	int       front; //头指针
	int       rear; //尾指针
}Queue;

void InitQueue(Queue *Q);
void EnQueue(Queue *Q, ElemType x);
void ShowQueue(Queue *Q);
void DeQueue(Queue *Q);

void GetHdad(Queue *Q, ElemType *v);
int Length(Queue *Q);
void ClearQueue(Queue *Q);
void DestroyQueue(Queue *Q);


#endif //__SEQQUEUE_H__
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

SeqQueue.cpp

#include"SeqQueue.h"

//队列初始化
void InitQueue(Queue *Q)
{
	//为队列分配存储空间
	Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
	assert(Q->base != NULL);
	//初始时队列为空，头指针和尾指针都指向0位置
	Q->front = Q->rear = 0;
}

//入队操作
void EnQueue(Queue *Q, ElemType x)
{
	//判断循环队列是否已满
	if(((Q->rear+1)%MAXSIZE) == Q->front)
		return;
	//队列未满，将数据入队
	Q->base[Q->rear] = x;
	//更改尾指针的指向
	Q->rear = (Q->rear+1)%MAXSIZE;
}

//打印循环队列中的数据
void ShowQueue(Queue *Q)
{
	//遍历循环队列中的元素，并将数据打印
	for(int i=Q->front; i!=Q->rear;)
	{
		printf("%d ",Q->base[i]);
		//此操作是为了实现循环遍历
		i = (i+1)%MAXSIZE;
	}
	printf("\n");
}

//出队操作
void DeQueue(Queue *Q)
{
	//判断循环队列是否为空
	if(Q->front == Q->rear)
		return;
	//如果非空，实现可循环出队
	Q->front = (Q->front+1)%MAXSIZE;
}

//获取队头元素
void GetHdad(Queue *Q, ElemType *v)
{
	//判断循环队列是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列不为空，获取队头元素
	*v = Q->base[Q->front];
}

//获取队列长度（元素个数）
int Length(Queue *Q)
{
	//计算尾指针位置与头指针位置的差距
	int len= Q->rear - Q->front;
	//如果为正数，那么len就是队列的长度；如果为负数，那么MAXSIZE+len才是队列的长度
	len = (len>0) ? len : MAXSIZE+len;
	return len;
}


//清空队列
void ClearQueue(Queue *Q)
{
	//将队头指针和队尾指针都置为0
	Q->front = Q->rear = 0;
}

//销毁队列
void DestroyQueue(Queue *Q)
{
	//释放队列的存储空间
	free(Q->base);
	//将队列基址置空
	Q->base = NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

Main.cpp

#include"SeqQueue.h"

void main()
{
	Queue Q;
	InitQueue(&Q);

	for(int i=1; i<=8; ++i)
	{
		EnQueue(&Q, i);
	}
	ShowQueue(&Q);
	DeQueue(&Q);
	EnQueue(&Q,10);
	DeQueue(&Q);
	EnQueue(&Q,20);
	ShowQueue(&Q);
	printf("%d\n",Length(&Q));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20