java 使用链表的队列

Queue Using Linked List

提问by CosmicComputer

I am implementing a linked queue in Java. However, there is/are error/s when I run my code.

我正在用 Java 实现一个链接队列。但是，当我运行我的代码时有/有错误。

public class LinkedQueue<E> implements Queue<E> {
   private int count;
   private Node<E> front, rear;

   public LinkedQueue() {
      count = 0;
      front = rear = null;
   }

   public void enqueue (E element) {
      Node<E> node = new Node<E> ();

      if (isEmpty())
         front = node;
      else
         rear.setNext (node);

      rear = node;
      count++;
   }

   public E dequeue() throws QueueEmptyException {
      if (isEmpty())
         throw new QueueEmptyException  ("queue");

      E result = front.getElement();
      front = front.getNext();
      count--;

      if (isEmpty())
         rear = null;

      return result;

   }

   public E first() throws QueueEmptyException {
      if (isEmpty())
         throw new QueueEmptyException ("queue"); 

      return front.getElement();
   }


   public boolean isEmpty() {
      return (front == rear);
   }


   public int size() {
      return count;
   }


    public E front() throws QueueEmptyException {       
        if (isEmpty())
            throw new QueueEmptyException("Queue underflow.");
        return (E) front.getNext();
    }
}

I've been configuring forever what's wrong in my LinkedQueue. Please help me fix the code. I'm new in Java and maybe the mistakes are caused by sytax errors.

我一直在配置 LinkedQueue 中的错误。请帮我修复代码。我是 Java 新手，可能错误是由语法错误引起的。

回答by CosmicComputer

You can use all the functionality of a Queue from the java.util.LinkedList generic class. Use the addLast method to enqueue an element, and the removeFirst method to dequeue an element. Since LinkedList is doubly linked, you should see all the performance benefits of a Queue.

您可以使用 java.util.LinkedList 泛型类中 Queue 的所有功能。使用 addLast 方法使元素入队，使用 removeFirst 方法使元素出队。由于 LinkedList 是双向链接的，您应该会看到队列的所有性能优势。

回答by WeMakeSoftware

java.util.LinkedListalready implements a Queue.
Why don't use that?

java.util.LinkedList已经实现了Queue.
为什么不用那个？

Queue<T> queue = new LinkedList<>();

回答by Erich Schreiner

Your enqueue() method does nothing with the element passed in. Probably you want to pass it on to the Node's constructor?

您的 enqueue() 方法对传入的元素没有任何作用。您可能想将它传递给 Node 的构造函数？

回答by kajacx

This looks extreamly suspicious:

这看起来非常可疑：

public void enqueue (E element) {
  Node<E> node = new Node<E> ();

  if (isEmpty())
     front = node;
  else
     rear.setNext (node);

  rear = node;
  count++;

}

}

the parameter elementis never used. Try

element从不使用该参数。尝试

Node<E> node = new Node<E> (element);

or something.

或者其他的东西。

回答by san242

Here is the sample implementation of Linked list using Queues.

这是使用队列的链接列表的示例实现。

public class LinkedQueue<E> {

    private DoublyLinkedNode<E> head;
    private DoublyLinkedNode<E> tail;

    int size;

    public void enqueue(E item) {

        DoublyLinkedNode<E> oldTail = this.tail;

        DoublyLinkedNode<E> newTailnode = new DoublyLinkedNode<E>(item);

        if(oldTail != null){
            oldTail.setNextNode(newTailnode);
            newTailnode.setNextNode(null);
            this.tail = newTailnode;

        }else{
            this.tail = newTailnode;
            this.head = newTailnode;
        }
        size++;
    }

    public boolean isEmpty() {
        return this.head == null;
    }
    public int length(){
        return size;
    }

    public E deque() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }

        E data = this.head.getData();

        this.head = this.head.getNextNode();

        size--;

        return data;
    }

    public E peek() {
        return this.head.getData();
    }

    public static void main(String[] args) {
        LinkedQueue<Double> queuelist = new LinkedQueue<Double>();
        queuelist.enqueue(60.0);
        queuelist.enqueue(12.0);
        queuelist.enqueue(16.4);
        queuelist.enqueue(26.5);

        queuelist.deque();
        System.out.println("queuelist.peek:"+ queuelist.peek());

        queuelist.deque();
        System.out.println("queuelist.length:"+queuelist.length());
        System.out.println("queuelist.peek:"+ queuelist.peek());
    }
}

public class DoublyLinkedNode<E> {
    private E data;
    private DoublyLinkedNode<E> nextNode;
    private DoublyLinkedNode<E> previousNode;

    public DoublyLinkedNode(E data) {
        this.data = data;
    }
    public E getData() {
        return data;
    }
    public DoublyLinkedNode<E> getNextNode() {
        return nextNode;
    }
    public void setNextNode(DoublyLinkedNode<E> nextNode) {
        this.nextNode = nextNode;
    }

    public DoublyLinkedNode<E> getPreviousNode() {
        return previousNode;
    }

    public void setPreviousNode(DoublyLinkedNode<E> prevNode) {
        this.previousNode = prevNode;
    }

    @Override
    public String toString() {
        return this.data.toString();
    }

}