前言：在我们学习了栈之后，明白了它的结构的特殊性即LAST IN FIRST OUT(后进先出)，与之相对应的也有一个特殊的结构队列（queue）--FIRST IN FIRST OUT(先进先出)，他们都是面对特殊情况下的数据的结构，那么队列有是如何实现的呢，是用来干嘛的呢？
1.什么是队列？
队列是一种先进先出的、操作受限的线性表。它的想法来自于生活中排队的策略，先来的元素先出去，后来的元素后出去。队列可以用数组或链表来实现，也有循环队列和优先队列等特殊类型，考虑到队列的先进先出的特点，即数据的头删尾插，我们选择用链表来实现队列，这里选用单链表即可。
队列的模型图：
日常生活中我们排队在餐厅门口处取餐，挂号都是一种队列的模型。
2.队列的实现
1.结构体与函数接口
和栈相反，对于队列因为只允许操作队头与队尾，我们除了创建单链表的结构体外，还创建了一个结构体表示队列，包含队头节点，队尾节点，以及队长，故这里的单链表结构体相当于是为我们提供节点，实现队列是在此基础上的该队列结构体。
其次便是实现的一些基本功能的接口。队列的实现整体较为简单，我们这里还是以存放整数为例。
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdbool.h> #include<assert.h> #include<stdlib.h> typedef int queDATAtype; typedef struct Queuenode { struct Queuenode* next; queDATAtype data; }QUE; typedef struct QUEue { QUE* front; QUE* tail; int size; }LTnode; void Queueinit(LTnode* p);//初始化队列 void Queuedestroy(LTnode* p);//销毁队列 void LTpush(LTnode* p,int x);//尾插 void LTpop(LTnode* p);//头删 int LTfront(LTnode* p);//返回队头 int LTtail(LTnode* p);//返回队尾 int LTsize(LTnode* p);//返回队长 bool LTempety(LTnode* p);//判空队
2.初始化队列
初始化队列很简单，即我们的队头与队尾此时皆为空，长度为零。
//初始化 void Queueinit(LTnode* p) { assert(p); p->front = NULL; p->tail = NULL; p->size = 0; }
3.销毁队列
即从头开始遍历队列，不为空则释放，然后指向下一节点，（与头删一样，我们先保存下一节点，在释放）直到头尾节点皆被释放，之后置空，长度归零。
void Queuedestroy(LTnode* p) { assert(p); QUE* cur = p->front; while (cur) { QUE* next =cur->next; free(cur);; cur = next; } p->front = p->tail = NULL; p->size = 0; }
4.入队
入队即尾插，因为这里是无哨兵位的单链表，因此在判空队列之后，我们先开辟出节点空间并初始化为要插入的节点，然后再判断若为空节点，即没有元素，那么队头节点与队尾节点相等并为该插入的新节点，否则，就是尾插--与单链表操作类似，链接尾节点的next，之后成为新的尾节点。插入之后，记得队长加一。
void LTpush(LTnode* p, int x) { QUE*newnode=(QUE*)malloc(sizeof(QUE)); if (newnode == NULL) { return; perror("malloc fail"); } assert(p); newnode->next = NULL; newnode->data = x; if (p->front ==NULL ) { assert(p->tail==NULL); p->front = p->tail = newnode; p->size++; } else { p->tail->next = newnode; p->tail = newnode; p->size++; } }
5.出队
出队，即头删，因此我们先判空队列之后，在判断是否有元素，即头尾指针不同时为零。头删时要分两种情况：1.只有一个元素时头删，这时我们要将头尾指针同时free置空。2.多个元素头删，保存头结点的下一个，free头节点，成为新的头节点。
void LTpop(LTnode* p)//头删 { assert(p); assert(!LTempety(p)); if (p->front ->next==NULL) { free(p->front); p->front = NULL; p->tail = NULL; } else { QUE* cur = p->front->next; free(p->front); p->front = cur; } p->size--; }
以下四个操作较为简单，不做表述：
6.返回队头
int LTfront(LTnode* p) { assert(p); assert(!LTempety(p)); return p->front->data; }
7.返回队尾
int LTtail(LTnode* p) { assert(p); return p->tail->data; }
8.返回长度
int LTsize(LTnode* p) { assert(p); return p->size; }
9.判空队列
bool LTempety(LTnode* p) { assert(p); return p->size == 0; }
注意事项
这里需要注意的一点是，我们一般是不会对栈与队列的某个元素进行访问，必须遵循该结构对数据的操作方式，即数据只能先进先出。我们遍历数据也是如此：
int main() { LTnode n; Queueinit(&n); LTpush(&n, 1); LTpush(&n, 2); LTpush(&n, 3); while (!LTempety(&n)) { printf("%d ", LTfront(&n)); LTpop(&n); } Queuedestroy(&n); return 0; }
3.队列的用处
队列结构下的应用是指利用队列的特点来解决一些实际问题或算法问题。例如：
1.队列可以用来模拟排队等待的场景。
2.也可以用来实现广度优先搜索算法。
3.可以用来设计一些特殊的队列，如单调队列、优先队列等，来处理区间最值、滑动窗口等问题。
