类似于栈，队列也是一种特殊的数据结构，其底层的结构仍是顺序表和链表。
目录
1 队列的概念与特点
1） 概念
2） 特点
2 队列的结构
1） 逻辑结构
2） 物理结构
3 队列的实现
1） 初始化队列和销毁队列
（1） 初始化队列
（2） 销毁队列
2） 入队和出队
（1） 入队
（2） 出队
3） 取队头与队尾元素
4） 判空和返回有效元素个数
4 代码
重点一 队列的特点1 队列的概念与特点
1） 概念
队列是一种特殊的线性表。其只允许在一端进行插入数据，另一端进行删除数据。
入队：是向队列中插入数据的过程。插入数据的一端叫做队尾。
出队：是在队列中删除数据的过程。删除数据的一端叫做队头。
其实队列数据结构就像现实生活中排队时的队列，一个一个的数据就像排队的人，你要排队的时候就要从队尾排队，所以插入数据的一端就是队尾；同样的，如果你要离开队列，就要从队头离开，所以删除数据的一端叫做队头。
2） 特点
队列的特点与现实中的队列相同。先入队的肯定先出队，所以数据结构队列具有FIFO（first in first out）-- 先进先出的特点（正好与栈相反）。
重点二 队列的结构2 队列的结构
1） 逻辑结构
我们可以把队列想象成以下的结构：
2） 物理结构
队列的物理结构既可以使用链表，也可以使用数组（顺序表），这里选择使用链表来实现队列的结构（这里为了简化结构，使用单链表来实现）。
物理结构使用链表是基于其特点来选择的：队列符合先进先出的特点，如果选择数组的话，需要在尾部插入数据，在头部删除数据，虽然插入数据的时间复杂度为O(1)，但是删除数据的时候，需要频繁挪动数据，时间复杂度为O(n)，不是很方便，所以这里选择使用链表来作为其底层结构。
但是链表的尾插仍然是O(n)，时间复杂度较高，所以这里会优化其结构，并不单单使用单链表。尾插的时间复杂度为O(n)，究其原因是因为需要从首节点开始遍历整个链表找到尾节点，所以在实现队列的结构的结构时，不仅需要有节点的结构，还需要有两个指针来指向队列的头和尾，方便进行数据的插入和删除。
队列的结构如下：
typedef int QDataType;
//定义队列结点的结构
typedef struct QueueNode
{QDataType data;//队列结点里的数据struct QueueNode* next;//指向下一个结点的指针
}QNode;
//定义队列的结构
typedef struct Queue
{QNode* phead;//对头，允许删除数据QNode* ptail;//队尾，允许插入数据
}Queue;3 队列的实现
队列相关的操作主要有初始化队列、销毁队列、入队、出队、取队头元素、取队尾元素、判空以及有效元素的个数。
1） 初始化队列和销毁队列
（1） 初始化队列
初始化队列比较简单，只需要让队头和队尾指针指向 NULL 就可以了。
（2） 销毁队列
由于队列是以单链表作为底层结构的，所以其销毁就类似于单链表的销毁。这里定义一个 pcur 指针来指向队列的队头节点，然后循环判断 pcur 是否为 NULL（是否走到尾节点），在循环中保存 pcur 下一个节点的指针，然后释放 pcur 当前指向的节点，让 pcur 走到下一个节点，最后不要忘记让 phead 和 ptail （队头指针和队尾指针）都指向空，不然会变成野指针。
当然，也可以判断 pcur 是否等于 ptail (队尾指针)，但是循环结束后，还需要释放队尾指针指向的节点。最后也不要忘记让 phead 和 ptail 都指向NULL。
2） 入队和出队
（1） 入队
入队是在队尾插入数据，所以就相当于单链表的尾插，之前单链表的尾插需要从头节点找到尾节点，但是在队列里面，尾插可以直接找到尾节点，就是 patil 节点，入队的过程如图所示：
这里需要判断一下特殊情况，就是队列为空（phead == NULL）的情况，此时 phead 与 ptail 都指向NULL，这样在改变 ptail 指向节点的 next 指针的时候，就会发生对 NULL 指针的解引用，会报错，所以为空时需要特殊处理一下：开辟一个新节点newnode，让 phead 和 ptail 都指向 newnode就可以了。
（2） 出队
出队就是单链表的头删，既然是删除数据，就需要在出队之前首先判断队列为不为空，出队的过程如图所示：
但是有一个特殊情况需要特殊处理一下，就是队列中只有一个节点的情况，虽然不会出现对 NULL 指针的解引用情况，但是此时队列为空了，但是 ptail 还指向已经释放了的节点，已经变成了野指针，所以需要把 ptail 也变为 NULL。
3） 取队头与队尾元素
这两个接口很简单，取队头元素只需要返回 phead 指向节点的 data 数据就可以了，取队尾元素只需要返回 ptail 指向节点的 data 数据。但是，在这之前需要先判断队列是否非空，如果是空队列，那么 phead 和 ptail 就是 NULL，访问 data 数据会发生对 NULL 指针的解引用的。
4） 判空和返回有效元素个数
判空很简单，只需要判断 phead 是否为 NULL 就可以了。
返回有效元素个数也很简单，但是这里注意不能用 ptail - phead 来计算元素个数，因为其地址并不是连续的。这里应该用一个计数器 count 来记录元素个数，然后用一个指针变量 pcur 来遍历队列，遍历完后返回 count 即可。
当然，如果这样写其时间复杂度就是 O(n)，如果想要时间复杂度变为 O(1) 的话，可以在队列之中添加一个 size 变量：
typedef struct Queue
{QNode* phead;//队头指针QNode* ptail;//队尾指针size_t size;//有效元素个数
}Queue;这样设计结构的话，只需要返回 size 就可以了。但是这样写不要忘记在入队时 ++size ，在出队时 --size。
4 代码
Queue.h文件：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;
}Queue;//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//取队头元素
QDataType QueueFront(Queue* pq);
//取队尾元素
QDataType QueueBack(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);Queue.c文件：
#include"Queue.h"//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;
}//销毁队列
//1
//void QueueDestroy(Queue* pq)
//{
// assert(pq);
// //相当于单链表的销毁
// QNode* pcur = pq->phead;
// while (pcur != pq->ptail)
// {
// QNode* next = pcur->next;
// free(pcur);
// pcur = next;
// }
// //不要忘记释放队尾指针指向节点
// free(pq->ptail);
// pq->phead = pq->ptail = NULL;
//}//2
void QueueDestroy(Queue* pq)
{assert(pq);//相当于单链表的销毁QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;
}//入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//相当于单链表的尾插if (pq->phead == NULL){QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail！\n");exit(1);}newnode->data = x;newnode->next = NULL;pq->phead = pq->ptail = newnode;}else{//开辟一个新结点QNode* newnode = (QNode*)malloc(sizeof(QNode));//可以再判断newnode有效性，这里就不判断了newnode->data = x;newnode->next = NULL;pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}
}
//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);//只需判断pq->phead指针为不为空return pq->phead == NULL;
}//出队
void QueuePop(Queue* pq)
{//出队首先要判断队列为不为空assert(!QueueEmpty(pq));//相当于单链表的头删//只有一个结点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//多个结点QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}}//取队头元素
QDataType QueueFront(Queue* pq)
{//判断队列为不为空assert(!QueueEmpty(pq));//返回队头指针所指向结点的数据return pq->phead->data;
}//取队尾元素
QDataType QueueBack(Queue* pq)
{//判断队列为不为空assert(!QueueEmpty(pq));//返回队尾指针所指向结点的数据return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);//创建一个计数器变量int count = 0;QNode* pcur = pq->phead;while (pcur){pcur = pcur->next;count++;}return count;
}test.c文件：
#include"Queue.h"void Test5()
{Queue q;QueueInit(&q);//测试入队QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);//测试取对头元素与取队尾元素/*QDataType ret1 = QueueFront(&q);printf("%d\n", ret1);QDataType ret2 = QueueBack(&q);printf("%d\n", ret2);*///测试出队QueuePop(&q);QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);QDataType ret1 = QueueFront(&q);printf("%d\n", ret1);QDataType ret2 = QueueBack(&q);printf("%d\n", ret2);int size = QueueSize(&q);printf("%d\n", size);QueueDestroy(&q);
}int main()
{Test5();return 0;
}
可以看到，队列基本上就是单链表的复现，只不过增加了一个队头指针和队尾指针，相信在理解了单链表的基础上，队列也就很简单了。
