0

这是我使用双向链表的队列实现：

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 O(1) ？

谢谢 ！！

4

2 回答 2

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

此外，您实际上并不需要双链表。单链表应该可以正常工作（除非您还想支持其他操作）。

于 2013-03-28T12:33:01.970 回答
0

队列有两种标准实现。

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

另一种实现使用两个链表。第一个列表是队列的最前面，按顺序排列；第二个列表是队列的后面，以相反的顺序。项目被添加到第二个列表并从第一个列表中检索。每当第一个列表为空并且要获取一个项目时，第二个列表就会反转并成为第一个列表，并创建一个新的（空的）第二个列表。

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

于 2013-03-28T15:47:11.683 回答