使用鏈接列表實現隊列

Question

我想了解add方法如何爲修訂工作ListQueue。任何幫助都感激不盡。我無法在網上找到任何完整的解釋，但不幸的是我無法理解它。

private Cell frontCell,backCell; 

    @Override 
public void add(char x) { 
    Cell newCell = new Cell(x); 
    if(frontCell == null){ 
     frontCell = backCell = newCell; 
    }else{ 
     backCell.next = newCell; 
     backCell = newCell; 
    } 
} 

還有一個內部類「小區」

public class Cell{ 

    char data; 

    Cell next; 

    public Cell(char data){ 
     this.data = data; 
     next = null; 
    } 
} 

「frontCell」存儲在隊列的開始時的細胞和「backCell」存儲單元在後面。

「frontCell」引用包含剛剛添加的數據的「backCell」。然後如果添加了另一個字符「backCell.next = newCell」和「backCell = newCell」。

隊列中正面和背面單元格之間的單元格是如何存儲的？

「frontCell」的引用是如何設置爲「backCell」的？

Answer 1

我不是專家，但我會試着解釋我理解它的方式。

當你創建隊列時它是空的，所以它意味着前面的單元格和後面的單元格都是空的。

然後，當添加新的小區（小區1）

Cell newCell = new Cell(x) 

新單元存儲的值x和因爲你沒有正面之間插入和背面，然後它進入其下一個單元是空如果因爲我說你的frontcell爲空

if(frontCell == null){ 
    frontCell = backCell = newCell; 
} 

這裏新小區正面和背面，它的下一個單元格爲空，因爲沒有其他物品。

當您添加另一個小區（小區2）這時候，如果代碼沒有被觸發，因爲前面是不是空了，所以執行的代碼是

backCell.next = newCell; 
    backCell = newCell; 

這裏的最後一個單元格（你唯一的一個）將其先前爲空的下一個單元更改爲指向第二個單元，然後參考後面的單元從第一個單元改變爲第二個單元。如果你在這一點上調試代碼，你會碰到這樣的

firstcell= Cell1 
Cell1.next= Cell2 
Cell2.next = null 
back = Cell2 

而且如果添加另一個單元格，你將有

firstcell= Cell1 
Cell1.next= Cell2 
Cell2.next = Cell3 
Cell3.next=null 
back = Cell3 

我希望這可以幫助你undertand更好

Answer 2

只有當frontCell爲空時，即當隊列爲爲空時，纔會觸發行frontCell = backCell = newCell。這是有道理的 - 當你將一個元素添加到一個0元素的隊列中時，它將變成一個1元素的隊列，所以正面和背面的單元格是相同的。

如果隊列中已經存在單元，則隊列中的最後一個元素的下一個指針指向最新的加法，然後將新加入設置到後面。

空隊列：

[] 
/\ 
f b 

添加一種元素

[E1] 
/\ //front and back are pointing 
f b 

多元件隊列之前添加：

[E1->E2->E3->(null)] 
/  \ 
f   b 

後：

[E1->E2->E3->E4-null] 
/   \ 
f    b 

Answer 3

對於每個單元格，您的單元類別爲data，而next引用列表中的下一個單元格，這就是它們如何全部鏈接在一起。

if(frontCell == null)，被詢問是否該列表是空的，如果是的話frontCell = backCell = newCell;，這意味着你要添加的新單元是列表中唯一的細胞，因此它既是frontCell，也是backcell。

else如果列表不爲空，backCell.next = newCell;您要添加的新小區由backCell聯繫，和你的newCell是新backCell（backCell = newCell;）。

嘗試在紙上繪製像這樣的數據結構可能會更容易（如this excellent free Data Structures textbook顯示），並嘗試添加並移除一些單元格，遵循代碼告訴您發生的情況。