Question

数据结构：用带头循环链表表示队列的问题

Answer 1

分类: 电脑/网络 >> 程序设计 >> 其他编程语言
问题描述:

用带头循环链表表示队列（设队列长度为N）

若只设 头 指针，则出队列和入队列的时间复杂度分别是多少？

若只设 尾 指针，则出队列和入队列的时间复杂度分别是多少？

我的答案：

若只设 头 指针，则出队列O（1）；入队列O（N）

若只设 尾 指针，则出队列O（1）；入队列O（1）

对吗？

解析:

前提：队列中的结点从队尾插入，从队头删除；队列中的结点的指向是从队头指向队尾，因为是循环链表，则队尾结点的下一个结点是队头。

如果只设头指针，则出列容易，头指针往后移一个就行；入列则要遍历整个队列，确定队尾后再插入，所以出列是O(1)，入列是O(n)

如果只设尾指针，则入列时直接插入，出列只须后移一个结点即可找到队头结点，都是常数级的时间耗费，即都是O(1)

一般来说循环队列不用设头指针，只需一个指向尾结点的指针就行了，确定头和尾都很容易。