队列是个很常见的数据结构，我来简单介绍一下。从链队列入手，之后再介绍顺序队列，环形队列，双端队列等。全程用C语言描述，并养成画逻辑图的好习惯。
我先引用头文件，定义宏。后续有开空间的操作要引用 stdlib.h，宏可以增强代码的可读性。
#include<stdio.h> #include<stdlib.h> #define OK 0 #define ERR -1
队列是一种先进先出的数据结构。栈是一个桶，我们把序号为 1、2、3 的节点依次放进桶里保存，取节点时从最外面的 3 开始取；而队列是一个通道，如果将 1、2、3 节点依次存在队列中，取数据时就要到通道的另一侧，从 1 开始取。
队列节点的结构如下：
/* 队列节点结构 */
typedef struct QNode
{
//队列节点数据域
int data;
//队列节点指针域
struct QNode *link;
} QNode, *QueuePtr;
最简单的链队列具有两个指针 — 队头指针和队尾指针。构造空的链队列时，这两个指针都指向一个指针域为空的节点，即链队列的头节点。
注意下面代码中函数的参数是结构体 Q 的地址 &Q，为什么这里不直接用 Q ? 这里用到了C++的引用，作用是避免了指针的使用。
/* 链队列结构 */
typedef struct Queue
{
// front指向队列首元素
QueuePtr front;
// rear指向队列末尾元素
QueuePtr rear;
} LinkQueue;
/* 构造空链表 */
int initQueue(LinkQueue &Q)
{
//构造空链表时，这两个指针都需要开辟空间，并且都指向一个空节点，即头节点
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if(Q.front == NULL)
return ERR;
//置空头指针指向的节点的指针域，即头节点的指针域不能乱指，应该指向空
Q.front->link = NULL;
return OK;
}
链队列的基本操作 ——> 创造一个新节点，让该节点入队：
/* 链队列 元素入队 */
int statusEnQueue(LinkQueue &Q, int e)
{
//首先声明一个指向某个节点的指针p，让他指向空
QNode *p = NULL;
//给p指针指向的区域开辟空间，之前p指向空，赋值后指向的区域大小等于一个节点的大小
p = (QNode *)malloc(sizeof(QNode));
if(p == NULL)
return ERR;
//p指针指向的节点数据域赋值为e
p->data = e;
//p指针指向的节点指针域置空，因为不置空会可能会指向一个随机地址
p->link = NULL;
//队列尾节点指向新节点p
Q.rear->link = p;
//队尾指针指向新节点p,即p成为了新的队尾节点
Q.rear = p;
return OK;
}
链队列的基本操作 ——> 节点出队。简而言之是让头节点指向第二个节点。
/* 链队列 元素出队 */
int exitQueue(LinkQueue &Q)
{
QNode *p = NULL;
/* 判断队列是否为空(当且仅当队列为空时,队列头指针和尾指针都指向队列头节点) */
if (Q.front == Q.rear)
{
printf("no elements in Queue");
return ERR;
}
/* 找到队列第一个元素，即头节点的下一个元素 */
p = Q.front->link;
/* 头节点指针指向从头节点往后数的第二个节点，实现头节点下一个节点出队,即去除队列的第一个元素 */
Q.front->link = p->link;
/* 易错点:出队之后,如果队列为空,说明尾指针还指着出队的节点,需要让它指向头节点 */
if (Q.rear == p)
Q.front = Q.rear;
/* 释放出队的节点。如果要用出队的这个节点，就不用free了，但记得不释放的话 p->link 还在指向第二个节点，记得改一下，可见画图很重要，没画图这个指针可能就忘记处理了 */
free(p);
return OK;
}
看到这儿·，可能有人会有个问题，如果队列中只有一个元素，那么刚才 Q.front->link = p->link 这行代码，我们让第二个元素变成了第一个元素，但是第二个元素根本就不存在啊，这是怎么回事？
第二个元素虽然不存在，但这行代码的含义是将 p 节点的指针域赋给头节点的指针域，所以 p 节点的指针域可以是空嘛。p->link 是 p 指针指向的节点的指针域里存放的地址，而不是 p 指针指向的节点的下一个节点，这个问题就是概念不清导致的。
参考资料：《数据结构与算法考研复习指导》— 王道考研系列
