2. 考研
  3. 请设计一个队列，要求满足： 初始时队列为空； ②入队时，允许增加队列占用空间； ③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减； ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题： 该队列是应选择链式存储结构

请设计一个队列，要求满足： 初始时队列为空； ②入队时，允许增加队列占用空间； ③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减； ④入队操作和出队操作的时间复杂度始终保持为O(1)。 请回答下列问题： 该队列是应选择链式存储结构

admin2020-06-17  56
问题 请设计一个队列，要求满足：
初始时队列为空；
②入队时，允许增加队列占用空间；
③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；
④入队操作和出队操作的时间复杂度始终保持为O(1)。
请回答下列问题：
该队列是应选择链式存储结构，还是应选择顺序存储结构?
选项
答案顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析：要求①容易满足；链式存储方便开辟新空间，要求②容易满足：对于要求③，出队后的结点并不真正释放，用队头指针指向新的队头结点，新元素入队时，有空余结点则无须开辟新空间，赋值到队尾后的第一个空结点即可，然后用队尾指针指向新的队尾结点，这就需要设计成一个首尾相接的循环单链表，类似于循环队列的思想。设置队头、队尾指针后，链式队列的入队操作和出队操作的时间复杂度均为O(1)，要求④可以满足。因此，采用链式存储结构(两段式单向循环链表)，队头指针为front，队尾指针为rear。
解析
转载请注明原文地址:https://kaotiyun.com/show/VU3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)