Java - 我正在将一个栈链表修改为队列链表，但我的出队方法仍像弹出一样行为。

Question

Java - 我正在将一个栈链表修改为队列链表，但我的出队方法仍像弹出一样行为。

3

private Node back目前还没有被使用，而enqueue（之前是push）和dequeue（之前是pop）除了重命名一些东西以外并没有真正被修改。再次强调，这原本是一个栈，但我正在尝试将其修改为队列。我以前用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;
      }    
  }

我不是很理解上面的Node内容。

  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;
  }

我在这里遇到最大的问题是上面的代码目前运行像是弹出（获取和移除列表中最后输入的元素）。

  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为真（否则为假）。

- instago

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lews Therin · Answer 1

我对数据结构不是很擅长，但我认为你的enqueue和dequeue仍然像pop和push一样行为。队列的front应该指向队列头部，而tail则指向最后一个有效对象的下一个位置。因此，tail最终应该指向null。我认为应该像这样：

  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;
  }

- Makoto · Answer 2

这里的主要问题是，队列是先进先出（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;
  }

你正在将新创建的狗元素的下一个节点设置为前端。您需要移到队列的末尾，将最近的节点设置为新节点，新节点设置为null。使用您的代码，它应该看起来像这样：

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;
    }
}