队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。
以下为公用代码：
typedef int Status; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int QElemType;
一、队列的顺序存储（循环队列）
把队列的头尾相接的顺序存储结构称为循环队列。
为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。
知识重点：
设队列的最大尺寸为QueueSize，则
空队列的条件：front == rear
队列满的条件：(rear + 1) % QueueSize == front （取模是为了整合rear与front大小为一个问题）
队列长度计算：(rear - front + QueueSize) % QueueSize
1、存储结构
#define MAXSIZE 5
// 循环队列的顺序存储结构
typedef struct
{
QElemType data[MAXSIZE];
int front;// 头指针
int rear;// 尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;2、初始化
// 初始化一个空队列
Status InitQueue(SqQueue *Q)
{
Q->front = 0;
Q->rear = 0;
return OK;
}代码分析：空队列时，front与rear指针相等且均指向下标为0的位置。
3、求队列长度
// 返回Q的元素个数，也就是队列的当前长度
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}代码分析：见前文所述队列长度的计算。
4、入队列操作
// 若队列未满，则插入元素e为新的队尾元素
Status EnQueue(SqQueue *Q, QElemType e)
{
if((Q->rear + 1) % MAXSIZE == Q->front)// 判断队列是否已满
return ERROR;
Q->data[Q->rear] = e;// 元素e的值赋给队尾
Q->rear = (Q->rear + 1) % MAXSIZE;// rear指针后移一位，若到最后则转到数组头部
return OK;
}算法分析：
(1)、入队前先判断队列是否已满，判断条件见前文所述；
(2)、新元素的值赋给队尾空间；
(3)、rear指针后移一位，若到最后则转到数组头部。
5、出队列操作
// 若队列不空，则删除队头元素，用e返回其值
Status DeQueue(SqQueue *Q, QElemType *e)
{
if(Q->rear == Q->front)// 判断队列是否为空
return ERROR;
*e = Q->data[Q->front];// 将队头元素值赋给e
Q->front = (Q->front + 1) % MAXSIZE;// front指针后移一位，若到最后则转到数组头部
return OK;
}算法分析：
(1)、出队前先判断队列是否为空，判断条件见前文所述；
(2)、把将要删除的队头元素的值赋给e；
(3)、front指针后移一位，若到最后则转到数组头部。
二、队列的链式存储
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点（这里的头结点是指队头结点的前一个结点），而队尾指针指向终端结点。
空队列时，front和rear都指向头结点，即front == rear。
1、存储结构
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front, rear;
}LinkQueue;2、入队操作
// 插入元素e为新的队尾元素
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));// 分配失败时返回NULL指针
if(!s)// 存储分配失败
exit(OVERFLOW);// exit定义在<stdlib.h>中，OVERFLOW定义在<math.h>中
s->data = e;
s->next = NULL;
Q->rear->next = s;// 把新结点s赋值给原队尾结点的后继
Q->rear = s;// 把s设为队尾结点，rear指向s
return OK;
}算法分析：
(1)、首先分配一个存储空间s；
(2)、判断s是否分配成功；
(3)、把新元素值e赋给s的数据域；
(4)、s的指针域置空；
(5)、把新结点s赋给原队尾结点的后继；
(6)、把新结点s设为队尾结点，rear指向s。
3、出队操作：出队列时，就是头结点的后继结点出队。若链表除头结点外只剩一个元素，则需将rear指向头结点。
// 若队列不为空，删除队头元素，用e返回其值
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if(Q->front == Q->rear)// 判断队列是否为空
return ERROR;
p = Q->front->next;// 将要删除的队头结点暂存给p
*e = p->data;// 将要删除的结点的数据赋给e
Q->front->next = p->next;// 将原来队头结点的后继赋给头结点的后继
if(Q->rear == p)// 若队头是队尾，则删除后将rear指向头结点
Q->rear = Q->front;
free(p);// 释放p
return OK;
}算法分析：
(1)、声明一指针p；
(2)、出队前先判断队列是否为空，条件如前文所述；
(3)、将要删除的队头结点暂存给p；
(4)、将要删除的结点的数据赋给e；
(5)、将p的后继赋给头结点的后继；
(6)、若队头也是队尾，则删除后将rear指向头结点；
(7)、释放p。
总结：在可以确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列长度，则应用链队列。
三、sizeof与malloc()
sizeof是一个关键字，它的作用是求它的操作数的类型长度，以字节为单位表示。当sizeof的操作数是个数组名时，它返回该数组的长度，以字节为单位。
malloc()是一个函数，它的作用是分配一块内存，并返回一个指向这块内存的指针。
函数原形如下，声明于头文件<stdlib.h>中
void *malloc(size_t size); // size_t是一个无符号类型，定义于stdlib.h
malloc()的参数就是需要分配的内存字节数。如果内存池中的可用内存可以满足这个需求，malloc()就返回一个指向被分配的内存块起始位置的指针，其类型为 void * —— C标准表示一个void * 类型的指针可以转换为其他任何类型的指针。
如果操作系统无法向malloc()提供它所需要的内存，malloc()就返回一个NULL指针。因此，对每个从malloc()返回的指针进行检查，确保它并非NULL是非常重要的。
