使用链接列表实现队列

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显示），并尝试添加并移除一些单元格，遵循代码告诉您发生的情况。