数据结构专升本学习，队列篇（顺序队和循环队列）
前言：
之前我们把栈学完了，比较简单，今天我们学习队列里面的顺序队和循环队列，说难不难，说简单不简单，我们需要认真学习，博主会尽力把原理和逻辑讲明白，不懂的童鞋可以认真多看几遍，博主真的很想教会大家。希望大家认真看，有问题的地方可以评论提出来，希望大家，喜欢。
每日一遍，防止早恋：
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.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.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…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.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;
}
注意：博主的代码不是用指针所以会报错，需要改为.cpp文件，才可以，或者你改指针然后用”->“访问
总结：
其实队列难度还好和栈有异曲同工之处，只要我们理解了逻辑了，写出来是很容易的，前提是你的知道代码意思，知道代码意思才能用代码来写出你的逻辑，循环队列就是相当于转动的存储器，像生活的水管两头连接，然后里面的水不停的转动。创作不易，点赞，关注，评论，收藏，谢谢啦。不给就哭给你看！！！
上一篇：
#数据结构专升本学习，栈篇（链式栈）
下一篇：
数据结构专升本学习，队列篇（链式队列）
