入隊和出隊如何在隊列的鏈接實現下工作

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 
}