队列具有先进先出的特点：在队头删除数据（出队），在队尾插入数据（进队）；
什么是设计队列？它有什么独特的特点？
- 离散事件的模拟（模拟离散事件的先后顺序，如CPU中的指令译码队列）
- 操作系统中的作业调度（一个CPU操作多个作业）
- 简化程序设计
队列的基本操作：
- 构建一个空队列(InitQueue(Q));
- 判断队列是否为空(QueueEmpty(Q));
- 求队列的长度（QueueLength(Q)）;
- 返回队列的队头元素，不改变队列的状态（GetQueueHead(Q)）;
- 插入元素x作为Q的新的队尾元素（EnQueue(Q,x)）;
- 删除队列的队头元素DeQueue(Q);
- 清除队列的所有元素（ClearQueue(Q)）;
链队列的定义：
为了操作方便，我们给链队列添加一个头结点（不存数据,即空结点），并令头指针指向头节点，尾指针指向真正的队尾元素结点。因此判断链队列为空的条件就是队头指针和队尾指针均指向头结点。
链表中结点的定义
typedef struct Qnode
{
datatype data;
struct Qnode *next;
}Qnode;
链队列类型定义：(头结点)
typedef struct
{
Qnode *front;
Qnode *rear;
}LinkQueue;
（1）构建一个空队列
LinkQueue *InitQueue()
{
LinkQueue *p;
Qnode *q;
p=(LinkQueue*)malloc(sizeof(LinkQueue));//为队列头指针分配空间
q=(Qnode*)malloc(sizeof(Qnode));//为头结点分配空间
q->next=NULL;//置头结点的指针域为空
p->front=p->rear=q;//队首指针、队尾指针均指向头结点
return p;
}
（2）取队头元素
datatype GetQueueHead(LinkQueue *Q)
{
if(Q->front==Q->rear)//判断队列是否为空
{
printf(" 链表队列为空");
return FALSE;
}
return Q->front->next->data;
}
(3)入队
void EnQueue(LinkQueue *Q,datatype x)
{
Qnode *p;
p=(Qnode)malloc(sizeof(Qnode));//开辟空间
p->data=x;//x赋值给p里面的data
p->next=NULL;//next指向空
Q->rear->next=p;//将值为x的元素入队(Q->rear指向的是队列的最后一个元素，所以这句话的意思就是队尾的最后一个元素的尾指针指向p)
Q->rear=p;//修改队尾指针的指向位置
}
(4) 出队
datatype DeQueue(LinkQueue *Q)
{
Qnode *p;
datatype x;
if(Q->front==Q->rear)//判断队列为空
{
printf("队列为空，无法删除元素");
return FALSE;
}
p=Q->front->next;//p指向队列头结点
x=p->data;//取出队列的头结点数据
Q->front->next=p->next;//删除头结点
if(Q->rear==p)//判断该链表队列中是否只有这一个元素
Q->front=Q->rear;
free(p);
return x;
}
注意：在删除队头元素的时候，仅仅需要修改结点中的指针，但当队列中最后一个元素被删除后，队尾指针也会丢失，因此需要对队尾指针重新赋值。
队列产出溢出：
队列的“上溢”：队列空间已满，而继续往队列中插入元素，就会使数组越界而导致程序代码被破坏，称为“上溢”
顺序队列的“假溢”：由于头尾指针都不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了"上溢"现象。
为了克服"假溢"现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
判定循环队列是空还是满，方法有三种：
·一种是另设一个布尔变量来判断；
·第二种是少用一个元素空间，入队时先测试（(rear+1)%m = front）? 满：空；
·第三种就是用一个计数器记录队列中的元素的总数。
