Java:如何基于 Node 类创建队列

Question

我正在尝试使用两个类(一个 Node 类和一个 Queue 类)来创建一个队列来进行分配。这是节点类:

class Node
{
 protected Node next;

 public Node()
 {
    next = null;
 }
}

此类基本上使用 Node.next 对象将数据链接在一起。我已经成功地能够使用 push() 和 pop() 创建一个堆栈，因为这两个操作发生在同一端，因此该点只是在指向新添加的节点和前一个节点之间进行操作。

但是，我在理解基于类似结构创建队列的逻辑时遇到了一些困难。我的队列类看起来像这样:

class Queue
{
 private Node footer;
 private Node header;

 public Queue()
 {
    footer = null;
    header = null;
 }

 public void add(Node newNode)
 {   
    //Adds onto the queue from the 'footer' end.
 }  

 public Node remove()
 {
    //Removes from the queue from the 'header' end.
 }

这是我的理解:(1)页眉和页脚指向同一个第一个节点。 (2) 后续添加应更改页脚以指向添加的节点，但页眉保留在第一个添加的节点上。 (3) 删除时， header 应指向下一个最旧的节点。

这是我无法弄清楚的(以及它与从堆栈中弹出的不同之处)。鉴于此队列中有超过 2 个节点，如何使 header 指向“下一个最旧的节点”？我知道如果我将 header.next 链接到队列中的下一个节点，我可以做到这一点，但是如何访问下一个节点以便它可以指向它？

我想过如何在 add() 中，newNode.next 应该指向下一个 newNode(堆栈的反向方向)，但这行不通，因为下一个 newNode 还不存在。.另一个想法的方法是修改 Node 类以具有 Node.previous 来向后指向，但我会违反此分配的规范。

我的导师暗示了一些关于“header.next 将指向第二个项目，因为页眉和页脚最初指向第一个节点”，并且执行此操作的方法非常简单。但是，我一直在绘制它的工作原理，并且我很困惑初始指向同一节点将如何允许 header.next “自动”指向下一个最旧的节点，特别是如果添加越来越多的节点并且页脚最终与页眉分开超过 2 个节点。关于 OOP 有什么我没有看到的吗？

任何帮助都会很棒!

Answer 1

扩展并提供 @Sanjeev 答案的微妙替代方案(我认为你的老师暗示过这一点):

不要使用footer来存储“实际”节点，而是将其用作占位符:将其声明为final变量，在构造函数中对其进行初始化并确保a) 它的 next 节点始终是您的 header (这将称为 circular list )，或者它的 next 节点为 null。

你能看到这如何解决你的“这不起作用，因为下一个 newNode 还不存在”问题:当然，你不能将添加的最后一个节点指向添加之前将添加的下一个节点它 - 相反，您将它指向这个“虚拟”节点 - 这是将添加的下一个节点的占位符(如果是的话)。

add(Node newestNode){
   identify the last node added as the one whose next property is the footer. 
   change the next property of that node from footer to this new newestNode 
   set the next property of this new newestNode to footer 
}

最好将添加的最后一个节点识别为页脚所指向的节点(而不是指向页脚的节点)，如果允许您将 previous 作为以及节点上的 next 属性，但听起来您不允许这样做。当然，由于我们使用页脚作为“虚拟节点”，我们可以简单地使用 footer.next 就像 footer.previous 一样，并让它指向向后前锋，但我会让你考虑一下这有多干净。这里还有其他选择，我也将让您考虑。

How do I get the header to point to the 'next oldest node'`

“最旧”的节点是第一个添加的。 “最新”节点是最后添加的节点。其余节点的顺序如何存储？与堆栈中的方式相同 - 通过遍历作为实例变量存储在节点上的引用链。我想说的要点是，当实现为 linked data structures 时，堆栈和队列，比您想象的要相似得多，至少从以下方面来看:迭代任何链接的数据结构都是通过遍历这些链接来完成的 - 不要太了解坚持你正在朝不同方向“移动”的事实 - 相同的基本原则适用:

Node remove(){ 
    identify the "oldest" node as header.next. 
    Store a reference to that node so you can return it. 
    identify the "second oldest node" as header.next.next 
    change header.next to header.next.next
    return the reference to the old header.next you saved above.         

(请注意，使用页眉/页脚作为占位符，而不是像 @Sanjeev 建议的那样在其中存储“实际”节点，这是不必要的，但它会让您的生活更轻松 - 例如，通过帮助您避免大量空检查)