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

一、队列的相关知识

（一）栈和队列的对比

队列与栈一样，它是一种特殊的线性表，其操作受限，它与栈具有相同的逻辑结构，都属于线性结构，区别在于其中元素的处理不同，队列只允许在一端进行插入，且只允许在另一端进行删除，队列遵循的原则是先进先出（FIFO），即先入队列的元素最先离开（最后插入队列中的元素总是最后被删除），与日常生活中的排队是一样的。

例如下图是一个队列，只允许一端进入（入队），另一端退出（出队）：

（二）队列的存储结构

队列有两种方式存储队列，基于顺序存储结构和链式存储结构，即顺序队列和链队列。
1、循环队列
若将顺序队列的一维数组首尾相连形成一个环状，即为循环队列，下图是一个循环队列且MaxSize=7，初始条件时循环队列为空，其队头指针等于队尾指针，即Q.front=Q.rear，如下：

2、双端队列
双端队列允许队列在两端都可以进行入队（插入）和出队（删除）操作，如下图：

同样，若限制一端的入队或出队，又可分为输入受限的双端队列和输出受限的双端队列，例如在输入受限的双端队列中，只允许在一端进行入队和出队，而另一端只能出队。

（三）队列的应用

队列的应用场景有以下：
（1）缓冲区（例如计算机与打印机中间的打印数据缓冲区）；
（2）页面替换算法；
（3）图的广度优先搜索、树的层次遍历，都借助到了队列的基本思想。

三、顺序队列的代码实现

（一）顺序队列的定义

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

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

（二）顺序队列的初始化

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

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

（三）判空操作

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

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

（四）判满操作

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

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

（五）入队（插入操作）

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

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

以上这两行代码也可以通过一行代码简化，即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
2
3
4
5
6
7
8
9

（六）出队（删除操作）

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

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

以上这两行代码也可以通过一行代码简化，即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;	
}
1
2
3
4
5
6
7
8
9

（七）读取顺序队列队头元素

读取当前顺序队列队头元素，并不是取出该队头元素，首先判断队列是否为空，因为队头指针为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;
}
1
2
3
4
5
6
7

（八）顺序队列的遍历输出

顺序队列的遍历输出中，首先判断队列是否为空，然后通过一个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;
}
1
2
3
4
5
6
7
8
9
10

（九）顺序队列的建立

顺序队列的建立程序代码中通过输入一个值表示要创建的顺序队列的元素个数，然后通过一个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);
	}
}
1
2
3
4
5
6
7
8
9
10
11

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

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

#include<stdio.h>
#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
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

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

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

代码如下：

#include<stdio.h>
#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);	//遍历输出队列
}
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

运行结果如下：