全部科目 > 嵌入式系统设计师 >
2020年下半年 上午试卷 综合知识
第 17 题
知识点 队列  
章/节 嵌入式系统程序设计  
 
 
在常见的数据结构中,(16)是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构,它的修改遵循先进后出的原则;(17)是一种先进先出的线性表。(18)是取值范围受限的线性表。
 
  A.  链表
 
  B.  队列
 
  C.  栈
 
  D.  串
 
 




 
 
相关试题     栈与队列 

  第34题    2019年下半年  
为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是(34)。

  第48题    2013年下半年  
有空栈S,对下列待进栈元素序列a、b、c、d、e、f进行进栈、进栈、出栈、进栈、进栈、出栈的操作后,桟S的栈顶和栈底元素分别为(48)。

  第54题    2013年下半年  
如果在一个单处理器的系统中有n个进程,则就绪队列中进程的个数最多为(54)。

 
知识点讲解
· 队列
 
        队列
        队列常用于需要排队的场合,如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。
        队列是一种先进先出(FIFO)的线性表,只允许在队列的一端插入元素,而在另一端删除元素。在队列中,允许插入元素的一端称为队尾(rear),允许删除元素的一端称为队头(front)。
        队列的基本运算如下。
        (1)初始化队列initQueue(Q):创建一个空的队列Q。
        (2)判队空isEmpty(Q):当队列为空时返回“真”值,否则返回“假”值。
        (3)入队enQueue(Q,x):将元素x加入到队列Q的队尾,并更新队尾指针。
        (4)出队delQueue(Q):将队头元素从队列Q中删除,并更新队头指针。
        (5)取队头元素frontQueue(Q):返回队头元素的值,但不更新队头指针。
        可以用一组地址连续的存储单元存放队列中的元素,称为顺序队列。由于队中元素的插入和删除限定在两端进行,因此设置队头指针和队尾指针,分别指示出当前的队首元素和队尾元素。
        设队列Q的容量为6,其队头指针为front,队尾指针为rear,头、尾指针和队列中元素之间的关系如下图所示。
        
        队列的头、尾指针与队列中元素之间的关系
        在顺序队列中,为了降低运算的复杂度,元素入队时只修改队尾指针,元素出队时只修改队头指针。由于顺序队列的存储空间容量是提前设定的,所以队尾指针会有一个上限值,当队尾指针达到该上限时,就不能只通过修改队尾指针来实现新元素的入队操作了。若将顺序队列设想为一个环状结构(通过整除取余运算实现),则可维持入队、出队操作运算的简单性,如下图所示,称之为循环队列。
        
        循环队列的头、尾指针示意图
        设循环队列Q的容量为MAXSIZE,初始时队列为空,且Q.rear和Q.front都等于0,如下图(a)所示。元素入队时修改队尾指针,即令Q.rear=(Q.rear+1)% MAXSIZE,如下图(b)所示。元素出队时修改队头指针,即令Q.front=(Q.front+1)% MAXSIZE,如下图(c)所示。
        
        循环队列的头、尾指针示意图
        根据队列操作的定义,当出队操作导致队列变为空时,就有Q.rear==Q.front,如上图(d)所示;若入队列操作导致队列满,则也有Q.rear==Q.front,如上图(e)所示。在队列空和队列满的情况下,循环队列的队头、队尾指针指向的位置是相同的,此时仅根据Q.rear和Q.front之间的关系无法判定队列的状态。为了区分队空和队满,可采用两种处理方式:其一是设置一个标志域,以区别头、尾指针的值相同时队列是空还是满;其二是牺牲一个元素空间,约定以“队列的尾指针所指位置的下一个位置是头指针”表示队列满,如上图(f)所示,而头、尾指针的值相同时表示队列为空。
        设队列中的元素类型为整型,则循环队列的类型定义为:
        
        【函数】创建一个空的循环队列。
        
        【函数】判断队列是否为空。
        
        【函数】元素入循环队列。
        
        【函数】元素出循环队列。
        
        队列的链式存储也称为链队列。为了便于操作,可给链队列添加一个头结点,并令头指针指向头结点,如下图所示。在这种情况下,队列为空的判定条件是头指针和尾指针相同,且均指向头结点。
        
        链队列示意图



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2023 All Rights Reserved
软考在线版权所有