数据结构之队列定义及基本操作实现
数据结构学着就是有意思，真诚推荐郝斌⽼师的数据结构视频，真的讲解的⾮常详细，容易理解。
⼀直在跟着郝斌⽼师的数据结构视频学习，看完了队列的视频，记录下来，总结⼀下。
队列的定义：队列是⼀种特殊的线性表，只允许在表的头部（front处）进⾏删除操作，在表的尾部（rear处）进⾏插⼊操作的线性数据结构，这种结构就叫做队列。进⾏插⼊操作的⼀端称为队尾，进⾏删除操作的⼀端称为队尾。
队列的类型：链式队列，即⽤链表实现的队列。静态队列：即⽤数组实现的队列。在这⾥，我们采⽤⽤数组实现的静态队列。因为⽤链表实现的队列，是⼀种动态队列，操作更加容易，所以我们这⾥采⽤的是静态队列。
在静态队列中，郝斌⽼师讲的是⼀种更为复杂的静态循环队列。这⾥解释⼀下就是，假如我们采⽤的是静态队列，那就必然涉及到数组，如果我们在不断的从队列中删除数据，那么我们队列的头部（front处）就会不断的向上⾛（在这⾥说明⼀下，队列中front永远指向队列的头部元素，rear永远指向队列的最后⼀个元素的下⼀个元素），这样就会造成我们被删除的位置永远⽆法再被利⽤，就是造成空间的浪费，所以，如果这样，队列这种数据结构也就失去了原本存在的意义。所以，⽤静态数组实现的静态队
列⼀般都是静态循环队列。那么，问题就来了，既然是静态循环队列，什么时候队列才是空呢？什么时候队列才是满呢？
流血不流泪
这⾥⾸先先说⼀下，什么时候队列才能为空，根据我们前⾯的讲解，队列在删除时，front会不断的向上移动，如下⾯的⽰意图：
如上⾯的⽰意图，在初始状态下front和rear都处于0的位置，在插⼊元素时，rear会向上⾛，则填⼊⼀个元素后0的位置就会被填⼊，当再填⼊⼀个元素后1的位置则⼜被填满。此时rear在2的位置，front在0的位置，此时队列中有两个元素，分别位于0和1处。那么，怎么才算是队列为空呢？很简单，就是不断的删除元素，当元素全都被删完了以后就表⽰当前队列为空了。删除0的元素，front将会移动⼀个位置到1，再删除⼀个元素front将会移动⼀个位置到2，此时整个队列中没有元素存在，整个队列就为空。所以，表⽰队列是否为空的条件就是front和rear 处于⼀个位置上。
那么，何时才表⽰当前队列已满呢？可能⼤家也猜出来了，⼤家可能会认为当front和rear在同⼀位置时，整个队列也可以同时表⽰当前队列已满。那就是不断的插⼊元素，rear不断地移动位置，直到rear再次移动到0的位置后，所有的位置都被元素插满，此时整个队列已满。没错，此时整个队列确实已满。但是这样就会和我们的队列为空的条件重复，所以这⾥我们有两种办法来解决这种情况，我们可以定义⼀个表⽰count个数的值，表⽰当前队列中元素的个数。如果front和rear处于同⼀个位置，并
且count为0则队列为空。如果front和rear处于同⼀个位置，并且count不为9，则表⽰当前队列已满。另外⼀个⽅法就是我们默认不全⽤整个属于，我们⽤n-1个元素，这样，当rear和front处
于“紧挨着”的位置时，就表⽰当前队列已满，并且在下标来看，并没有严格的front和rear的⼤⼩关系。
好了，如果前⾯⼤家已经理解，那么，接下来就可以来实现队列的基本操作了（代码都有注释，我就不再详细解释了）。
队列的定义：
1/*
2定义队列
3队列是⼀种只能在⼀段插⼊⼀段删除的数据结构。
4这⾥采⽤静态循环队列，所以队列采⽤数组实现
5*/
6 typedef struct Queue{
7int * pBa; //⽤来存放数组
8int front; //⽤来表⽰当前为front，指向队列头
9int rear; //⽤来表⽰当前为rear，指向队列尾部的下⼀个结点
10 }QUEUE;
队列的初始化操作：⼤家在这⾥也可以将队列的长度作为参数传⼊，我这⾥就直接写了
1/*
家庭火灾2队列初始化函数
3初始化⼀个空队列，就是给出队列⼀个长度，并且⾥⾯没有任何数值
公司推荐信
4*/
5void init(QUEUE *pQ){
6 pQ->pBa=(int *)malloc(sizeof(int)*6); //给出⼀个6个整形长度的队列数组
7 pQ->front=0;
三个强盗8 pQ->rear=0; //将队列初始化为空
9 }
队列的⼊队函数：
1/*
2判断当前队列是否已满的函数
3因为我们默认认为当⼀个n的队列已经存⼊了n-1个值后，就默认它已经满了，不允许它再存储了，所以，
4判断队列是否已满就是判断rear和front是否已经是“紧挨着”，即rear在移动⼀位就会和front重合。
5*/
6int full_queue(QUEUE *pQ){
7if((pQ->rear+1)%6==pQ->front){肝苏胶囊
8return0;
9 }
10el{
11return1;
12 }
13 }
14
电脑如何开热点15/*
16⼊队函数
17根据队列的特性，⼊队只能在队列的尾部，即rear处进⾏，所以⼊队函数的算法就是将被插⼊的数据放在rear的位置
18插⼊完成后rear向后移动⼀位，使rear永远指向队列中最后⼀个元素的下⼀个元素。
19在这⾥有⼀个需要注意的地⽅：在我们移动rear的位置时，如果当前rear的位置已经是数组的最后⼀个位置，应该怎么办？
20就应该让rear在回到0的位置，因为我们的队列默认设置的就是循环队列，也就是说，我们的队列是可以拐弯的，当队列没有满，21但是rear却已经在队列的最后⼀个位置了，那我们就应该在将队列移动到0的位置。这种情形在数学上就是加1取余。
22*/
23int en_queue(QUEUE *pQ, int val){
24if(full_queue(pQ)==0){
25return0;
26 }
27el{
28 pQ->pBa[pQ->rear]=val;
29 pQ->rear=(pQ->rear+1)%6;
30return1;
31 }
32 }
队列的遍历函数：
1/*
2遍历队列的函数
3因为这只是遍历⼀个队列，所以我们不能破坏原有的队列结构，所以，我们必然需要去定义⼀个新的i来表⽰当前所在的下标。 4遍历的语法⾮常简单，就是从头开始，直到队列的末尾，即i到了最后⼀个结点的下⼀个结点（rear处），遍历就算是结束了。
5*/
6void traver_queue(QUEUE *pQ){
7int i=pQ->front; //令i从“头”开始遍历
8
9while(i!=pQ->rear){
10 printf("%d ",pQ->pBa[i]);
11 i=(i+1)%6; //将i向下移动⼀个位置
12 }
13 }
出队函数：
1/*
2当前队列是否为空的函数
3*/
4int empty_queue(QUEUE *pQ){
5if(pQ->front==pQ->rear){
6return0;
7 }
8el{
9return1;
10 }
性的英文11 }
12
13/*
14出队函数
声东击西
15因为出队函数已经破换了队列原有的数据结构，所以我们就没有必要去重新定义⼀个新的下标
16出队函数的算法⾮常简单，就是在队列的头部（front处）进⾏删除，删除之后将front向下移动⼀个位置。
17*/
18int out_quene(QUEUE *pQ,int *pVal){
19if(empty_queue(pQ)==0){
20return1; //1表⽰当前队列为空
21 }
22el{
23 *pVal=pQ->pBa[pQ->front];
24 pQ->front=(pQ->front+1)%6;
25return0; //0表⽰当前当前出队成功
26 }
27 }
上述就是队列的定义及基本操作的代码实现。
本⽂系原创，若转载请标明出处。
