如何使用单链表实现队列,使其ENQUEUE和DEQUEUE占用O(1)？

Question

这是CLRS 3rd的练习:

10.2-3通过单链表L实现队列.操作ENQUEUE和DEQUEUE仍然需要O(1)时间.

使用单链表实现队列并不困难.我的问题是关于时间的复杂性.如何实现取O(1)的ENQUEUE和DEQUEQUE？

我在谷歌上发现的东西就像使用指针来跟踪头部和尾部.现在问题变成如何使用O(1)时间在单链表上跟踪头尾？恕我直言,需要O(n)跟踪尾巴.我对吗？

Answer 1

管理头部和尾部指针需要O(1)时间.

排队:

tail -> next = newNode;
newNode -> next = NULL;
tail = newNode;

出列:

output_node = head;
head = head -> next;
// do whatever with output_node;

注意:在执行指针赋值之前,您还必须执行边界检查和内存分配/解除分配