当前位置:   article > 正文

(队列篇)1、队列的概念及其基本操作(采用顺序存储结构,C++代码编写,包括初始化、入队、出队、获取当前队列长度等)_队列入队出队的代码

队列入队出队的代码

一、队列概念

队列是一种操作受限的线性表,只允许在一端进行插入,在另一端删除。其操作的特性是先进先出First In First Out(FIFO),记得区分栈和队列。

具体过程如图:
在这里插入图片描述
此篇文章是采用顺序存储的方式实现队列,在内存中分配一块连续的存储单元存放队列中的元素(相当于创建一个数组而已),还要建立 front 和 rear 指针(虽说是指针,其实就是记住队头和队尾的位置,方便进行插入和删除),本文中 front 指向队头元素,rear 指向队尾元素的下一个位置。

二、基本操作

在进行相关操作之前,先要创建队列里面的基本元素(结构体):

#define MaxSize 100			//最大存储个数

//非循环队列
typedef int ElemType;		//typedef用于取别名,这里int取个别名,方便统一data的类型
typedef struct {
	ElemType data[MaxSize];
	int front;		/*头指针*/
	int rear;		/*尾指针,若队列不空,指向队列元素的下一个位置*/
}SqQueue;			//SqQueue是这个结构体的别名
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

(tips:如果对 & 引用有问题的话,跳到最后去看一下我推荐的文章吧,我主要在函数里面用的是引用传递)

1、初始化队列,对 front 和 rear 赋值

//1、初始化一个空队列
void InitQueue(SqQueue &Q) {
	Q.front = 0;		//均初始化为0
	Q.rear = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5

2、队列当前长度

返回的是真实队列的长度。

//2、队列当前长度
int QueueLength(SqQueue Q) {
	return (Q.rear - Q.front + MaxSize) % MaxSize;		//数学哈哈哈
}
  • 1
  • 2
  • 3
  • 4

3、队列判空

只要 front 和 rear的值相等就证明队列空了。

//3、队列判空
bool isEmpty(SqQueue Q) {
	return (Q.front == Q.rear);		//空则true,否则false
}
  • 1
  • 2
  • 3
  • 4

4、队列判满

队列满了就不能进行入队了,不然会溢出。(其实如果出队了的话,数组前面其实还是有位置的,所以会造成假溢出,这可以用循环队列进行处理。)

//4、队列判满
bool isFull(SqQueue Q) {
	return (Q.rear == MaxSize);		//满则返回true,否则false
}
  • 1
  • 2
  • 3
  • 4

5、入队

若队列未满,则将x加入,满了则不入队。

//5、入队
bool EnQueue(SqQueue &Q, ElemType x) {
	if (isFull(Q)) {				//队列满的判断
		cout << "队列已满,不能入队!" << endl;
		return false;
	}

	Q.data[Q.rear++] = x;	//入队操作
	return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

6、出队

若队列非空,删除队头元素,并用x返回。

//6、出队
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (isEmpty(Q)) {			//队列空的判断
		cout << "队列已空,不能出队!" << endl;
		return false;
	}

	x = Q.data[Q.front++];
	return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

7、读取队头元素

若队列非空,则将队头元素赋值给x,记住不会改变队列,仅仅是读取而已。

//7、读取队头元素
bool GetHead(SqQueue Q, ElemType& x) {
	if (isEmpty(Q)) {
		cout << "队列已空,不能读取头元素!" << endl;
		return false;
	}
	x = Q.data[Q.front];
	return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

 

三、整体代码过程

#include <iostream>
using namespace std;

#define MaxSize 100			//最大存储个数

//非循环队列
typedef int ElemType;
//结构体
typedef struct {
	ElemType data[MaxSize];
	int front;		/*头指针*/
	int rear;		/*尾指针,若队列不空,指向队列元素的下一个位置*/
}SqQueue;

//基本操作
//1、初始化一个空队列
void InitQueue(SqQueue &Q) {
	Q.front = 0;
	Q.rear = 0;
}

//2、队列当前长度
int QueueLength(SqQueue Q) {
	return (Q.rear - Q.front + MaxSize) % MaxSize;
}

//3、队列判空
bool isEmpty(SqQueue Q) {
	return (Q.front == Q.rear);		//空则true,否则false
}

//4、队列判满
bool isFull(SqQueue Q) {
	return (Q.rear == MaxSize);		//满则返回true,否则false
}

//5、入队
bool EnQueue(SqQueue &Q, ElemType x) {
	if (isFull(Q)) {				//队列满的判断
		cout << "队列已满,不能入队!" << endl;
		return false;
	}

	Q.data[Q.rear++] = x;	//入队操作
	return true;
}

//6、出队
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (isEmpty(Q)) {			//队列空的判断
		cout << "队列已空,不能出队!" << endl;
		return false;
	}

	x = Q.data[Q.front++];
	return true;
}

//7、读取队头元素
bool GetHead(SqQueue Q, ElemType& x) {
	if (isEmpty(Q)) {
		cout << "队列已空,不能读取头元素!" << endl;
		return false;
	}
	x = Q.data[Q.front];
	return true;
}


//主函数
int main() {
	SqQueue Q;
	//初始化
	InitQueue(Q);

	//入队
	for (int i = 0; i < 5; i++) {
		EnQueue(Q, i);
	}

	//获取当前队列长度
	int length = QueueLength(Q);
	cout << "当前队列长度为:" << length << endl;

	//出队
	int x = -1;		//存储出队的元素,随便赋个值,不然会报错
	DeQueue(Q, x);
	cout << "出队的元素是:" << x << endl;

	//读取队头元素
	int t = -1;
	GetHead(Q, t);
	cout << "当前队头元素是:" << t << endl;

	//获取当前队列长度
	length = QueueLength(Q);
	cout << "当前队列长度为:" << length << endl;

	return 1;

}
  • 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

结果:
在这里插入图片描述

如果对函数形参传进来的 & 有疑问,可以看一下这篇文章:C++ 中指针和引用的区别

大家一起学,一起进步!!!
各位宝子们如果觉滴还不错的话,可以点个赞 or 收个藏 or 打个赏哦,佛系博主一个。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/884856
推荐阅读
相关标签
  

闽ICP备14008679号