• 循环队列(出队、入队、判空、长度、遍历、取头)(数据结构与算法)

    循环队列

    涉及到移动、赋值原队列参数的函数参数列表如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
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)，即常数时间复杂度。这是因为循环队列通过使用固定容量和记录队列元素个数的方式，避免了移动元素的成本。

  • 相关阅读:
    华为数通——奇偶数子网划分与流量控制（QoS）
    开创性的区块链操作系统项目——益智RPG游戏
    【洛谷】P3275 糖果
    CppLib v1.1 和 pexports v4.7 的下载链接记录
    Patroni for opengauss 9：basebackup
    IB化学介绍及备考
    【自动驾驶】ROS小车系统
    MVC和MVVM
    分类散点图 stripplot() 加辅助线axhline() 多图合一
    AGV调度台软件QT
  • 原文地址：https://blog.csdn.net/AII_IIA/article/details/134477564