哎，又是你们，都快双11了，打赏一下小编吧。

言归正传，今天我们讲讲链队列，头文件那些上次讲过了，差不多，我就不再赘述了。

我们先讲讲队列的特性：先进先出

在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。

如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。


为了实现插入和删除操作，我们需要用到一个数组来存储元素和指针移到，另外还需要两个指针front和rear来表示队列的头部和尾部（所以其实我们可以把它当成循环队列来理解。）

那么目标明确了，就先定义结构体了。

typedef struct node
{
　　elemtype data;                             //元素
　　struct node *next;                         //移到的指针设置
}QNode,*queuenode;                          //QNode是数组，后面那个就是数组的指针形式了，可以这么理解的，名称自己随意了，最好是能表达意思的那种
typedef struct
{
　　queuenode front, rear;                  //这里的定义其实是多变的，但是归根结底还是要把这两个设置为指针型。
}linkqueue;                                           //这里的定义其实也是多变的，你可以定义为指针型，都OK的，但是数组简单一点，就这样了。

1，插入（也就是入队）

这里补充一下，为什么今天没有定义函数了呢，因为队列的定义相对简单，直接在主函数里实现就好了。（但还是要尽可能的保持主函数的简洁性）

再来剖析一下入队操作：1，基础的分配空间；2，插入必备的赋值，和地址转换

status enqueue(linkqueue *Q, elemtype e){                    //可能有同学会问，为什么我的是*Q，因为我上面的第二个数组我只设置了数组类型名，我想用地址来                                                                                                   做，所以就加*号了，这里看大家习惯了。除此之外，我这里讲一下，不知道讲过没有，还是讲一下，数                                                                                             组的指针的引用区别：数组是加“.” ，而指针则是用“->” 。
queuenode p;
p=(queuenode) malloc (sizeof (QNode));
if(!p) exit (ERROR);
p->data = e;
p->next = NULL;                                                              //大家还没有忘记我们上面放的那个图吧，队列是先进先出，所以它的插入都是插在后面，也就是说插进                                                                                               来的那个元素的next始终指向NULL。
Q->rear->next = p;                                                           //这里有没有那个小伙伴有问题的啊，好，没有，下一个
Q->rear = p;                                                                      //开玩笑开玩笑，为什么这里会用rear呢，按理来说，插入不是应该要头结点的next吗？大家再好好想一                                                                                                想我们一开始的那个图，队列是先进先出，也就是说只有队尾是在移动的，是能够用了插入的，你一直                                                                                              用front那岂不是每次插入的都是同一个位置，是吧，当然，你可以再中间断开，但那样麻烦的十我是不                                                                                              会做的。
return OK;                                                                          //想必有小伙伴已经发现了一个问题了，嘿嘿，我先不说
}

2，删除（也就是出队）

剖析剖析，删除之基本操作：1，弹出去一个元素，其他的补上去，呸，我呸，知不知道那样的时间复杂度为O（n），队列队列，一开始设置那个头结点用来干什么的，好看的吗（当然不包括上面发现问题的同学们的那个东西），这时我们就可以通过移动头结点来进行删除操作了，这样的时间复杂度就少了太多了，2，切记要free空间，虽然系统自己会清理掉，但写出来就是加分项哦

status dequeue(linkqueue *Q, elemtype *e){                        //Q我不管你们怎么定义了，但是e一定要用指针，其实要作出改变的对象应该都要用*的，也就是指针                                                                                                    了（好习惯）
queuenode p;
if(Q->front == Q->rear) return ERROR;                                 //好了好了，现在我们来说说上面发现的那个问题，我一开始是不是说了这是一个循环队列，循环循                                                                                                      环，那是不是总有一天front会跟rear碰上，这就是一个目前为止最能体现出插人函数分配空间的用处                                                                                                    的了，因为每次插入，我们都会给它分配空间，所以它是可以无限插入直到电脑不行了的。

                                                                                                //那碰上了，怎么办。碰上了就代表到头了，也就是循环一遍了，那删除一开始，还没开始动，就到                                                                                                      头了，那肯定就是一个空队列了，就要退出了。
p = Q->front->next;                                                                  //移移移移动头结点
*e = p->data;
Q->front->next = p->next;                                                        //这里是必须要指一下next的哦，大家还记得链表吗，头结点位于第一个元素前面一点点
if(Q->rear ==p)Q->rear = Q->front;                                          //这里是什么意思，就是代表着队列里只有一个元素
free(p);
return OK;
}

好了好了，插入和删除就到这里结束了，再给大家讲一下print函数吧

剖析again，怎么输出呢，有很多方法：1，从头结点开始遍历，2，我们一开始不是有定义一个数组吗，可以通过数组输出，3，因为是循环队列，从队尾开始也是OK的。（这里讲讲第一种，比较常用的）

void printf_Q(linkqueue Q){
int i;
Q.front=Q.front->next;                                          //注意一开始必须要指一下next，原因上面讲过了
if(Q.front==Q.rear) return ERROR;                      //一样的，空就退出
for(i=0;;i++){
printf(“%d “,Q.front->data);                                   //输出就很简单了，因为结点也是定义的数组指针，所以直接值向data就好了
if(Q.front!=Q.rear)                                                 //直到他们碰上，就代表已经循环了一遍了
Q.front=Q.front->next;
else
break;
}

}

老师还有布置一个返回长度的函数吧，那个跟print其实差不多，就不赘述了。

大家，下次再见吧（再说）！！！