队列

队列的定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出 的线性表。允许插入的一端称为队尾，允许删除的一端为对头。

 

循环队列

队列顺序存储的不足

实现顺序存储需要建立一个数组，所谓入队操作，其实就是在队尾追加一个元素；出队操作，就是让所有的元素向前移动，保证队列的对头，即下标为0的位置不为空。

 

 由于出队时要移动所有的元素，为提高出队的性能，我们可以让对头不需要一定在下标为0的位置。

为了避免当一个元素的时候，对头和队尾重合使处理变得麻烦，引用两个指针，front和rear，指向对头元素和队尾元素，当front==rear时，为空对。

假溢出

当数组末尾元素已经占用，再向后加，就会产生数组越界的错误。

 循环队列的定义

我们把队列头尾相接的顺序存储结构称为循环队列。

 但是这样就会有一个问题，即当front==rear时，对内不一定为空。

解决办法有两个：

1.定义一个flag，当front=rear，且flag=0时队列为空，当front=rear，且flag=1时队列为满。

2.或者我们保留一个元素空间，也就是说，队列满时，数组中还有一个空闲单元。此时front=rear时，队列就空；当（rear+1）%size==front时，队列为满。

当rear>front时，队列长度为rear-front。

当rear<front时，队列长度为size-front+size.

通用的计算队列长度公式为：（rear-front+size)%size 

队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它能尾进头出而已，我们把它简称为链队列。 

入队chu

/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q,QElemType e)
{ QueuePtr s=(QueuePtr)malloc(sizeof(QNode));if(!s) /* 存储分配失败 */exit(OVERFLOW);s->data=e;s->next=NULL;Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */return OK;
}

 出队

/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{QueuePtr p;if(Q->front==Q->rear)return ERROR;p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */*e=p->data;				/* 将欲删除的队头结点的值赋值给e */Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */Q->rear=Q->front;free(p);return OK;
}