如何使用单链表实现队列，使其ENQUEUE和DEQUEUE占用O（1）？
这是CLRS 3rd的练习：
10.2-3通过单链表L实现队列。操作ENQUEUE和DEQUEUE仍然需要O（1）时间。
使用单链表实现队列并不困难。 我的问题是关于时间的复杂性。 如何实现带O（1）的ENQUEUE和DEQUEQUE？
我在谷歌上发现的东西就像使用指针跟踪头部和尾部。 现在问题变成如何使用O（1）时间跟踪单链表上的头尾？ 恕我直言，需要O（n）跟踪尾部。 我对吗？
管理头部和尾部指针需要O（1）时间。
排队：
tail -> next = newNode; newNode -> next = NULL; tail = newNode;
出列：
output_node = head; head = head -> next; // do whatever with output_node;
注意：在执行指针赋值之前，还必须执行边界检查和内存分配/解除分配
它很简单，只需在末尾加入enque，然后在前面使用deque，并设置2指针（或unique_ptrs）指向end和front，这样做。 像这样：
struct queue{ Node *head; Node *tail; int node_cnt; // well, you can put this in if you like }; Node *enque(Node *head, int data) { Node *p = new Node(Node data); if (head) { head->next = p; head = p; } else head = p; ++ q.node_cnt; return head; } int deque(Node *tail) { Node *p = tail; int x = tail->data; tail = tail.next(); delete p; -- q.node_cnt; return x; }
上面只是一个演示代码，但你可以看到你不需要遍历整个列表来enque或deque。
如果允许使用std容器， std::list就是你要找的东西。
如果没有（我认为是这种情况），尝试回答这个问题：你为什么需要执行n次操作？ 你能把指针存放到最后吗？
比如，你有一个明确的链表和一个指针head和一个列表项有next指针。
- 如果您将新项目排入队列，则只需添加一个新项目，修改以前的“第一个”项目的
next指针，并将head指针重新指向新项目。 这是3次操作= O（1） - 如果您将项目出列，则将
last指针移动到last一个项目的next指针`指向的指针并删除该项目 – 2个操作= O（1）