若只设头指针,则入队、出队操作的时间是多长时间？？？

vampillur · 发表于 2020-3-15 22:30:01

设长度为n的链队列用单循环链表表示
若只设头指针,则入队、出队操作的时间是多长时间？？？
若只设尾指针呢？？
又需要多少时间

maloneliu · 发表于 2020-6-17 14:15:01

队列的特点是：先进先出；
单链的特点是：迭代的时候只能向前，不能回头；
在只知道头指针的情况下：
入对：首先要遍历单链，找到尾指针，时间复杂度O(n);
出对：直接访问头指针即可，时间复杂度O(1);
只知道尾指针的情况和上面分析的正好相反。

vampillur · 发表于 2020-6-19 15:30:02

谢谢

		自动登录	找回密码
密码			立即注册