队列

常见应用

• 脱机打印输出：按申请的先后顺序依次输出
• 多用户系统中多用户排队分时循环使用CPU和主存
• 按用户的优先级排成多个队，每个优先级一个队列
• 实时控制系统中，信号按接收的先后顺序一次处理
• 网络电文传输，按到达的先后顺序依次进行

顺序队

表示

• 最大队列长度

• const MAXQSIEZE=100;

• 或#define MAXQSIZE 100

• 重定义结构体

  • QElemType *base(顺序队数组的首元素地址）
  • int front;头指针，如果队列不空，指向队头元素front队头元素下标
  • int rear;尾指针，如果队列不空，指向队尾元素再往后一个位置，和栈顶指针一个意思。rear队尾元素下标
  • 注意头尾指针不是真正的指针，是表示下标的int型变量罢了。
    

• 重定义结构体的新类型名字就叫SqQueue,我们一般SqQueue Q;这样就定义了一个顺序队列。你也可以给队列起别的名字不只是Q，下面采用队列的默认名字Q来说事。

上溢：队列满了，你还往队尾添加元素。那我让rear指针怎么在往上走呢？所以就要报错说上溢了

下溢：队列空了，你还要从队头删除元素，那我让front指针怎么再往下走呢？所以就要报错说下溢了

出队从队头（front指针指的元素）出队，入队从队尾入队（rear指针指的空间入队）

• 所以会造成假上溢的问题，就是你出队front指针往上走一格，然后入队rear指针也往上走，会不会rear指针都走到头了（数组最后一个元素再往后一格的地址位置），假如你front指针指向了不是下标为0的位置，此时你队列看着还能添加元素，可是你只能从队尾添加，rear指针都到头了，你还添加个屁。所以，这不就是假上溢了吗？

所以就有了循环队列，就是我可以这样解决假上溢问题

• Q.rear=(Q.rear+1)%MAXQSIZE;这个解决方案很巧妙，假如Q.rear指向了顺序队数组最后一个元素的下标的位置，然后它再+1，是不是就到了上溢的临界点（还没上溢，可能就是队列假满了）？然后比如MAXQSIZE是6，啊，那最后一个元素下标是5，然后5+1再对6取余，这样是不是Q.rear回到了0？这样不就可以在顺序队数组前头添加元素了？解决了假上溢问题
• front指针也是如此，front指针在顺序队列也会有一次指向了数组最后一个元素下标的位置。然后+1就要到了上溢临界点，然后采取跟Q.rear一样的操作——Q.front=(Q.front+1)%MAXQSIZE;然后就解决了假上溢问题
• 当然你也可以一个if判断rear/front指针是否指向了队列数组最后一个元素的下一个位置，然后让rear或者front=0也行，但是咱们一行代码能解决的事情为什么两行代码，所以求余的写法非常简洁，而且也很巧妙。通用性也有（在一下子往队列插入好些元素，比如Q.rear+n这种情况。）

循环队列解决了假上溢问题，那么如何判断队空和队满？因为循环队列队空和队满都是Q.front==Q.rear;那我怎么知道队空还是队满？

• 解决方案：

  • 少用一个元素空间

    • 当队空时，Q.rear=Q.front，如果一直出队的话，front指针会追向rear，直到跟rear指向同个数组位置。
    • 当队满时，(Q.rear+1)%MAXQSIZE==front，此时rear指向的那个元素空间没有存任何数据，这个意思就是说rear指针再+1就和front指针重合了。此时就知道队列要满了，如果一直入队，就是rear追front
      

  • 设置一个flag，队列存着元素flag=1;队列没存着元素flag=0;看或者输出flag就能知道队列空不空，满不满

  • 记录元素个数，比如定义个count,实时记录着队列的元素个数，看或者输出count就能知道队列空不空，满不满

• 关于循环队列的判断队空和队满，产生队满是rear追front，产生队空是front追rear。有了这个思想你理解循环队列队空对满的判断条件就不难理解了。

算法（循环队列）

• 队列初始化

  • 思路：给base（队列所用的数组）new个内存空间，然后如果分配失败（if的异常处理）就退出，分配成功就让Q.front和Q.rear=0即可（“指向”base数组首元素），然后返回OK
  • Q.base=new QElemType[MAXQSIZE];给队列数组分配内存空间
  • if(!Q.base){exit(OVERFLOW};异常处理
  • Q.front=Q.rear=0;队头指针队尾指针“指向”数组首元素（和数组首元素下标0相同），此时队列为空
  • return OK;
  • 参数&Q(SqQueue &Q,下同）

• 队列求长

  • 返回值为int型，直接return Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
  • 为嘛如此麻烦？因为循环队列会有rear指针指向的下标小于front指针指向的下标的情况，你总不能直接return rear-front;返回一个负数长度吧？所以借鉴假上溢的解决办法，咱们这样做，比如rear=4，front=5，MAXQSIZE=6，这是一个队列满的情况（队列满时队列一共容下了5个元素），再插入元素就真上溢了。（4-5+6）%6=5，所以队列长度为5。所以return Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;这个方法是不是很巧妙？
  • 参数&Q,返回值int别写错了，因为要返回队列长度

• 循环队列入队

  • 思路：先判断队列满不满？满了就异常处理退出入队函数，不满就让rear指针”指向“的下标的位置入队元素，然后rear指针往上走一格（同时判断是否假上溢，若假上溢，rear指针回到指向数组下标为0的位置上来），然后返回OK
  • if((Q.rear+1)%MAXQSIZE==Q.front){return ERROR;}
  • 没有走if，就Q.base[Q.rear]=e;队尾指针指的下标对应的位置上入队一个元素。
  • Q.rear=(Q.rear+1)%MAXQSIZE;然后队尾指针上移一格，同时进行假上溢判定
  • return OK;入队完毕，返回OK
  • 参数&Q，e（QElemType型）

• 循环队列出队

  • 思路：先判断队列空不空？空了异常处理，退出出队函数，不空就让front指针”指向“的元素赋值给e，然后front指针上移一格，同时进行假上溢判定，如果假上溢，rear指针回到指向数组下标为0的位置上来，然后返回OK
  • if(Q.front==Q.rear){return ERROR;}判断队空且是否异常处理
  • e=Q.base[Q.front];保存队头元素，另作他用
  • Q.front=(Q.front+1)%MAXQSIZE;让队头指针上移一格，同时进行假上溢判定
  • return OK;出队完毕，返回OK
  • 参数&Q，e（QELemtype型）

• 取队头元素

  • 如果队列不空，即if(Q.front!=Q.rear)
  • 那么直接返回Q.base[Q.front]即可，这就是队头元素。队头指针也不用变因为你也没做出队操作什么的。

链队

定义

• const MAXQSIEZE=100;

• 或者#define MAXQSIZE 100

• 重定义一个结构体

  • 数据域data
  • 指针域*next
  • 然后给这个重定义结构体（结点结构体或指向结点结构体的指针）起个别名，一个QNode，一个*QueuePtr
    

• 重定义一个指针结构体（图如上）

  • QueuePtr front;队头指针，同时也是链队列的头指针
  • QueuePtr rear;队尾指针，同时也是链队列的尾指针
  • 给该重定义结构体起个别名（新类型名）叫LinkQueue
  • 链队列linkqueue定义成普通结构体是为了在用其成员变量队头队尾指针时代码写成Q.front Q.rear，这样就和顺序队列的操作可以对比着看了不至于看链队列如此的生涩

算法：

• 链队列初始化

  • 思路：先给队头队尾指针（链队列这两个指针就是真正的指针）分配空间，然后如果某一个分配空间失败了，就异常处理退出链队列初始化函数。如果分配成功，则让对头指针的next域设置为空（NULL），此时队头队尾指针都指向队列的头结点（和单链表一样，有头结点是为了方便操作）。然后返回OK代表链队列初始化成功
  • Q.front=Q.rear=new QNode ;（队头队尾一块给分配内存空间了（这样的写法意思是队头队尾指向同一个结点，代表链队列初始化后一开始是空队列）
  • 如果没内存给分配了（链队列不大可能），就异常处理，if(!Q.front){exit OVERFLOW;}，这里只写了一个指针（队头指针）的异常处理判定，是因为rear指针跟front指针指的一个结点的内存空间，如果front指针指向的内存空间分配失败，那不也代表rear指针指向的内存空间分配失败？
  • Q.front->next=NULL;不用多说，链队列初始化，那就得让头结点的next域置空
  • return OK;初始化完毕，返回成功信号。
  • 参数&Q

• 销毁链队列

  • 思路：从队头节点开始，依次释放所有节点（注意利用rear指针）
  • while(Q.front){}先判断链队列存不存在，注意这里是链队列！不要往顺序队列那里去想！不存在直接返回OK
  • while循环里：Q.rear=Q.front->next;delete Q.front;Q.front=Q.rear;这里巧妙的运用了rear指针，而不是另创一个指针指向头结点（front队头指针所指的结点）的next域（下一结点），免得浪费空间
  • 就这样一次一次循环，从队头结点开始delete，一直到尾结点。到尾结点的时候，Q.rear会被赋值成空（Q.front->next肯定是NULL了），然后Q.front又被Q.rear赋值（Q.rear此时是NULL）为空了，然后进入循环判断，退出循环，避免发生指向不明的情况。
  • 销毁链队列完毕，返回OK
  • 参数&Q

• 入队

  • 思路：和单链表尾插法入表是一样的思路，因为链队列入队只能从队尾入。看代码就能懂
  • p=new Qnode;
  • if(!p){exit(OVERFLOW);}如果分配新结点的内存不足，则异常处理
  • 下面和单链表的尾插法一致
  • p->data=e;
  • p->next=NULL;
  • Q.rear->next=p;
  • Q.rear=p;
  • return OK;
  • 参数&Q，e（QELemtype型）

• 出队

  • 思路：和单链表删除一个元素的思路类似，比单链表删除元素简单一些，因为链队列出队只能从队头出队，也就是只能删除Q.front指针的指向的头结点的下一个结点。
  • if(Q.front==Q.rear){return ERROR;};异常处理，判断队列是不是空的，空的就不要执行出队操作了，直接返回个错误。而入队不需要判断front指针和rear指针的位置情况因为链队列不是循环队列而且链队列很难上溢，但有下溢的可能。
  • p=Q.front->next;要定义一个工作指针指向要删除的链队列的结点（队头出队，删除队头结点）
  • Q.front->next=p->next;
  • if(Q.rear==p){Q.rear=Q.front;}这个是针对出队的结点是队尾指针指向的结点，防止该结点出队后Q.rear这个队尾指针变成了野指针，因此删除最后一个结点时（即队尾结点，if那个条件成立时），让rear指针指向头结点，即和队头指针front指向同一个结点，这样也代表了删除完队尾结点后队列为空。
  • delete p;注意这行不能和if那一行互换，因为如果互换，p指向的结点删除了，万一是队尾结点，Q.rear不就变成了野指针？然后你还让rear指针和p去比较看相不相等？放狗屁。
  • return OK;出队操作完毕，返回OK
  • 参数&Q，&e（QELemtype型）

• 求（取）队列的队头元素

  • 很简单，只要队列不是空的，你返回front指针指向的头结点的下一个结点，就是队头结点，即可
  • if(Q.front==Q.rear){return ERROR;}如果队列是空的，就不用返回队头元素了，直接异常处理返回错误就OK了
  • e=Q.front->next->data;如果链队列不是空的，那么就返回队头元素（肯定是front这个指针指向的头结点的下一个结点）给e即可
  • return OK;队头元素取出成功。
  • 参数&Q，&e