长度为n的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？
n11n
O(n) O(1)
O（1）O（1）
O(n). O(1) O(1) , O(1)
出o（1），入n，出入o（1）
以头插法为例：
只设头指针，入队在首节点实现，但需要遍历到尾节点改变指针指向，故为O(n)；出队需要遍历到尾节点，为O(n)
只设尾指针，入队同理，因为已经到尾节点故为O(1)；出队需要通过循环遍历到尾节点前一个节点，故为O(n)
缘小遇 回复 缘小遇： 看了一下答案，不是很明白只设尾指针出队O(n)，因为出队把尾节点删除，此时为了保持循环链表的结构，就需要尾节点前一个节点的的指针去指向头节点，又无法向前，就只能遍历过来。如果有明白的同学能指正，非常感谢！
Austin00 回复 缘小遇： 其实可以 直接把写一个元素的数据复制到当前节点，然后把下一个节点删除，这样就能删除当前节点了。不用必须到达前一个节点的位置
只设头指针，入队o(n)出队 o(n)
只设尾指针 入队o(1)出队 o（1）
队列的特点是：先进先出； 单链的...
用户登录可进行刷题及查看答案
队列的特点是：先进先出； 单链的特点是：迭代的时候只能向前，不能回头； 在只知道头指针的情况下： 入队：首先要遍历单链，找到尾指针，时间复杂度O(n); 出队：直接访问头指针即可，时间复杂度O(1); 只知道尾指针的情况下，出入队时间均为O(1)，因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案