什么是基于单向链表的数据结构，使得排队和取消排队都采用 O(1)？

Question

一个结构如何实现基于简单链表的抽象数据类型文件，使得ENQUEUE和DEQUEUE过程在O(1(中？约束：实现队列的结构必须仅由单个字段指向(例如：头、尾或元素数量等(

我的理解是把这份单独的清单从头到尾传阅。

但即使在这种情况下，仍然需要两个指针：头和尾来满足O(1(。

但是，该问题要求队列仅由一个字段指向。

有什么想法或暗示吗？

Answer 1

我认为这对于循环链表是可行的，在循环链表中，你指向尾部，这样你就可以访问O(1(中的头作为tail.next。

class Node<T> {
T value;
Node<T> next;
Node(T value, Node<T> next) { this.value = value; this.next = next; }
}
class Queue<T> {
Node<T> tail = null;
void enqueue(T t) {
if (tail == null) {
tail = new Node<T>(value, null);
tail.next = tail;
} else {
Node<T> newTail = new Node<T>(value, tail.next);
tail.next = newTail;
tail = newTail;
}
}
T dequeue() {
if (tail == null) throw new NoSuchElementException();
Node<T> head = tail.next;
T result = head.value;
if (head == tail) {
tail = null;
} else {
tail.next = head.next;
}
return result;
}
}