一个QUEUE的链表实现

Question

下面是我使用双链表实现的队列:

QUEUE-EMPTY
if L.head == NIL
    return True
else return False
QUEUE(x):
if L.head == NIL:
    x.prev = NIL
    L.head = x
else
    cur = L.head
    while cur.next != NIL
        cur = cur.next
    cur.next = x
    x.prev = cur
    x.next = NIL
DEQUEUE():
x = L.head
L.head = x.next
x.next.prev = L.head
return x

如何改进?

是否存在使QUEUE 0(1)的平均值?

谢谢! !

Answer 1

见下面的更改和注释:

QUEUE(x):
if L.head == NIL:
    x.prev = x.next = NIL // otherwise you never set up next
    L.head = x
else
    cur = L.head
    while cur.next != NIL
        cur = cur.next
    cur.next = x
    x.prev = cur
    x.next = NIL
DEQUEUE():
// handle empty queue
if L.head == NIL:
    ERROR! // or something
else
    x = L.head
    L.head = x.next
    if x.next != NIL: // handle empty queue
        x.next.prev = L.head NIL // otherwise it points to itself
    return x

要使QUEUE(x)为O(1)，需要保持指向尾部的指针

QUEUE(x):
if L.head == NIL:
    x.prev = NIL
    L.head = L.tail = x
else
    cur = L.tail
    cur.next = L.tail = x
    x.prev = cur
    x.next = NIL
DEQUEUE():
if L.head == NIL:
    ERROR! // or something
else
    x = L.head
    L.head = x.next
    if x.next != NIL:
        x.next.prev = NIL
    else
        L.tail = NIL
    return x

同样，你并不真的需要一个双链表。单链表应该可以很好地工作(除非您还想支持其他操作)。

Answer 2

队列有两种标准实现。

环形缓冲区可以存储在数组中，并带有指向头部和尾部的指针。所有的算术运算都是对数组的长度取模。如果队列尾部赶上了队列头部，则队列已经溢出，不能再使用。

另一个实现使用两个链表。第一个列表按顺序排在队列的前面;第二个列表位于队列的后面，以相反的顺序排列。项目被添加到第二个列表中，并从第一个列表中检索。每当第一个列表为空并且要提取项时，第二个列表将被反转并成为第一个列表，并创建一个新的(空的)第二个列表。

两个实现的插入和读取/删除的时间复杂度都是0(1)。环形缓冲区实现的绝对时间复杂度为0(1)，但它预先定义了队列的最大大小。链表实现的平摊时间复杂度为0(1)，但没有限制队列的最大大小，假设有足够的内存可用。