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)链队列为空的条件 
(2)链队列的删除操作 
(3)循环队列队满的情况 
(4)循环队列中元素位置的计算 
(5)循环队列中元素个数的计算 

二、综合应用题

  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 应用题练习自测表

题    号

考  查  点

得    分

(1)队列上溢的处理 
(2)用两个栈模拟队列的操作 

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

Contact

北京考研中心大厦

Connect

Subscribe

最新考研资料,欢迎联系博主获取。

京ICP备14027590号