Java：如何基于节点类创建队列

Question

我尝试使用两个类创建一个队列，一个节点类和一个队列类用于分配。下面是节点类：

class Node
{
 protected Node next;

 public Node()
 {
    next = null;
 }
}

此类基本上使用节点将数据链接在一起。下一个目标。我已经成功地用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） 删除时，标头应指向下一个最旧的节点

以下是我无法理解的（以及它与从堆栈中弹出不同的地方）。如果此队列中有2个以上的节点，如何使标头指向“下一个最早的节点”？我知道我可以这样做，如果我链接标题。在队列中的下一个节点旁边，但是如何访问下一个节点，以便它可以指向它

我考虑了如何在add（）中创建新节点。next应该指向下一个newNode（堆栈的反向），但这不起作用，因为下一个newNode还不存在。。另一个想法是修改Node类以拥有一个节点。前面提到了一种向后指的方法，但我会破坏这个任务的规范

我的指导老师暗示了一些关于“header.next将指向第二个项目，因为页眉和页脚最初指向第一个节点”，这样做的方法非常简单。然而，我一直在画这是如何工作的，我不知道初始指向同一个节点将如何允许标头。“自动”旁边指向下一个最旧的节点，尤其是如果添加了越来越多的节点，并且页脚最终与页眉之间的距离超过2个节点时。是不是有什么我没看到的东西

任何帮助都会很好

Answer 1

您需要做的第一件事是确保您创建的第一个节点是最老的，因此它应该是第一个根据先进先出（FIFO）原则从队列中删除的节点。要将其存档，您可能需要修改您的添加方法，例如，顺便说一下，这个例子是基于单链表实现的

   void add(char new_data) 
{ 

    /* 1. alloc the Node and put data*/
    Node new_Node = new Node(new_data); 

    /* 2. Make next of new Node as head */
    new_Node.next = head; 

    /* 3. Move the head to point to new Node */
    head = new_Node; 
}   

然后，您需要一个删除方法，该方法将首先删除列表中最旧的节点记住在队列中删除的顺序是先进先出（FIFO） 也就是说，这种删除方法应该对您有所帮助

    void remove() 
{ 
    // Store head node 
    Node temp = head, prev = null; 

    // If head node itself holds the key to be deleted 
    if (temp != null ) 
    { 
        head = temp.next; // Changed head 
        return; 
    } 

    // Search for the key to be deleted, keep track of the 
    // previous node as we need to change temp.next 
    while (temp != null) 
    { 
        prev = temp; 
        temp = temp.next; 
    }     

    // If key was not present in linked list 
    if (temp == null) return; 

    // Unlink the node from linked list 
    prev.next = temp.next; 
} 

这在我的链接列表中对我有效

Answer 2

以下是sudo代码，它将帮助您入门

public void add(Node newNode)
 {   
    if footer is null ?
    then
     header = newNode and footer = newNode;
    else 
     footer.next = newNode and footer = newNode;
    end if
 }

 public Node remove()
 {
    Node returnMe = header;
    if header is not null?
    then
      header = header.next
      if header is null
      then
         footer = null;
      endif
    end if
    return returnMe;
 }

Answer 3

进一步展开，并提供@Sanjeev答案的微妙替代方案（我认为您的导师暗示的答案）：

与其使用footer存储“实际”节点，不如将其用作占位符：将其声明为final变量，在构造函数中初始化它，并确保a）它的next节点始终是header（这将被称为circular list），或者它的next节点为空

你能看到这是如何解决“因为下一个新节点还不存在，所以无法工作”问题的吗：当然，你不能在添加前将最后一个节点指向下一个要添加的节点，而是将它指向这个“虚拟”节点，这是下一个要添加节点的占位符，什么时候，如果是的话

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 
}

最好将添加的最后一个节点标识为footer指向的节点（而不是指向footer的节点），如果允许您在节点上具有previous和next属性，这将很容易，但听起来好像不允许您这样做。当然，因为我们使用页脚作为“哑节点”，所以我们可以简单地使用^ {CD8}}的方式^ {< CD9}}，使它指向向后而不是向前，但是我会让你考虑一下这将是多么干净。这里还有其他的选择，我也会让你考虑。

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

“最早的”节点是第一个添加的节点。“最新”节点是最后添加的节点。其余节点的顺序是如何存储的？与在堆栈中的方式相同—通过遍历作为节点上的实例变量存储的引用链。我想说的主要一点是，当堆栈和队列实现为linked data structures时，它们比您想象的要相似得多，至少从a开始：遍历任何链接的数据结构是通过以下方式完成的：遍历这些链接-不要太在意您正在向不同的方向“移动”-相同的基本原则适用：

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建议的那样在其中存储“实际”节点，这是没有必要的，但它会让您的生活更轻松——例如，通过帮助您避免大量的空检查）

Answer 4

How do I get the header to point to the 'next oldest node', given that I have more than 2 nodes in this queue? I know I can do this if I link header.next to the next node in the queue, but how can I access the next node so that it can point to it?

要使标头指向该节点，只需执行header = header.next。原因是Java objectt分配是通过引用进行的。从标题开始。接下来是节点类型，头是节点类型，它将复制头的地址。页眉的旁边，即页眉是高级的一个位置

I thought about how in add(), the newNode.next should point to the next newNode (reverse direction of a Stack), but this can't work because the next newNode isn't in existence yet..

我认为没有必要考虑反向。原因是，对于添加，它是将元素添加到队列的尾部/页脚。唯一的特殊情况是队列没有任何元素（footer == header == null），1个元素：（footer = header = element），其他情况：页眉不会更改，但需要将元素附加到页脚，然后使页脚指向新节点

当只有1个元素时，footer.next == header.next == null