1.队列的基本概念

队列(Queue)简称队，是一种操作受限的表，只允许在表的一端进行插入，另一端进行删除。向队列中插入元素称为入队或进队，删除元素称为出队或离队，操作特性为先进先出。

队列的“先入先出”特性是指：最后插入的元素总是被最后删除，每次从队列删除的总是最早插入的元素。

2.队列的顺序存储

#define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int front,rear;
}SqQueue;

初始状态（队空状态）：Q.front=Q.rear=0。

进队操作：队不满时，先将元素加到队尾，再将队尾指针加1。

出队操作：队不空时，先将队头元素取出，再将队头指针加1。

3.循环队列

在普通队列中，每次入队和进队操作都会将队头队尾指针增加，会造成一种“假溢出”问题，这时候就需要使用循环队列。将顺序队列从逻辑上视为一个环状空间，此为循环队列。

初始时：Q.front=Q.rear=0。

队首指针进1：Q.front=(Q.front+1)%MaxSize。

队尾指针进1：Q.rear=(Q.rear+1)%MaxSize。

循环队列的问题：当队空和队满时，均有Q.front==Q.rear。该怎么判断队空还是队满？

解决：方案1，牺牲一个单元来区分队空还是队满，入队时少用一个队列单元，使队满条件为:(Q.rear+1)%MaxSize==Q.front,队空条件为：Q.front==Q.rear。

方案2，增设表示元素个数的数据单元，队空时：Q.size==0,队满时：Q.size==MaxSize。

方案3：增设tag变量，tag等于0时，若Q.front==Q.rear，则为队空，tag等于1时，Q.front==Q.rear，则为队满。

//初始化
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0;
}
//队的判空
bool isEmpty(SqQueue Q){
if(Q.rear==Q.front) {
return true;
}
else{
return false;}
}
//入队
bool EnQueue(SqQueue &Q,ElemType x){
if((Q.rear+1)%MaxSize==Q.front){
return false;
}
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize;
return true;
}
//出队
bool DeQueue(SqQueue &Q,ElemType x){
if(Q.rear==Q.front){
return false;}
x=Q.data[Q.front];
Q.front=(Q.fornt+1)%MaxSize;
return true;
}

4.队列的链式存储

实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向头结点，尾指针指向尾结点。

typedef struct{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *rear,*front;
}LinkQueue;

当Q.front==NULL且Q.rear==NULL时，链式队列为空。

//初始化
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=NULL;
}
//队判空
bool isEmpty(LinkQueue Q){
if(Q.front==Q.rear){
return true;
}
else{
return false;
}
}
//入队
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=x; s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}
//出队
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==Q.rear){
return false;
}
LinkNode *p=Q.front->next;
x=p->data;
Q.front->next=p->next;
if(Q.rear==p)
   Q.rear=Q.front;         //若原队列中只有一个结点，删除后变空。
free(p);
return true;
}

5.双端队列

双端队列是指允许两端都可以进行入队和出队的队列，将队列两端分别称为前端和后端，两端都可以入队和出队。