免费智能真题库 > 历年试卷 > 程序员 > 2012年上半年 程序员 上午试卷 综合知识
  第38题      
  知识点:   队列
  关键词:   存储空间   队列   容量        章/节:   常用数据结构       

 
设循环队列Q的定义中有rear和size两个域变量,其中,rear指示队尾元素之后的位置,size表示队列的长度,如图所示(队列长度为3,队头元素为X)。设队列的存储空间容量为M,则队头元素的位置为(38) .
 
 
  A.  (Q.rear-Q.size+1)
 
  B.  (Q.rear-Q.size+1 )%M
 
  C.  (Q.rear-Q.size)
 
  D.  (Q.rear-Q.size+M)%M
 
 
 

 
  第38题    2012年下半年  
   52%
栈和队列的主要区别是(38)。
  第37题    2017年上半年  
   33%
为支持函数调用及返回,常采用称为“( )”的数据结构。
  第34题    2019年上半年  
   27%
函数调用和返回控制是用( )实现的。
   知识点讲解    
   · 队列
 
       队列
               队列的定义
               队列(queue)是一种只允许在一端进行插入,而在另一端进行删除的线性表,是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾(rear),只允许进行删除的一端称为队头(front)。队列的插入操作通常称为入队列或进队列,而队列的删除操作则称为出队列或退队列。当队列中无数据元素时,称为空队列。
               由队列的定义可知,队头元素总是最先进队列的,也总是最先出队列;队尾元素总是最后进队列,因而也是最后出队列。这种表是按照先进先出(First In First Out, FIFO)的原则组织数据的,因此,队列也被称为"先进先出"表。
               下图是一个队列的进出示意图,通常用指针front指示队头的位置,用指针rear指向队尾的位置。
               
               队列的进出示意图
               队列的基本操作
               队列的基本操作主要有以下6种。
               .InitQueue(&Q):初始化操作,构造一个队列Q。
               .QueueEmpty(Q):若栈Q为空队列,返回1,否则返回0。
               .EQueue(&Q, e):插入元素e到队列Q的尾部。
               .OQueue(&Q,&e):删除Q的队首元素,并用e返回其值。
               .GetQhead(Q,&e):用e返回Q的队首元素。
               .ClearQueue(&Q):将Q清空为空队。
               队列的顺序存储结构
               顺序存储结构采用一维数组(向量)实现,设队列头指针front和队列尾指针rear,并且假设front指向队头元素的前一位置,rear指向队尾元素。若不考虑队满,则入队操作语句为Q[rear++]=x;若不考虑队空,则出队操作语句为x=Q[++front]。当然,出队时,并不一定需要队头元素(与退栈类似)。
               按上述的做法,有可能出现假溢出,即队尾已到达一维数组的高端,不能再入队,但因为连续出队,队列中元素个数并未达到最大值。解决这种问题,可用循环队列。在循环队列中,需要区分队空和队满:仍用front=rear表示队列空,在牺牲一个单元的前提下,用front==(rear+1)% MAX表示队列满。在这种约定下,入队操作的语句为:rear=(rear+1)%MAX, MAX, Q[rear]=x;出队操作语句为:front=(front+1)% MAX。
               顺序队列的类型定义如下:
               
               顺序队列定义为一个结构类型,该类型变量有3个数据域:data、front、rear。其中data为存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量,取值范围是0~QueueSize-1。约定队尾指针指示队尾元素在一维数组中的当前位置,队头指针指示队头元素在一维数组中的当前位置的前一个位置,这种顺序队列说明如下。
               .初始化时,设置SQ.front=SQ.rear=0。
               .队头指针的引用为SQ.front,队尾指针的引用为SQ.rear。
               .队空的条件为SQ.front==SQ.rear;队满的条件为SQ.front=(SQ.rear+1)% QueueSize。
               .入队操作:在队列未满时,队尾指针先加1(要取模),再送值到队尾指针指向的空闲元素。出队操作:在队列非空时,队头指针先加1(要取模),再从队头指针指向的队头元素处取值。
               .队列长度为(SQ.rear+QueueSize-SQ.front)% QueueSize。
               特别应注意的是:在循环队列的操作中队头指针、队尾指针加1时,都要取模,以保持其值不出界。
               在循环队列上队列的实现基本操作的函数如下。
               1)初始化initqueue(SQueue *SQ)
               
               2)判空QueueEmpty(SQueue SQ)
               
               3)入队EQueue(SQueue *SQ, ElemType e)
               
               4)出队OQueue(SQueue *SQ, ElemType *e)
               
               5)取队首元素GetQhead(SQueue *SQ, ElemType *e)
               
               6)清队列ClearQueue(SQueue *SQ)
               
               队列的链式存储结构
               队列的链接实现称为链队,链队实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头节点,尾指针指向队尾节点即单链表的最后一个节点。为了简便,链队设计成一个带头节点的单链表。
               链队的类型定义如下:
               
               链队列的说明如下。
               .队列以链表形式出现,链首节点为队头,链尾节点为队尾。
               .队头指针为LQ→front,队尾指针为LQ→rear,队头元素的引用为Q→front→data,队尾元素的引用为LQ→rear→data。
               .初始化时,设置LQ→front=LQ→rear=NULL。
               .进队操作与链表中链尾插入操作一样;出队操作与链表中链首删除操作一样。
               .队空的条件为LQ→front==NULL。理论上,只要系统内存足够大,链队是不会满的。
               在链队上实现队列基本操作的函数如下。
               1)队列初始化InitQueue(LQueue *LQ)
               
               2)入队EQueue(LQueue *LQ, ElemType e)
               
               3)出队OQueue(LQueue *LQ, ElemType *e)
               
               4)判空QueueEmpty(LQueue *LQ)
               
               5)取队首元素GetQhead(LQueue *LQ, ElemType *e)
               
               6)清队列ClearQueue(LQueue *LQ)
               
               循环队列中的边界条件判别准则
               判别循环队列的"空"或"满"不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设一个布尔变量来区别队列的空和满;二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合,如果会重合就认为队列已满;三是设置一个计数器记录队列中元素总数,不仅可判别空或满,还可以得到队列中元素的个数。
               双端队列的作用
               双端队列是限定插入和删除操作在线性表的两端进行,可将其看成是栈底连在一起的两个栈,但其与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的,因而每个栈只需一个指针;而双端队列允许两端进行插入和删除元素,因而每个端点必须设立两个指针,如下图所示。
               
               双端队列的示意图
               在实际应用中,可对双端队列的输出进行限制(即一个端点允许插入和删除,另一个端点只允许插入),也可对双端队列的输入进行限制(即一个端点允许插入和删除,另一个端点只允许删除)。可见,采用双端队列可增加应用中的灵活性。
   题号导航      2012年上半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第38题    在手机中做本题