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

admin2020-06-17  32

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

选项

答案顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析:要求①容易满足;链式存储方便开辟新空间,要求②容易满足:对于要求③,出队后的结点并不真正释放,用队头指针指向新的队头结点,新元素入队时,有空余结点则无须开辟新空间,赋值到队尾后的第一个空结点即可,然后用队尾指针指向新的队尾结点,这就需要设计成一个首尾相接的循环单链表,类似于循环队列的思想。设置队头、队尾指针后,链式队列的入队操作和出队操作的时间复杂度均为O(1),要求④可以满足。因此,采用链式存储结构(两段式单向循环链表),队头指针为front,队尾指针为rear。

解析
转载请注明原文地址:https://kaotiyun.com/show/VU3i777K
0

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