循环队列(出队、入队、判空、长度、遍历、取头)(数据结构与算法)_实现一个队列并包括队列的入队出队以及判断队列是否为空的方法

循环队列

涉及到移动、赋值原队列参数的函数参数列表如front，rear，都最好别用&引用，否则会修改原队列中的地址和数值如：SqQueue &Q
使用SqQueue Q作参数列表时，函数引入的只是一份副本，不会修改原队列中变量、指针的空间地址与数值。

• 在函数参数列表中，使用&符号将参数声明为引用类型。这意味着该函数将直接操作传递给它的变量，而不是创建该变量的副本。

• 当不使用&时，参数将被声明为传值方式传递。这意味着在将变量传递给函数时，将创建该变量的一份副本，并在函数内部使用该副本。

• 在函数内部对参数进行的任何修改都不会影响到原始变量。

• 在使用&时，参数将被声明为引用方式传递。这意味着函数将直接访问传递给它的变量，而不是创建副本。在函数内部对参数的任何修改都会直接影响原始变量。

因此，使用&可以避免不必要的复制，节省内存和处理时间。同时，通过对原始变量的修改，可以使函数更灵活地与其他代码进行交互。

创建循环队列结构体

//循环队列
typedef struct
{
	QElemType* base;	//初始化的动态分配存储空间
	int front;	//头指针，若队列不空，指向队列头元素
	int rear;	//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;  //普通类型用 '.' *SqQueue指针类型用 '->'
1
2
3
4
5
6
7

队列初始化

分配数组空间、判断是否分配成功、令队头队尾指针指向初始位置0，队列为空

//队列的初始化
bool InitQueue(SqQueue& Q)
{
	Q.base = new QElemType[MAXQSIZE]; //分配数组空间
	//Q.base = (QElemType*)MAXQSIZE * sizeof(QElemType);  C语言语法
	if (!Q.base)
	{
		exit(OVERFLOW);  //存储分配失败
	}
	Q.front = Q.rear = 0; //头指针尾指针置为0， 队列为空
	return true; 
}
1
2
3
4
5
6
7
8
9
10
11
12

循环队列入队

//循环队列入队
bool EnQueue(SqQueue& Q, QElemType value)
{
	if (!QueueFull(Q))   //如果队列没满
	{
		Q.base[Q.rear] = value; //将入队元素放入Q.rear所指向的空间中
		Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针+1
		return true;
	}
	return false; //队列已满，入队失败
}
1
2
3
4
5
6
7
8
9
10
11

循环队列出队

//循环队列出队
bool DeQueue(SqQueue& Q, QElemType value)
{
	if (!QueueEmpty(Q))  //如果队列非空
	{
		value = Q.base[Q.front];//将出栈元素保存到value中
		Q.front = (Q.front + 1) % MAXQSIZE; //队头指针+1
		return true; 
	}
	return false; //队列为空，出队失败
}
1
2
3
4
5
6
7
8
9
10
11

取队头元素

//取队头元素
QElemType GetHead(SqQueue Q)
{
	if (!QueueEmpty(Q)) //队列不为空
	{
		return Q.base[Q.front];  //返回队头指针元素
	}
	return false;
}
1
2
3
4
5
6
7
8
9

遍历队列元素

//遍历打印队列元素
bool QueuePrint(SqQueue Q) 
{
	//这里注意！！！ 如果要用这种方法，参数列表一定不能用'SqQueue &value'引用，
	//因为使用&会修改真正的Q.front和Q.rear空间地址,影响原函数的指针位置，和后面的函数调用。
	if (Q.front == Q.rear)
		return false;
	while (Q.front != Q.rear)
	{
		cout << Q.base[Q.front] << "  ";
		Q.front = (Q.front + 1) % MAXQSIZE;
	}
	cout << endl;
	return true;

	//方案二，由于额外创建了临时变量遍历队列，不管用不用'&Q'都不会影响原队列中front与rear的位置
	//if (!QueueEmpty(Q))   //队列非空
	//{
	//	QElemType temp = Q.front; //创建临时变量，位置与队头相同
	//	while (temp != Q.rear)
	//	{
	//		cout << Q.base[temp] << " ";  //输出temp所处位置的元素
	//		temp = (temp + 1) % MAXQSIZE; //temp位置上移加 1 
	//	}
	//	cout << endl;
	//	return true;
	//}
	//return false;
}
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

循环队列长度/元素个数

//求循环队列的长度/元素个数
int QueueLength(SqQueue Q)
{
	//若rear指向大于队列长度后重新转一圈指向队头，假如rear=3，front= 4, 3-4=-1不合法。则通过（3-4+6)%6 = 5个元素
	return((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}
1
2
3
4
5
6

队列判空

//判断队列是否为空
bool QueueEmpty(SqQueue& Q)
{
	return (Q.front == Q.rear);
}
1
2
3
4
5

队列判满

//判断队列是否已满
bool QueueFull(SqQueue& Q)
{
	return (Q.rear + 1) % MAXQSIZE == Q.front;  //队列满
}
1
2
3
4
5

完整代码

#include<iostream>
using namespace std;

#define MAXQSIZE 100  //最大队列长度
typedef int QElemType;

//循环队列
typedef struct
{
	QElemType* base;	//初始化的动态分配存储空间
	int front;	//头指针，若队列不空，指向队列头元素
	int rear;	//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;  //普通类型用 '.' *SqQueue指针类型用 '->'

bool InitQueue(SqQueue& Q);			//循环队列初始化
int  QueueLength(SqQueue Q);			//循环队列长度
bool QueueFull(SqQueue& Q);			//判断队列是否已满
bool QueueEmpty(SqQueue& Q);		//判断队列是否为空
bool EnQueue(SqQueue& Q, QElemType value);//循环队列入队
bool DeQueue(SqQueue& Q, QElemType value);//循环队列出队
bool QueuePrint(SqQueue Q);		//打印输出队列
QElemType GetHead(SqQueue Q);		//获取队头元素

//队列的初始化
bool InitQueue(SqQueue& Q)
{
	Q.base = new QElemType[MAXQSIZE]; //分配数组空间
	//Q.base = (QElemType*)MAXQSIZE * sizeof(QElemType);  C语言语法
	if (!Q.base)
	{
		exit(OVERFLOW);  //存储分配失败
	}
	Q.front = Q.rear = 0; //头指针尾指针置为0， 队列为空
	return true; 
}
//求循环队列的长度/元素个数
int QueueLength(SqQueue Q)
{
	//若rear指向大于队列长度后重新转一圈指向队头，假如rear=3，front= 4, 3-4=-1不合法。则通过（3-4+6)%6 = 5个元素
	return((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}
//判断队列是否已满
bool QueueFull(SqQueue& Q)
{
	return (Q.rear + 1) % MAXQSIZE == Q.front;  //队列满
}
//判断队列是否为空
bool QueueEmpty(SqQueue& Q)
{
	return (Q.front == Q.rear);
}
//循环队列入队
bool EnQueue(SqQueue& Q, QElemType value)
{
	if (!QueueFull(Q))   //如果队列没满
	{
		Q.base[Q.rear] = value; //将入队元素放入Q.rear所指向的空间中
		Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针+1
		return true;
	}
	return false; //队列已满，入队失败
}
//循环队列出队
bool DeQueue(SqQueue& Q, QElemType value)
{
	if (!QueueEmpty(Q))  //如果队列非空
	{
		value = Q.base[Q.front];//将出栈元素保存到value中
		Q.front = (Q.front + 1) % MAXQSIZE; //队头指针+1
		return true; 
	}
	return false; //队列为空，出队失败
}
//取队头元素
QElemType GetHead(SqQueue Q)
{
	if (!QueueEmpty(Q)) //队列不为空
	{
		return Q.base[Q.front];  //返回队头指针元素
	}
	return false;
}
//遍历打印队列元素
bool QueuePrint(SqQueue Q) 
{
	//这里注意！！！ 如果要用这种方法，参数列表一定不能用'SqQueue &value'引用，
	//因为使用&会修改真正的Q.front和Q.rear空间地址,影响原函数的指针位置，和后面的函数调用。
	if (Q.front == Q.rear)
		return false;
	while (Q.front != Q.rear)
	{
		cout << Q.base[Q.front] << "  ";
		Q.front = (Q.front + 1) % MAXQSIZE;
	}
	cout << endl;
	return true;

	//方案二，由于额外创建了临时变量用来遍历队列，不管用不用'&Q'都不会影响原队列中front与rear的位置
	//if (!QueueEmpty(Q))   //队列非空
	//{
	//	QElemType temp = Q.front; //创建临时变量，位置与队头相同
	//	while (temp != Q.rear)
	//	{
	//		cout << Q.base[temp] << " ";  //输出temp所处位置的元素
	//		temp = (temp + 1) % MAXQSIZE; //temp位置上移加 1 
	//	}
	//	cout << endl;
	//	return true;
	//}
	//return false;
}

int main13()
{
	SqQueue Q;  //创建循环队列Q
	InitQueue(Q); //队列初始化
	QElemType value = 0;
	
	int number = 0; //入队的元素个数
	cout << "请输入要入队的元素个数：" << " ";
	cin >> number;

	int num = 0; //入队的数据元素
	while ((number--) > 0)
	{
		cin >> num; //输入数据元素
		EnQueue(Q, num); //将num入队 
	}

	cout << "队列输出顺序：";
	QueuePrint(Q); //遍历输出队列元素
	cout << "队头元素为：" << GetHead(Q) << endl;
	cout << "队列长度为：" << QueueLength(Q) << endl;
	
	cout << endl;
	DeQueue(Q, value);
	QueuePrint(Q);  //遍历输出
	cout << "出队后队头元素为：" << GetHead(Q) << endl;
	cout << "出队后队列长度为：" << QueueLength(Q) << endl;

	system("pause");
	return 0;
}

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

输出结果为：

循环队列的特点

1. 顺序存储：循环队列使用数组作为底层数据结构，元素按顺序存储在数组中。这样可以简化队列的实现，并且通过使用循环来优化队列的操作。

2. 固定容量：循环队列拥有固定的容量，即队列最多可以存储的元素数量是预先确定的。在使用数组作为底层数据结构时，需要初始化队列的最大容量。

3. 头尾相连：循环队列将队列的头部和尾部连接起来形成一个环状结构，当队列的尾部指针达到数组的最末尾时，它将会绕回到数组的开头。这样可以充分利用数组的存储空间，避免浪费空间。

4. 队空和队满判断：循环队列通过队头指针和队尾指针的位置关系来判断队列的状态。当队头指针和队尾指针相等时，表示队列为空；当队尾指针的下一个位置是队头指针时，表示队列已满。

5. 入队和出队的复杂度：在循环队列中，入队和出队操作的时间复杂度都是O(1)，即常数时间复杂度。这是因为循环队列通过使用固定容量和记录队列元素个数的方式，避免了移动元素的成本。