2.2 队列的概念、实现及应用

2.2 队列的概念、实现及应用

2.2 队列的概念、实现及应用

一、选择题

　　1．选择题题目部分
　　● 判断“链式队列为空”的条件是 （1） （front为头指针，rear为尾指针）。
　　（1）A．front==NULL B．rear==NULL C．front==rear D．front!=rear
　　● 用不带头节点的单链表存储队列时，其头指针指向队头节点，其尾指针指向队尾节点，则在进行删除操作时 （2） 。
　　（2）A．仅修改头指针 B．仅修改尾指针
　　C．头、尾指针都要修改 D．头、尾指针可能都要修改
　　● 判断一个循环队列cq（最多元素为QueueSize）为满队列的条件是 （3） 。
　　（3）A．cq.rear==sq.front B．cq.rear==QueueSize
　　C．(cq.rear+1)%QueueSize==cq.Front D．cq.rear%QueueSize+1==cq.front
　　● 若循环队列以数组Q[0，…，m-1]作为其存储结构，变量rear表示循环队列中队尾元素的实际位置，其移动按rear=(rear+1) mod m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 （4） 。
　　（4）A．rear-length B．(rear-length+m) mod m
　　C．(1+rear+m-length) mod m D．m-length
　　● 循环队列A[0,…,m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素个数是 （5） 。（补充：队尾指针指向队尾元素）。
　　（5）A．(rear-front+m)%m B．rear-front+1
　　C．rear-front-1 D．rear-front
　　2．选择题练习答案与分析
　　题号（1）答案 A
　　习题分析：
　　链表的第一个节点是队首节点，链表的最后一个节点是队尾节点，队尾节点的指针值为null。显然当队首节点的指针值为null时（也就是front==NULL），说明队列为空。
　　题号（2）答案 D
　　习题分析：
　　当链表中不止一个元素时，只需要修改头指针；当链表中只有一个元素时，就需要将头指针和尾指针都赋值为空。
　　题号（3）答案 C
　　习题分析：
　　只要注意到这是循环队列，依据其结构：循环队列的rear指向队尾元素的下一个单元，而不是队尾元素，可得答案为C。
　　题号（4）答案 C
　　习题分析：
　　其实这种题目在考场上最好的解题方法是找一个实际的例子，往里面一套便知道了。下面解释一下原理。
　　因为rear表示的是队列尾元素的实际位置（***注意不是队尾指针***）。而且题中有“移动按rear=(rear+1)mod m，这句说明：队列的存放元素顺序为：…Q[1]，Q[2]，…Q[m-1]，Q[0]…所以在理想情况下rear-length+1能算出队首元素的位置。（即当m=8，rear=5，length=2时，rear-length+1=4，4就是正确的队首元素实际位置）但rear-length+1有一种情况无法处理：即当m=8，rear=1，length=5时，无法算出。
　　所以我们在rear+1-length的基础上加上m再和m求模，以此方法来计算。所以本题答案应为C。
　　题号（5）答案 A
　　习题分析：
　　一般情况下，根据循环队列的定义，很容易得出队列中元素个数为：rear-front+1。但考虑到队列是循环队列，随着元素不断地插入和删除，rear指针的值可能比front指针的值还小，因此，要作一个求模的操作。即循环队列中元素的个数是：(rear-front+m)%m 。
　　3．训练自测表（如表2-7所示）

表2-7 选择题练习自测表

二、综合应用题

　　1．综合应用题题目部分
　　● 习题1：何谓队列的上溢现象，一般有几种解决办法？试简述之。
　　● 习题2：请利用两个栈S1和S2来模拟一个队列。已知栈的3个运算定义如下：
　　PUSH(ST,x)：元素x入ST栈；
　　POP(ST,x)：ST栈顶元素出栈，赋给变量x；
　　Sempty(ST)：判ST栈是否为空。
　　那么请写明如何利用栈的运算来实现该队列的3个运算：enqueue：插入一个元素入队列； dequeue：删除一个元素出队列；queue_empty：判队列为空（请写明算法的思想及必要的注释）。
　　2．综合应用题答案与分析
　　习题1分析：
　　在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列指针rear，队列的容量为maxsize。当有元素要加入队列时，若rear=maxsize，则会发现队列上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当引起的，可以用循环队列来解决。
　　一般来说，要解决队列的上溢现象，有以下几种方法。
　　（1）可建立一个足够大的存储空间以避免溢出，但这样往往会造成空间使用率低，浪费存储空间。
　　（2）要避免“假溢出”现象，可以用以下方法解决。
　　第一种：采用移动元素的方法。每当有一个新的元素入队，就将队列中已有的元素向队头移动一个位置。
　　第二种：每当删除一个队头元素，则可依次移动队列中的元素，使front指针总是指向队列中的第一个位置。
　　第三种：采用循环队列的方式。将队头、队尾看做是一个首尾相连的循环队列。
　　习题2分析：
　　栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空时，队列才为空。其操作算法如下所示： 

　　3．训练自测表（如表2-8所示）

表2-8 应用题练习自测表

2.2 队列的概念、实现及应用