1.队列的概念文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
在开始前，请牢记这句话：队列是一个先进先出的数据结构。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
队列（queue）是限定在表的一端进行插入，表的另一端进行删除的数据结构，如同栈的学习，请联系前文所学链表，试想一个单链表，我们只能对他的链表表尾进行插入，而只能对链表的表头进行结点的删除，其余一切的操作均不允许，这样强限制性的“链表“，就是我们所说的队列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
让我们重新理顺一下定义：队列是一个线性的数据结构，规定这个数据结构只允许在一端进行插入，另一端进行删除，禁止直接访问除这两端以外的一切数据。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
如图：队列就像一个两端相通的水管，只允许一端插入，另一端取出，先放入管中的球先从管中拿出。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
2. 队列的结点设计与初始化文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
队列不如栈那般方便进行模拟，因此队列只有链式的设计方法，但是不同的是，队列本身分为多种队列，如顺序队列（就是此文所讲队列）和循环队列（下一篇文章所讲），以及后文在C++STL章中会提到的优先队列等等，均来自于队列的衍生。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
我们以顺序队列的设计为例。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
首先是队列的结点设计，我们可以设计出两个结构体，一个结构体Node表示结点，其中包含有一个data域和next指针（可以发现，这样的结点设计我们已经重复出现了很多次了，正是因为这样的结构设计方便理解）。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
（图表示结点）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
其中data表示数据，其可以是简单的类型（如int,double等等），也可以是复杂的结构体（struct类型）。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
next指针表示，下一个的指针，其指向下一个结点，通过next指针将各个结点链接。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
如同栈再次设计一个结构体进行限制性设计，接着，我们也额外添加一个结构体，其包括了两个分别永远指向队列的队尾和队头的指针，我们主要的操作只对这两个指针进行操作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
（图表示队列设计）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
其结构体设计的代码可以表示为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
//结点定义typedef struct node{ int data; struct node *next;}node;//队列定义，队首指针和队尾指针typedef struct queue{ node *front; //头指针 node *rear; //尾指针}queue; |
有关初始化，稍微复杂一点的是，我们对于初始化需要初始化两个类型，一个是初始化结点，一个是初始化队列，初始化队列稍微有些不同，那就是当初始化队列的时候，需要将头尾两个结点指向的内容统统制空，表示是一个空队列，两个创建的函数代码可以表示为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
//初始化结点node *init_node(){ node *n=(node*)malloc(sizeof(node)); if(n==NULL){ //建立失败，退出 exit(0); } return n;} //初始化队列queue *init_queue(){ queue *q=(queue*)malloc(sizeof(queue)); if(q==NULL){ //建立失败，退出 exit(0); } //头尾结点均赋值NULL q->front=NULL; q->rear=NULL; return q;} |
3. 判断队列是否为空文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
判断队列是否为空比较简单，直接就是判断队列头指针是否是空值即可（关联如何创建队列可更好理解），判断队列是否为空是比较常用的操作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
其代码可以表示为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
//队列判空int empty(queue *q){ if(q->front==NULL){ return 1; //1--表示真，说明队列非空 }else{ return 0; //0--表示假，说明队列为空 }} |
或者直接利用返回值进行更简单的判断（两者效果完全一样）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25089.html
int empty(queue *q){ return q->front==NULL;} |