队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。
与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出
队列存储结构
通常，称进数据的一端为 "队尾"，出数据的一端为 "队头"，数据元素进队列的过程称为 "入队"，出队列的过程称为 "出队"。
不仅如此，队列中数据的进出要遵循 "先进先出" 的原则，即最先进队列的数据元素，同样要最先出队列。拿图 1 中的队列来说，从数据在队列中的存储状态可以分析出，元素 1 最先进队，其次是元素 2，最后是元素 3。此时如果将元素 3 出队，根据队列 "先进先出" 的特点，元素 1 要先出队列，元素 2 再出队列，最后才轮到元素 3 出队列。
栈和队列不要混淆，栈结构是一端封口，特点是"先进后出"；而队列的两端全是开口，特点是"先进先出"。
因此，数据从表的一端进，从另一端出，且遵循 "先进先出" 原则的线性存储结构就是队列。
队列存储结构的实现有以下两种方式：
- 顺序队列：在顺序表的基础上实现的队列结构；
- 链队列：在链表的基础上实现的队列结构；
空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
实际生活中，队列的应用随处可见，比如排队买东西 、医院的挂号系统等，采用的都是队列的结构。
拿排队买票来说，所有的人排成一队，先到者排的就靠前，后到者只能从队尾排队等待，队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后，才轮到自己买票。这就不是典型的队列结构吗？
?
?顺序队列
即采用顺序表模拟实现的队列结构。
我们知道，队列具有以下两个特点：
- 数据从队列的一端进，另一端出；
- 数据的入队和出队遵循"先进先出"的原则；
因此，只要使用顺序表按以上两个要求操作数据，即可实现顺序队列。
顺序队列简单实现
由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素，如图 1 所示：
?
?
图 1 顺序队列实现示意图
由于顺序队列初始状态没有存储任何元素，因此 top 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。
在图 1 的基础上，当有数据元素进队列时，对应的实现操作是将其存储在指针 rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 top+1 操作。
例如，在图 1 基础上将?{1,2,3,4}?用顺序队列存储的实现操作如图 2 所示：
?
?
图 2 数据进顺序队列的过程实现示意图
在图 2 基础上，顺序队列中数据出队列的实现过程如图 3 所示：
?
图 3 数据出顺序队列的过程示意图
但我们一般只使用链表实现队列，这里还是给大噶介绍一下，用顺序表实现队列的大致过程.
链表队列
简称"链队列"，即使用链表实现的队列存储结构。
链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素，如图 1 所示:
图 1 链式队列的初始状态
?
图 1 所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。
在创建链式队列时，强烈建议初学者创建一个带有头节点的链表，这样实现链式队列会更简单。
由此，我们可以编写出创建链式队列的 C 语言实现代码为:
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* rear;
}Queue;
//队列初始化
void QueueInit(Queue* q)
{
q->front = NULL;
q->rear = NULL;
}
链式队列数据入队
链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：
- 将该数据元素用节点包裹，例如新节点名称为 elem；
- 与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
- 最后移动 rear 指针指向该新节点，即 rear=elem；
由此，新节点就入队成功了。
例如，在图 1 的基础上，我们依次将?{1,2,3}?依次入队，各个数据元素入队的过程如图 2 所示:
?
?
图 2 {1,2,3} 入链式队列
数据元素入链式队列的 C 语言实现代码为：
void QueuePush(Queue* q, QDataType data)
{
assert(q);
//1、用节点包裹入队元素
QNode* newNode = (QNode*)malloc(sizeof(QNode));
assert(newNode);
newNode->next = NULL;
newNode->data = data;
//2、新节点与rear节点建立逻辑关系
if (q->rear == NULL)
{
assert(q->front == NULL);
q->front = q->rear = newNode;
}
else
{
q->rear->next = newNode;
q->rear = newNode;
}
}链式队列数据出队
当链式队列中，有数据元素需要出队时，按照 "先进先出" 的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。
链式队列中队头元素出队，需要做以下 3 步操作：
- 通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
- 将 p 节点（即要出队的队头节点）从链表中摘除；
- 释放节点 p，回收其所占的内存空间；
例如，在图 2b) 的基础上，我们将元素 1 和 2 出队，则操作过程如图 3 所示：
?
图 3 链式队列中数据元素出队
链式队列中队头元素出队的 C 语言实现代码为：
void QueuePop(Queue* q)
{
assert(q);
assert(q->front && q->rear);
//只有一个节点需要特殊处理
if (q->front->next == NULL)
{
free(q->front);
q->front = q->rear = NULL;
}
else
{
QNode* next = q->front->next;
free(q->front);
q->front = next;
}
}
这次的文章到这里就结束了，谢谢大噶观看，点个蛋吧~
?
