数据结构学习笔记——队列的基本知识和顺序存储结构实现队列

目录

• 一、队列
• 二、顺序队列的定义
• 三、顺序队列的初始化
• 四、判断顺序队列是否为空队
• 五、判断顺序队列是否为满队
• 五、入队（插入 *** 作）
• 六、出队（删除 *** 作）
• 七、读取顺序队列队头元素
• 八、顺序队列的遍历输出
• 九、顺序队列的建立
• ❤️顺序存储结构实现栈的完整代码
• • 一个简单的顺序队列的基本实现例子

一、队列

• 队列与栈一样，它是一种特殊的线性表，其 *** 作受限，它与栈具有相同的逻辑结构，都属于线性结构，区别在于其中元素的处理不同，队列只允许在一端进行插入，且只允许在另一端进行删除，队列遵循的原则是先进先出（FIFO），即先入队列的元素最先离开，与日常生活中的排队是一样的。有两种方式存储队列，顺序存储结构和链式存储结构，即顺序队列和链队列，另外我们还可以将顺序队列的一维数组首尾相连形成一个环状，即为循环队列。
  
  队列的图示如下：
  

二、顺序队列的定义

顺序队列中使用数组来存储队列元素，通过一组数组地址的连续的存储单元来存放从队头至队尾的数据元素，同时设置两个指针，分别是队头指针front和队尾指针rear，用于指示队头元素和队尾元素，定义的代码如下：

//顺序队列的定义
#define MaxSize 20	//可自行设置更改
typedef struct {
	int data[MaxSize];
	int front,rear;	//队头指针和队尾指针
} SqQueue;

三、顺序队列的初始化

当Q.front=Q.rear=0时，表示顺序队列的初始状态，队列为空，如下代码：

//顺序队列的初始化
void InitQueue(SqQueue &Q) {
	Q.front=Q.rear=0;	//队头指针和队尾指针d都指向0
}

四、判断顺序队列是否为空队

判断顺序队列是否为空队时，可以判断两个指针是否相等，即Q.front==Q.rear，如下代码：

