入队和出队如何在队列的链接实现下工作

Question

Enqueue如何处理链开始时为空的特殊情况以及当链以一个节点开始时的出队过程。

Answer 1

的OpenJDK implementation使用两个招数：

1. 的队列包含一个盲元件总是存在，即使是在空队列。盲元素始终是队列中的第一个元素，但在课堂外不可见。

2. 队列实际上是一个环。我们知道我们达到了currentElement.next == blind的最后一个元素。

下图显示了长度为0（左）和长度为1（右）的队列。

使用这些技巧的好处是：

• 没有空指针
• 没有的if-else添加/排队元素

对于删除/双端队列我们仍然必须检查队列是否为空。

添加

newElement.next = head.next; 
newElement.prev = head; 
newElement.prev.next = newElement; 
newElement.next.prev = newElement; 

删除

if (head.next == head) { 
    // ERROR, queue is empty 
} else { 
    removedElement.next.prev = removedElement.prev; 
    removedElement.prev.next = removedElement.next; 
} 

注意，是绝对可以实现一个队列没有这些技巧，只使用一个额外的if-else语句。 以下图像表示长度为0（左）和长度为1（右）的天真执行的队列。

添加

if (head == null) { 
    // queue is empty 
    head = newElement; 
} else { 
    // add to head 
} 

删除

if (head == null) { 
    // ERROR, queue is empty 
} else { 
    // remove from tail 
}