队列的基本概念
1. 队列定义：只允许在一端进行插入，在另一端进行删除的线性表。
2. 队列特点：先进先出（FIFO）。
3. 队列基本操作：初始化队列、销毁队列、入队、出队、读队头元素、判队列空等。
InitQueue(&Q)：初始化队列，构造一个空队列Q。
DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。
EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
队列的顺序实现
用一组地址连续的存储单元，依次存放从队头到队尾的数据元素，称为顺序队列。
需要附设两个指针：队头指针（front）和队尾指针（rear），分别指向队头元素和队尾元素。
#define MAXSIZE 50 //定义队列中元素的最大个数
typedef struct{
ElemType data[MAXSIZE]; //存放队列元素
int front,rear;
}SqQueue;
初始状态（队空条件）：Q.front = Q.rear = 0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。
“假溢出”：如果在插入E的基础上再插入元素F，将会插入失败。因为rear==MaxSize，尾指针已经达到队列的最大长度。但实际上队列存储空间并未全部被占满，这种现象叫做“假溢出”。假溢出的原因是顺序队列进行队头出队、队尾入队，造成数组前面会出现空闲单元未被充分利用。
循环队列
解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。队列这种头尾相接的顺序存储结构称为循环队列。
初始时：Q.front = Q.rear=0
队首指针进1：Q.front = (Q.front + 1) % MAXSIZE
队尾指针进1：Q.rear = (Q.rear + 1) % MAXSIZE
队列长度：(Q.rear - Q.front + MAXSIZE) % MAXSIZE
问题：当循环对列为空或满时，都是队尾指针等于队头指针，即rear=front 。当rear=front时，该是判满还是判空呢？
为了区分队空还是队满的情况，有三种处理方式：
（1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”。
队满条件： (Q.rear + 1)%Maxsize == Q.front
队空条件仍： Q.front == Q.rear
队列中元素的个数： (Q.rear - Q .front + Maxsize)% Maxsize
（2）类型中增设表示元素个数的数据成员。这样，队空的条件为 Q.size == O ；队满的条件为 Q.size == Maxsize 。这两种情况都有 Q.front == Q.rear。typedef int ElemType; #define MAXSIZE 50 typedef struct{ ElemType data[MAXSIZE]; int front; //头指针 int rear; //尾指针,若队列不空，指向队列尾元素的下一个位置 int size; }SqQueue;（3）类型中增设tag 数据成员，以标记最近一步操作是入队(标记为1)还是出队(标记为0)。只有最近一步为出队后的Q.rear==Q.front，才能确定为队空；队满同理。
typedef int ElemType; #define MAXSIZE 50 typedef struct{ ElemType data[MAXSIZE]; int front; //头指针 int rear; //尾指针,若队列不空，指向队列尾元素的下一个位置 int tag; }SqQueue;
//rear:指向队尾下一个元素 front:指向队头元素
#define MaxSize 3
typedef struct{
int data[MaxSize];
int front; //队头指针
int rear; //队尾指针
}SqQueue;
//0.初始化
void InitQueue(SqQueue &Q){
//牺牲一个存储空间
//rear:指向队尾下一个元素 front:指向队头元素
//判空条件：front==rear
//判满条件：(rear+1)%MaxSize==front
Q.front=0;
Q.rear=0;
}
//1.入队操作
bool EnQueue(SqQueue &Q,int x){
if((Q.rear+1)%MaxSize==Q.front){ // 判断队列是否满
return false;
}
Q.data[Q.rear]=x; //存值
Q.rear=(Q.rear+1)%MaxSize; // 向下一个存储单元移动
return true;
}
//2.出队操作
bool DeQueue(SqQueue &Q,int &x){
if(Q.front==Q.rear){ // 判断队列是否为空
return false;
}
x=Q.data[Q.front]; //取值
Q.front=(Q.front+1)%MaxSize; // 向下一个存储单元移动
return true;
}
//3.获取队头元素
bool GetHead(SqQueue &Q,int &x){
if(Q.front==Q.rear){ // 判断队列是否为空
return false;
}
x=Q.data[Q.front];
return true;
}
队列的链式实现
定义—链式队列结点
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}LinkQueue;初始化
void InitQueue(LinkQueue &Q){
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); // 创建头结点
s->next=NULL;
Q.front=s;
Q.rear=s;
} 入队
bool EnQueue(LinkQueue &Q,int x){
//无需判断队满
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x;
//结点后插
s->next=Q.rear->next;
Q.front->next=s;
Q.rear=s;
return true;
} 出队
bool DeQueue(LinkQueue &Q,int &x){
if(Q.front==Q.rear){ // 判断队列是否为空
return false;
}
LinkNode *p=Q.front->next; // 获取所要出队的结点
x=p->data;
if(p->next==NULL){ // 判断是否为最后一个元素
Q.rear=Q.front;
}
Q.front->next=p->next;
free(p);
return true;
}
获取队头元素
bool GetHead(LinkQueue &Q,int &x){
if(Q.front==Q.rear){ // 判断队空
return false;
}
LinkNode *p=Q.front->next;
x=p->data;
return true;
}
双端队列