//判断顺序队列是否为空队列
bool EmptyQueue(SqQueue Q) {
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

五、判断顺序队列是否为满队

注意，这里判断顺序队列是否为满队的代码，实质上并不是能真正地判断出来，因为存在“假溢出”的现象，当队列还有一个元素时，程序中的if语句判断仍会满足Q.rear==MaxSize这一条件，此时两个指针front和rear都指向data[MaxSize]，即这就是顺序队伍存在的问题，未能判断是否为满队（后续可以通过循环队列解决），代码如下：

//判断顺序队列是否已满
bool FullQueue(SqQueue Q) {
	if(Q.rear==MaxSize)
		return true;
	else
		return false;
}

五、入队（插入 *** 作）

入队 *** 作可以概括为，当队不为满队时，先将要入队的元素进行传入值，然后再将队尾指针加1，如下：

Q.data[Q.rear]=x;	//先将入队元素传入值
Q.rear=Q.rear+1;	//队尾指针加1

以上这两行代码也可以通过一行代码简化，即Q.data[Q.rear++]=x，入队的完整代码如下：

//入队（插入 *** 作）
bool EnterQueue(SqQueue &Q,int x) {
	if(Q.rear==MaxSize)	//表示此时队列已满
		return false;
	//Q.data[Q.rear++]=x;
	Q.data[Q.rear]=x;	//先将入队元素传入值
	Q.rear=Q.rear+1;	//队尾指针加1
	return true;
}

六、出队（删除 *** 作）

出队 *** 作可以概括为，当队不为空队时，先取队头元素，然后将队头指针加1，代码如下：

x=Q.data[Q.front];	//先出队
Q.front=Q.front+1;	//队头指针加1

以上这两行代码也可以通过一行代码简化，即Q.data[Q.front++]=x，出队的完整代码如下：

//出队（删除 *** 作）
bool PopQueue(SqQueue &Q,int x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	//Q.data[Q.front++]=x;
	x=Q.data[Q.front];	//先出队
	Q.front=Q.front+1;	//队头指针加1
	return true;	
}

七、读取顺序队列队头元素

读取当前顺序队列队头元素，并不是取出该队头元素，首先判断队列是否为空，因为队头指针为Q.front，队头元素为Q.data[Q.front]，然后将该值赋给x，通过x记录队头元素，代码如下：

//读取队列的队头元素
bool GetHeadQueue(SqQueue Q,int &x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	x=Q.data[Q.front];	//x记录队头元素
	return true;
}

八、顺序队列的遍历输出

顺序队列的遍历输出中，首先判断队列是否为空，然后通过一个while循环，循环条件是当队头指针小于队尾指针时一直执行下去，然后每次取队头指针所指的数据元素，之后再加1，从而输出每个数据元素，代码如下：

//顺序队列的遍历输出
bool PrintQueue(SqQueue Q,int x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	while(Q.front<Q.rear) {
		x=Q.data[Q.front++];
		printf("%d ",x);
	}
	return true;
}

九、顺序队列的建立

顺序队列的建立程序代码中通过输入一个值表示要创建的顺序队列的元素个数，然后通过一个for循环建立顺序队列，其中每次通过队列的入队 *** 作，从而向队列中输入数据元素并插入至队列中，代码如下：

//顺序栈的建立
void CreateQueue(SqQueue &Q,int x) {
	int number;
	printf("请输入要建立的队列元素个数：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("输入第%d个入队的元素：\n",i+1);
		scanf("%d",&x);
		EnterQueue(Q,x);
	}
}

❤️顺序存储结构实现栈的完整代码

顺序存储结构实现栈的完整代码如下：

#include
#define MaxSize 20
//顺序队列的定义
typedef struct {
	int data[MaxSize];
	int front,rear;	//队头指针和队尾指针
} SqQueue;

//顺序队列的初始化
void InitQueue(SqQueue &Q) {
	Q.front=Q.rear=0;	//队头指针和队尾指针d都指向0
}

//判断顺序队列是否为空队列
bool EmptyQueue(SqQueue Q) {
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

//判断顺序队列是否已满
bool FullQueue(SqQueue Q) {
	if(Q.rear==MaxSize)
		return true;
	else
		return false;
}

//入队（插入 *** 作）
bool EnterQueue(SqQueue &Q,int x) {
	if(Q.rear==MaxSize)	//表示此时队列已满
		return false;
	Q.data[Q.rear++]=x;
	/*Q.data[Q.rear]=x;	//先将入队元素传入值
	Q.rear=Q.rear+1;	//队尾指针加1*/
	return true;
}

//出队（删除 *** 作）
bool PopQueue(SqQueue &Q,int x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	Q.data[Q.front++]=x;
	/*x=Q.data[Q.front];	//先出队
	Q.front=Q.front+1;	//队头指针加1*/
	return true;	
}

//读取队列的队头元素
bool GetHeadQueue(SqQueue Q,int &x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	x=Q.data[Q.front];	//x记录队头元素
	return true;
}

//顺序队列的遍历输出
bool PrintQueue(SqQueue Q,int x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	while(Q.front<Q.rear) {
		x=Q.data[Q.front++];
		printf("%d ",x);
	}
	return true;
}

//顺序栈的建立
void CreateQueue(SqQueue &Q,int x) {
	int number;
	printf("请输入要建立的队列元素个数：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("输入第%d个入队的元素：\n",i+1);
		scanf("%d",&x);
		EnterQueue(Q,x);
	}
}

一个简单的顺序队列的基本实现例子

例如，创建一个顺序队列，其初始数据为{1，2，3，4}，首先遍历输出该队列，然后读取队头元素，执行一次入队 *** 作，入队元素为{5}，此时读取当前的队头元素，执行一次出队 *** 作，此时再读取当前的队头元素，最后遍历输出当前队列。

代码如下：

#include
#define MaxSize 20
//顺序队列的定义
typedef struct {
	int data[MaxSize];
	int front,rear;	//队头指针和队尾指针
} SqQueue;

//顺序队列的初始化
void InitQueue(SqQueue &Q) {
	Q.front=Q.rear=0;	//队头指针和队尾指针d都指向0
}

//判断顺序队列是否为空队列
bool EmptyQueue(SqQueue Q) {
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

//判断顺序队列是否已满
bool FullQueue(SqQueue Q) {
	if(Q.rear==MaxSize)
		return true;
	else
		return false;
}

//入队（插入 *** 作）
bool EnterQueue(SqQueue &Q,int x) {
	if(Q.rear==MaxSize)	//表示此时队列已满
		return false;
	Q.data[Q.rear++]=x;
	/*Q.data[Q.rear]=x;	//先将入队元素传入值
	Q.rear=Q.rear+1;	//队尾指针加1*/
	return true;
}

//出队（删除 *** 作）
bool PopQueue(SqQueue &Q,int x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	Q.data[Q.front++]=x;
	/*x=Q.data[Q.front];	//先出队
	Q.front=Q.front+1;	//队头指针加1*/
	return true;	
}

//读取队列的队头元素
bool GetHeadQueue(SqQueue Q,int &x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	x=Q.data[Q.front];	//x记录队头元素
	return true;
}

//顺序队列的遍历输出
bool PrintQueue(SqQueue Q,int x) {
	if(Q.front==Q.rear)
		return false;	//若队列为空则报错
	while(Q.front<Q.rear) {
		x=Q.data[Q.front++];
		printf("%d ",x);
	}
	return true;
}

//顺序栈的建立
void CreateQueue(SqQueue &Q,int x) {
	int number;
	printf("请输入要建立的队列元素个数：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("输入第%d个入队的元素：\n",i+1);
		scanf("%d",&x);
		EnterQueue(Q,x);
	}
}

//主函数
int main() {
	SqQueue Q;
	int x,e;
	InitQueue(Q);	//初始化
	CreateQueue(Q,x);	//创建队列
	printf("遍历输出当前队列元素：\n");
	PrintQueue(Q,x);	//遍历输出队列
	printf("\n");
	GetHeadQueue(Q,x);	//读取队列的队头元素
	printf("读取队列的队头元素,当前队头元素为：%d\n",x);
	printf("请输入一个要入队的元素：");
	scanf("%d",&e);
	EnterQueue(Q,e);	//入队 *** 作 
	GetHeadQueue(Q,x);
	printf("读取队列的队头元素,当前队头元素为：%d\n",x);
	PopQueue(Q,x);	//出队 *** 作 
	GetHeadQueue(Q,x);
	printf("执行一次出队 *** 作后,当前队头元素为：%d\n",x);
	printf("遍历输出当前队列元素：\n");
	PrintQueue(Q,x);	//遍历输出队列
}

运行结果如下：