Queue Structures

队列（FIFO）

1. 定义：只允许在一段插入另一端删除的 先进先出 ==排队== 线性表

   1. 抽象数据类型（Queue）：P94~95

2. 顺序队列 ==> 循环队列（头尾相接的改进版顺序队，解决”假溢出“）

   1. 队头指针：front
   2. 队尾指针：rear
   3. 队列最大尺寸：QueueSize
   4. 假溢出：数组中前端下标空闲，往后入队超出数组长度，非正常溢出，称为“假溢出”
   5. 循环队列两种判断队空队满方法
      1. 方法一：设置标志变量flag，front == rear，且flag=0时，队空；front == rear，且flag==1，队满
      2. 方法二：保留一个元素空间，front == rear，队空；数组中剩余一个空闲单位，即条件为：(rear+1)%QueueSize == front，队满

         1. 队列长度：(rear - front + QueueSize)%QueueSize （通用长度计算公式）

            1. 当rear > front：rear-front
            2. 当rear < front：rear-front+QueueSize

         2. 循环队列顺序存储结构定义：

            1 2 3 4 5 6 7

            typedef int QElemType; typedef struct { QElemType data[MAXSIZE]; //数组存放 int front; //队头指针 int rear; //队尾指针 }SqQueue;

         3. 初始化（建立）空队：

            1 2 3 4 5 6

            Status InitQueue(SqQueue *Q) { Q->front = 0; Q->rear = 0; return OK; }

         4. 返回队列长度：

            1 2 3 4

            int QueueLength(SqQueue Q) { return (Q.rear->Q.front+MAXSIZE)%MAXSIZE; //循环队通用长度计算公式 }

         5. 入队：

            1 2 3 4 5 6 7 8 9 10 11 12 13 14

            /* 1. 判断队满 2. 元素e赋值给队尾rear数据域data（排队） 3. 队尾rear后移一位，若最后一位转到头部 */ Status EnQueue(SqQueue *Q,QElemType e) { if((Q.rear+1)%MAXSIZE == Q.front) //1 { Q->data[Q->rear] = e; //2 Q->rear = (Q->rear+1)%MAXSIZE; //3 } return OK; }

         6. 出队:

            1 2 3 4 5 6 7 8 9 10 11 12 13 14

            /* 1. 判断队空 2. 取出队头front指针数据域赋值给*e 3. 队头front后移，若最后一位则转到头部 */ Status DeQueue(SqQueue *Q,QElemType *e) { if(Q->front == Q->rear) //1 { *e = Q->data[Q->front]; //2 Q->front = Q->front+1%MAXSIZE; //3 } return OK; }

3. 链队（尾进头出的单链表）

   1. 空链队：front、rear 均指向头结点（含有）

   2. 链队列结构建立：

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

      typedef int QElemType; /* 结点结构建立： 存放数据变量、next指针域 */ typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; /* 队列链表结构建立： 队头、队尾指针定义 */ typedef struct { QueuePtr front, rear; }LinkQueue;

   3. 链队（队尾）入队：变动尾指针rear

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

      /* 1. 动态生成新结点s 2. 异常判断：动态生成是否成功，内存溢出 3. 数据e赋值给结点s的数据域 4. 结点s指针域尾NULL，作为队尾 5. （原）尾指针rear指向的结点next指向（新结点）s 6. 尾指针rear指向新结点s */ Status EnQueue(LinkQueue *Q,int e) { QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); //1 if(!s) { exit(OVERFLOW); //2 } s->data = e; //3 s->next = NULL: //4 Q->rear->next = s; //5 Q->rear = s; //6 return OK; }

   4. 链队（队头）出队：变动头指针front

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

      /* 1. 生成新指针变量p用于存放待删除结点 2. 异常检测：判断队空 3，队头结点（头指针的指针域next指向的结点）暂存到p 4. 取出暂存结点的数据域到*e 5. 此结点的指针域next指向的下一个结点 赋值给 头指针的指针域指向的结点，成为新的队头结点 6. 判断此结点是否为队尾（即原队列只存在一个数据），则将尾指针初始化空队（指向头结点） 7. 释放暂存结点p */ Status DeQueue(LinkQueue *Q,int *e) { QueuePtr p; //1 if(Q->rear == Q->front) { return ERROR; //2 } p = Q->front->next; //3 *e = p->data; //4 Q->front->next = p->next; //5 if(Q->rear == p) { Q->rear = Q->front; //6 } free(p); return OK; }