顺序队和循环队列，队列篇（顺序队和循环队列入队出队操作）

数据结构专升本学习，队列篇（顺序队和循环队列）

前言：

之前我们把栈学完了，比较简单，今天我们学习队列里面的顺序队和循环队列，说难不难，说简单不简单，我们需要认真学习，博主会尽力把原理和逻辑讲明白，不懂的童鞋可以认真多看几遍，博主真的很想教会大家。希望大家认真看，有问题的地方可以评论提出来，希望大家，喜欢。

每日一遍，防止早恋：

1.什么是队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

1.1认识顺序队列，理解逻辑

顺序队列是队列的顺序存储结构，顺序队列实际上是运算受限的顺序表。和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应设置为0。讲人话就是（一个数组有两个标志，一个在头，一个在尾，头负责输出值，尾负责输入值这两个值最大值就是MaxSize）大致就是这样，在生活中我们学习任何东西，都需要学习它逻辑，才能理解这个东西的含义，方便我们记忆，画一个简单的生活图给大家理解一下

不知道大家有没有喝过茶颜悦色，博主是在长沙的在校大学生，这边茶颜悦色，特别火，每次博主有时间去外面玩会点一杯茶颜悦色，每次去博主就是那个队尾，那个可怜的家伙，去喝茶颜悦色每次都要排队，等博主到队头了，博主就会发现我后面就每没人了，卑微，点一杯“少年时”或者“幽兰拿铁”，你会发现，你还要等，等他出奶茶，这时候你会发现你之前的人也在等而且在你前面，还得排队，哈哈哈，当你喝到的时候会发现等待是值得的。（队列就相当于我们生活中的排队，先来的先买，后来的要排队，等队头买完）。顺序队列比较简单就是头尾自增，然后不管是头还是尾退出条件都是等于MaxSize，可以直接用循环队列的代码来表达顺序表，因为循环队列的最大值(sq.front+1)%MaxSize和MaxSize就小了1，我们就不演示了，重点是循环队列。

1.2理解循环队列，认识我们需要的代码

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

相当于一直在这个队列里面转，可以很方便的节省空间

#define MaxSize 20 //我们队列最大存储个数
typedef struct
{
	int data[MaxSize];
	int front,rear;
}SqQueue;//循环队列是类型
sq.rear =sq.front = 0;//初始化队列头尾
(sq.rear+1)%MaxSize==sq.front//这个是出队时发现队满了往上溢出，只要我们进队了，就可以接着往初始的地方出队
sq.rear==sq.front//这句就是队空往下溢出
sq.rear = (sq.rear+1)%MaxSize;//进队模除相当于循环进一，就相当于往后偏离了一个位置满了就会到队头因为模除
*x =sq.data[(sq.front+1)%MaxSize];//出队模除和进队一样的道理
1
2
3
4
5
6
7
8
9
10
11

上面就是循环队列核心代码。

1.3 循环队列初始化

typedef struct
{
	int data[MaxSize];//定义队列空间大小
	int front,rear;//队头和队尾
}SqQueue;
void InitQueue(SqQueue &sq)
{
	sq.rear =sq.front = 0;//初始化
}
int GetHead(SqQueue sq,int *x)//获取队头的值
{
	if(sq.rear==sq.front)//队空
	{
			return 0;
	}
	*x =sq.data[(sq.front+1)%MaxSize];//取队头的值
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.4循环队列入队

int EnQueue(SqQueue &sq,int x)//入队
{
	if((sq.rear+1)%MaxSize==sq.front)//判断队满
	{
			return 0;
	}
	sq.rear = (sq.rear+1)%MaxSize;//就相当于往上偏离了一个位置满了就会到初始的位置，因为模除循环
	sq.data[sq.rear] = x;//把值写入
	return 1;
}
1
2
3
4
5
6
7
8
9
10

1…5循环队列出队

int DeQueue(SqQueue &sq,int *x)
{
	if(sq.rear==sq.front){//判断队空
			return 0;
	}
	sq.front = (sq.front+1)%MaxSize;//就相当于往下偏离了一个位置满了就会到初始的位置因为模除
	*x =sq.data[sq.front];
	return 1;
}
1
2
3
4
5
6
7
8
9

1.6 循环队列效果演示和整体代码

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 6

typedef struct
{
	int data[MaxSize];
	int front,rear;
}SqQueue;
void InitQueue(SqQueue &sq)
{
	
	sq.rear =sq.front = 0;
}
int EnQueue(SqQueue &sq,int x)
{
	if((sq.rear+1)%MaxSize==sq.front)
	{
			return 0;
	}

	sq.rear = (sq.rear+1)%MaxSize;
	sq.data[sq.rear] = x;
	return 1;
}

int DeQueue(SqQueue &sq,int *x)
{
	if(sq.rear==sq.front){
			return 0;
	}
	sq.front = (sq.front+1)%MaxSize;
	*x =sq.data[sq.front];
	return 1;
}
int GetHead(SqQueue sq,int *x)
{
	if(sq.rear==sq.front)
	{
			return 0;
	}
	*x =sq.data[(sq.front+1)%MaxSize];
	return 1;
}
int QueueEmpty(SqQueue sq)
{
	if(sq.rear==sq.front)return 1;
	return 0; 
}
int main(int argc, char *argv[]) {
	SqQueue sq; 
	int e;
	int i,n,m,num;
	printf("初始化队列\n");
	InitQueue(sq);
	if(QueueEmpty(sq)==1)
	{
		printf("队空\n");
	 } 
	 else{
	 	printf("队不空\n"); 
	 }
	 printf("输入你需要入队的个数(不超过MaXSize：%d)\n",MaxSize);
	 scanf("%d",&n);
	  printf("输入你的%d的值：",n);
	 for(i=0;i<n;i++)
	 {
	 	scanf("%d",&num);
	 	if(EnQueue(sq,num))
	 	{
	 		printf("%d入队成功\n",num);
		 }
		 else{
		 	printf("%d入队失败可能队满了\n",num);
		 }
		 if(i==4){
		 	DeQueue(sq,&e);
	 		printf("出队：%3d\n",e);//队满的时候出一个就又可以进队一个，顺序表是不可以的 
		 }
	 }
	  GetHead(sq,&e);
	 printf("入队完成，队头的值为：%d\n",e);
	 printf("输入出队个数(不超过%d个数)\n",n);
	 scanf("%d",&m);
	 printf("出队的值：") ;
	 for(i=0;i<m;i++)
	 {
	 	if(DeQueue(sq,&e)==1)
	 	{
	 		printf("%3d",e);
	  }
		else
		{
			printf("队空");
		 }
	 }
	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

注意：博主的代码不是用指针所以会报错，需要改为.cpp文件，才可以，或者你改指针然后用”->“访问

总结：

其实队列难度还好和栈有异曲同工之处，只要我们理解了逻辑了，写出来是很容易的，前提是你的知道代码意思，知道代码意思才能用代码来写出你的逻辑，循环队列就是相当于转动的存储器，像生活的水管两头连接，然后里面的水不停的转动。创作不易，点赞，关注，评论，收藏，谢谢啦。不给就哭给你看！！！
上一篇：#数据结构专升本学习，栈篇（链式栈）
下一篇：数据结构专升本学习，队列篇（链式队列）