09.循环队列与链队列，09循环队列

09.循环队列与链队列，09循环队列

一、队列与循环队列 1.队列 (1)队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出(Fiirst In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。     从队列的定义可知，队列的入队操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。队列的删除操作，与栈不同的是，队列元素的出列是在队头，即小标为0的位置，若要删除一个元素的话，需要移动队列的所有元素，因此事件复杂度为O(n)。 (2)front/rear指针：为了避免当只有一个元素时，队尾和队头重合使处理变得麻烦，所有引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，队列为空(空队列)而不是队列还剩下一个元素。
2.队列的抽象数据类型 ADT 队列 Data     同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。 Operation     InitQueue(*Q):   初始化操作，建立一个空队列Q.     DestoryQueue(*Q):若队列Q存在，则销毁它。     ClearQueue(*Q):将队列Q清空     GetHead(Q,*e):若队列Q存在且非空，用e返回队列Q的队头元素。     EnQueue(*Q,e):若队列Q存在且非空，插入新元素e到队列Q中并称为队尾元素。     DeQueue(*Q,*e):删除队列Q中队头元素，并用e返回其值     QueueLength(Q)：返回队列Q的元素个数 endADT 3.循环队列  (1)定义：队列中头尾相接的顺序存储结构称为循环队列，用于解决"假溢出"问题。 (2)队满条件：     一般情况，当front=rear时，队列可能为空队列也可以为满队列。所以我们假设，当front==rear时队列为空；当队列满时，数组还有一个空闲空间。由于rear可能比front大，也可以比front小。我们这样定义，当队列满足条件"(rear+1)%QueueSize==front"时，我们就认为队列已满(QueueSize为队列最大存储容量)。 (3)队列长度公式     当rear>front时，队列的长度为rear-front;当rear<front时，队列的长度为(QueueSize-front)+(0+rear)，其中font、rear、QueueSize均为数组下标。经过推导的计算队列公式：     (rear-front+QueueSize)%QueueSize (4)循环队列的顺序存储结构 typedef int QElemType typedef struct {     QElemType data[MAXSIZE];     int front;    //队头指针     int rear;    //队尾指针，若队列不空，指向队尾元素的下一个位置 }SqQueue; (5)循环队列的相关操作 A.初始化一个循环队列Q Status InitQueue(SqQueue *Q) {     Q->front=0;     Q->rear=0;     return OK; } B.计算循环队列的长度 /*返回Q的元素个数，即队列的当前长度*/ int QueueLength(SqQueue Q) {     return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; } C.循环队列插入操作 实现：若队列未满，则插入元素e为新的队尾元素 Status EnQueue(SqQueue *Q,QElemType e) {     if((Q->rear+1)%MAXSIZE == Q->front)    //判断栈满((rear+1)%QueueSize==front)             return ERROR;     Q->data[Q->rear]=e;     Q->rear=(Q->rear+1)%MAXSIZE;    //rear指针向后移一位，若到最后则转到数组头部     return OK; } D.循环队列删除操作 实现：若队列不空，则删除Q中队头元素。用e返回其值 Status EnQueue(SqQueue *Q,QElemType *e) {     if(Q->rear==Q->front)             return ERROR;        //队列为空条件：rear=front     *e=Q->data[Q->front];    //将队头元素赋值给e     Q->front=(Q->front+1)%MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部     return OK; ｝ 总结：单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以我们下节引出队列的链式存储结构。 二、队列的链式存储结构 1.链队列：队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出，也称链队列。为了方便操作，队头指针指向链队列的头结点，队尾指针指向终端结点。当队头指针front和队尾指针rear都指向头结点时，队列为空。
2.链队列结构 typedef int QElemType /*结点结构*/ typedef struct QNode {     QElemType data;    //数据域     struct QNode *next;    //指针域 }QNode,*Queueptr; /*队列的链表结构*/ typedef  struct {     Queueptr front,rear;    //队头、队尾指针 }LinkQueue; 3.链队列的入队操作 算法：实质为链表尾插入结点，尾指针指向新结点 a.为新结点s开辟一段空间，并判断是否存储分配成功; b.将插入元素存到新结点s的数据域，并初始化s的指针域; c.把拥有元素e新结点s赋值给原队列结点的后继； d.把当前的s设置为队尾结点，rear指向s
实现：插入元素e为Q的新队尾元素

Status EnQueue(LinkQueue *Q,QElemType e)
{
    QueuePtr s=(QueuePtr)malloc(sizeof(QNode));    //为新结点s开辟一段空间
    if(!s)                                    //存储分配失败
            exit(OVERFLOW);    
    s->data=e;    //将元素e存储到新结点s的数据域
    s->next=NULL;//初始化新结点的指针域
    Q->rear->next=s;    //把拥有元素e新结点s赋值给原队列结点的后继
    Q->rear=s;    //把当前的s设置为队尾结点，rear指向s
}

4.链队列的删除操作 算法：实质是头结点的后继结点出队，将头结点的后继改为他后面的结点。若链表除头结点外，只剩下一个元素时，则需将rear指向头结点。 a.定义一个QueuePtr结点p，用于暂存欲删除的结点Q->front-next; b.将欲删除结点数据域数据赋值给e; c.将欲删除结点的后继结点(p->next)赋值给头队头结点的后继(Q->front->next) d.判定若队头是队尾，则删除后将rear指向头结点，最后再释放欲删除结点p.
实现：若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR

Status EnQueue(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;
}

三、循环队列与链队列性能分析 1.循环队列与链队列基本操作时间复杂度均为O(1); 2.循环队列事先申请好空间，使用期间不释放;链队列，无需事先申请空间但是每次申请和释放结点会存在一些事件开销; 3.循环队列必须有一个固定的长度，可能存在空间浪费；链队列需要一个指针域，会产生一些空间上的开销，所以在可以确定队列长度最大值的情况下建议用循环队列。