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

作者：IC00

2022-10-12
湖南
本文字数：2850 字
阅读完需：约 9 分钟

前言：

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

每日一遍，防止早恋：

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 文件，才可以，或者你改指针然后用”->“访问

总结：

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

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/ce65d6cfb421ecedf255e29a7】。文章转载请联系作者。

IC00

关注

一个热爱生活，喜欢拍照的热血青年 2022-07-14 加入

一个想学习技术的小盆友，想努力更文，争取今年发100篇

发布

暂无评论

创作场景

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

前言：

每日一遍，防止早恋：

1.什么是队列

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

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

1.3 循环队列初始化

1.4 循环队列入队

1..5 循环队列出队

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

总结：

IC00

评论