题目
【填空题】设长度为 n 的链队列用单循环链表表示,若只设头指针,则入队和出队操作的时间复杂度分别为 ______ 和 ________ ;若只设尾指针,则入队和出队操作的时间复杂度分别为 ______ 和 ________
【填空题】设长度为 n 的链队列用单循环链表表示,若只设头指针,则入队和出队操作的时间复杂度分别为 ______ 和 ________ ;若只设尾指针,则入队和出队操作的时间复杂度分别为 ______ 和 ________
题目解答
答案
["O(n)","O(1)","O(1)","O(1)"]
解析
步骤 1：链队列的入队操作
- 当链队列用单循环链表表示时，入队操作需要将新节点插入到队列的尾部。如果只设头指针，需要遍历整个链表找到尾部，因此时间复杂度为 O(n)。
- 如果只设尾指针，可以直接在尾部插入新节点，因此时间复杂度为 O(1)。
步骤 2：链队列的出队操作
- 出队操作需要删除队列的头部节点。如果只设头指针，可以直接删除头节点，因此时间复杂度为 O(1)。
- 如果只设尾指针，需要遍历整个链表找到头节点，因此时间复杂度为 O(n)。
- 当链队列用单循环链表表示时，入队操作需要将新节点插入到队列的尾部。如果只设头指针，需要遍历整个链表找到尾部，因此时间复杂度为 O(n)。
- 如果只设尾指针，可以直接在尾部插入新节点，因此时间复杂度为 O(1)。
步骤 2：链队列的出队操作
- 出队操作需要删除队列的头部节点。如果只设头指针，可以直接删除头节点，因此时间复杂度为 O(1)。
- 如果只设尾指针，需要遍历整个链表找到头节点，因此时间复杂度为 O(n)。