队头(front):允许删除的一端，又称队首。
队尾(rear): 允许插入的一端。
空队列：不含任何元素的空表。
队列的顺序存储 比较简单，下面我们学习一下队列的链式存储结构。
队列的链式存储类型可描述为
复制代码
1 typedef struct{ //链式队列节点
2 ElemType data:
3 struct LinkNode *next;
4 }LinkNode;
5 typedef struct{ //链式队列
6 LinkNode *front, *rear;
7 }LinkQueue
复制代码
当Q.front,Q.rear==NULL时，链式队列为空。为了方便插入和删除操作，通常将链式队列设计成一个带头结点的单链表。
链式队列的基本操作：
(1)初始化
void InitQueue(LinkQueue &Q){
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}
(2)判队空
bool IsEmpty(LinkQueue Q){
if(Q.front = = Q.rear) return true;
else return false;
}
(3)入队
void EnQueue(LinkQueue &Q,ElemType x){
s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x;s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}
(4)出队
复制代码
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==Q.rear) return false;//空队
p=Q.front; //让头元素指向p
x=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear==Q.front; //若原队列中只有一个结点，删除后变空
free(p);
return true;
}
复制代码
1、如果希望循环队列中的元素都能得到利用，则需要设置一个标志域tag，并以tag的值为0或1来区分队头指针front和队尾指针rear相同时的队列状态是“空”还是“满”。使编写此结构相应的入队和出队算法。
在循环队列的类型结构中，增设一个tag的整型变量，进队时设置为1，出队时设置为0。初始时，设置为tag=0,front=0,rear=0.
队空条件：Q.front ==Q.rear 且tag==0。
队满条件: Q.front == Q.rear且tag==1。
入队操作：Q.data[Q.rear]=x;Q.rear=(Q.rear+1)/MaxSize;Q.tag=1。
出队操作: x=Q.data[Q.front];Q.front=(Q.front+1)/MaxSize;Q.tag=0。
2、Q是一个队列，S是一个空栈，实现将队列中的元素逆置的算法。
只是对队列的一系列操作是不可能将其中的元素逆置的，所以我们可以借助栈来存储队列中的元素。
复制代码
void Inverser(Stack S, Queue Q){
while(Q.front!=Q.rear){ //将队列中的元素逐个地出队列，入栈
x=DeQueue(Q);
Push(S,x);
}
while(S.top!=-1){ //逐个出栈，然后入队列
Pop(S,x);
EnQueue(Q,x);
}
}
复制代码
3、利用两个栈 S1 、S2 来模拟一个队列，已知栈的4个运算定义如下：
Push(S,x); //元素x入栈S
Pop(S,x); //S出栈并将出栈的值赋给x
StackEmpty(S); //判断栈是否为空
StackOverflow(S); //判断栈是否满
那么如何利用栈的运算来实现该队列的3个运算：
Enqueue; //将元素x入队
Dequeue; //出队，并将出队元素存储在x中
QueueEmpty; //判断队列是否为空
利用两个栈S1和S2 来模拟一个队列，当需要想队列中插入一个元素时，用S1存放已输入的元素，即S1 执行入栈操作。当需要出队时，则对S2执行出栈操作。由于从栈中取出元素的顺序是原顺序的逆序，所以，必须将S1 中所有元素全部出栈并入栈到S2中，再在S2 中执行出栈操作，即可实现出队操作。因此，在执行操作前必须判断S2 是否为空，否则会导致顺序混乱。当栈S1和S2都为空时，队列为空。
总结如下：
（1）对S2的出栈操作用出队，若S2 为空，则先将S1 中的所有元素送入S2 。
（2）对S1的入栈操作用入队，若S1满，必须先保证S2 为空，才能将S1中的元素全部插入到S2中去。
入队算法：
复制代码
int EnQueue(Stack S1,Stack S2,ElemType e){
if(!StackOverflow(S1)){
Push(S1,x);
return 1;
}
if(StackOverflow(S1)&&!StackEmpty(S2)){
return 0;
}
if(StackOverflow(S1)&&StackEmpty(S2)){ //S1满 S2空
while(!StackEmpty(S1)){
Pop(S1,x);
Push(S2,x);
}
}
Push(S1,x);
return 1;
}
复制代码
出队算法：
复制代码
void DeQueue(Stack S1,Stack S2,ElemType &x){
if(!StackEmpty(S2))