3

private Node back还没有使用，并且enqueue（它是 push）和dequeue（它是 pop）除了重命名一些东西之外还没有真正被修改过。同样，这最初是一个堆栈，但我正在尝试将其修改为一个队列。我之前用 s 完成了非链表队列和堆栈int，但是对于对象和链表，我有点迷路了。

public class DogQueue 
{
    private Node front = null;
    private Node back = null;
    private Node element = null;
    private int counter = 0;

以上只是设置变量。

  private class Node //This sets up the Linked List
                     //Data Structure with nodes.
  {
      private Dog doggy;
      private Node nextNode;
      private Node firstNode;

      Node(Dog newDog)
      {
          doggy = newDog;
      }    
  }

我不太明白的节点东西在上面。

  public void enqueue(Dog aDog) //This should enqueue
                                //an object of type Dog.
  {       
      Node dogNode = new Node(aDog);
      dogNode.nextNode = front;
      counter++;
      front = dogNode;
  }

上面这里的push方法没有修改，只是改名了。

  public Dog dequeue()      //This should output
                            //the first entry in the list.
  {
      Dog firstDog = front.doggy;
      element = front.firstNode;
      counter--;
      return firstDog;
  }

上面是我遇到最多麻烦的地方——目前它的行为类似于 pop（获取和删除列表中最后输入的元素）。

  public boolean isFull()   //Checks to see if List is Full.
  {
      return ( counter == 5 );
  }

我将计数器设置为最多 5，这样我就可以调试 isFull。

  public boolean isEmpty()  //Checks to see if List is empty
  {
      if ( counter == 0 )
        {
            return true;
        } else {
            return false;
        }
  }

这只是说如果计数器为零，则 isEmpty 为真（否则为假）。

}
4

2 回答 2

0

我不擅长数据结构，但我相信你的入队和出队仍然表现得像 pop 和 push。前面应该指向队列的头部，尾部应该指向最后一个有效对象。所以尾巴最终应该指向空。我认为它应该是这样的：

  public void enqueue(Dog aDog)
     {
         Node dogNode = new Node(aDog);

         counter++;
         if (front == null)
             front = back = dogNode;
         else
         {
             back.nextNode = dogNode;
             back = dogNode;

         }
     }
  public Node dequeue()      
  {
      if(front == null) return null;
      Dog firstDog = front ;
      front = front.nextNode;
      counter--;
      return firstDog;
  }
于 2012-10-03T23:49:24.120 回答
0

这是主要问题。队列是 FIFO（先进先出），而堆栈是 LIFO（后进先出）。对于队列，您入队的第一个元素是您收到的第一个元素，而您压入堆栈的最新元素是您收到的第一个元素。

为此，让我们稍微检查一下您的代码。

  public void enqueue(Dog aDog) { //This should enqueue an object of type Dog.
      Node dogNode = new Node(aDog);
      dogNode.nextNode = front;
      counter++;
      front = dogNode;
  }

您正在将新 dog 元素的下一个节点设置在前面。您必须走到队列的末尾，将最近的节点设置为新节点，并将新节点设置为空。使用您的代码，它看起来像这样：

public void enqueue(Dog aDog) {
    if(front == null) {
        front = new Node(aDog);
        back = front; // back will move later
    } else {
        Node tmp = new Node(aDog);
        tmp.setFirstNode(back);
        back.setNextNode(tmp);
        back = tmp;
    }
}

  public Dog dequeue() {      //This should output the first entry in the list.
      Dog firstDog = front.doggy;
      element = front.firstNode;
      counter--;
      return firstDog;
  }

至少，这确实显示了队列中的第一件事。但它实际上并没有移动头指针！使用您的代码来执行此操作，它看起来像这样：

public Dog dequeue() {
    if(head == null) {
        return null;
    } else {
        Dog tmp = front.getDoggy()
        front = front.getNextNode(); //move the front to point to the next location
        front.getFirstNode().setNextNode(null); //sever the link to the first element 
        front.setFirstNode(null); //sever the link to the first element
        return tmp;
    }
}
于 2012-10-04T00:04:39.273 回答