队列（Queue）只允许在表的一端进行插入，表的另一端进行删除操作的线性表。
特点：先进先出。
队列的基本操作
InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Q,x)：入队，若队列Q未满，则将x加入使之成为新的队尾。
DeQueue(&Q,&x)：出队，若队列Q非空，则删除队头元素，并用x返回。
GetHead(Q,&x)：读队头元素，若队列Q非空则用x返回队头元素。
ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。
顺序队：采用顺序存储的队列。
#define MaxSize 50
typedef struct{
Element data[MaxSize];
int front,rear;
}SqQueue;
-front指向队头元素，rear指向队尾元素的下一位置（或front指向队头元素的前一位置，rear指向队尾元素）
-初始时front == rear ==0
判空：Q.front == Q.rear
队长：Q.rear - Q.front
循环队列：把存储队列的顺序队列在逻辑上视为一个环
取余 （%MaxSize）
front指针移动：Q.front = （Q.front + 1）% MaxSize
rear指针移动：Q.rear= （Q.rear+ 1）% MaxSize
队列长度：（Q.rear + MaxSize - Q.front ）% MaxSize
方法一：牺牲一个存储单元
队空条件：Q.front == Q.rear
队满条件：Q.front == （Q.rear + 1）% MaxSize
方法二：增加一个变量代表元素的个数
Q.size = 1
队空条件：Q.size == 0
队满条件：Q.size == MaxSize
方法三：增加tag标识
队空条件：Q.front==Q.size&&tag==0
队满条件：Q.front==Q.size&&tag==1
初始化
void InitQueue(SqQueue &Q){
Q.front = Q.rare = 0；
}
判队空
bool isEmpty(SqQueue Q){
if(Q.rear == Q.front)
return true;
else
return false;
}
入队
bool EnQueue(SqQueue &Q,ElemType x){
if((Q.rare+1)%Maxsize == Q.front){
return false;
}
Q.data[Q.rare]=x;
Q.rare = (Q.rare+1)%Maxsize;
return true;
}
出队
bool DeQueue(SqQueQue &Q,ElemType &x){
if(Q.rear == Q.front)
return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1)%Maxsize;
return true;
}
链队：采用链式存储的队列
type struct{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
初始化
void InitQueue(LinkQueue &Q){
Q.front = (LinkNode*)malloc(sizeof(LinkNode));
Q.rear = Q.front;
Q.front->next = null;
}
判队空
bool isEmpty(LinkQueue Q){
if(Q.rear == Q.front)
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.fornt->next = p->next;
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return true;
}
输出序列
出栈序列中每一个元素后面所有比它小的元素组成一个递减序列。
合法出栈序列个数：f(n)=C(2n,n)/(n+1)
双端队列允许两端都可以进行入队以及出队操作的队列
