Java队列链表

Question

在学校我们正在学习抽象数据结构。我们的任务是在java中实现一个链表。出于某种原因，我的队列仅将队列的每个第二个元素出队。也许有人可以告诉我我的错误，因为我不知道了。 BTW我使用BlueJ的，所以不要对PROGRAMM的起点难怪编码：d

的离队方法

public Car dequeue() 
{ 
    Car c = new Car(head); 

    if(c != null){ 

      if (head.getLast() == tail) { 

       if(tail == null){ 

        head = null;        
        return c; 
       }      
       else {       
        head = tail;        
        tail = null;       
        return c;      
       } 
      }      
      else {      
       head = head.getLast();      
       return c;       
      } 
    }   
    return c; 
} 

Car对象

public class Car 
{ 
    private String driver; 
    private Car last; 

    public Car(String pDriver) 
    { 
     driver = pDriver; 
    } 

    public Car(Car c) 
    { 
     this.driver = c.getDriverName();   
     this.last = c.getLast(); 
    } 

    public String getDriverName() 
    { 
     return driver; 
    } 

    public Car getLast() 
    { 
     return last; 
    } 

    public void setLast(Car pLast) 
    { 
     last = pLast; 
    } 
} 

Answer 1

看看，它是一个动态队列实现。

汽车（这仅仅是一个汽车，而不是一个队列节点）

public class Car { 

    private String driver; 

    public Car(String driver) { 
     this.driver = driver; 
    } 

    @Override 
    public String toString() { 
     return "Car (" + driver + ")"; 
    } 

} 

QueueForCars（实现一个队列，只有拥有汽车交易）

public class QueueForCars { 

    private class Node { 
     Car value; 
     Node previous; 
    } 

    private Node head; 
    private Node tail; 
    private int size; 

    public QueueForCars() { 
     tail = null; 
     head = null; 
     size = 0; 
    } 

    public void enqueue(Car value) { 

     Node newNode = new Node(); 
     newNode.value = value; 
     newNode.previous = null; 

     if (isEmpty()) { 
      head = newNode; 
      tail = newNode; 
     } else { 
      tail.previous = newNode; 
      tail = newNode; 
     } 

     size++; 

    } 

    public Car dequeue() { 

     if (!isEmpty()) { 

      Car value = head.value; 

      if (head == tail) { 
       head = null; 
       tail = null; 
      } else { 
       Node temp = head; 
       head = head.previous; 
       temp.previous = null; 
      } 

      size--; 
      return value; 

     } else { 
      return null; 
     } 

    } 

    public boolean isEmpty() { 
     return head == null; 
    } 

    public int getSize() { 
     return size; 
    } 

    @Override 
    public String toString() { 

     StringBuilder sb = new StringBuilder(); 

     if (!isEmpty()) { 

      Node current = head; 

      while (current != null) { 

       if (size == 1) { 
        sb.append(current.value).append(" <- head/tail\n"); 
       } else if (current == head) { 
        sb.append(current.value).append(" <- head\n"); 
       } else if (current == tail) { 
        sb.append(current.value).append(" <- tail\n"); 
       } else { 
        sb.append(current.value).append("\n"); 
       } 

       current = current.previous; 

      } 

     } else { 
      sb.append("empty queue!\n"); 
     } 

     return sb.toString(); 

    } 

} 

测试（测试实施）

public class Test { 

    public static void main(String[] args) { 

     QueueForCars queue = new QueueForCars(); 

     queue.enqueue(new Car("John")); 
     System.out.println(queue); 
     queue.enqueue(new Car("Mary")); 
     System.out.println(queue); 
     queue.enqueue(new Car("Richard")); 
     System.out.println(queue); 
     queue.enqueue(new Car("David")); 
     System.out.println(queue); 

     System.out.println(); 

     System.out.println("Dequeued: " + queue.dequeue()); 
     System.out.println(queue); 
     System.out.println("Dequeued: " + queue.dequeue()); 
     System.out.println(queue); 
     System.out.println("Dequeued: " + queue.dequeue()); 
     System.out.println(queue); 
     System.out.println("Dequeued: " + queue.dequeue()); 
     System.out.println(queue); 
     System.out.println("Dequeued: " + queue.dequeue()); // <- empty queue! 
     System.out.println(queue); 

    } 

} 

如果你想有一个通用实现队列，即，可以处理任何类型的数据队列，您的实现应该是这样的：

队列（通用实现队列）

public class Queue<Type> { 

    private class Node<Type> { 
     Type value; 
     Node<Type> previous; 
    } 

    private Node<Type> head; 
    private Node<Type> tail; 
    private int size; 

    public Queue() { 
     tail = null; 
     head = null; 
     size = 0; 
    } 

    public void enqueue(Type value) { 

     Node<Type> newNode = new Node<>(); 
     newNode.value = value; 
     newNode.previous = null; 

     if (isEmpty()) { 
      head = newNode; 
      tail = newNode; 
     } else { 
      tail.previous = newNode; 
      tail = newNode; 
     } 

     size++; 

    } 

    public Type dequeue() { 

     if (!isEmpty()) { 

      Type value = head.value; 

      if (head == tail) { 
       head = null; 
       tail = null; 
      } else { 
       Node<Type> temp = head; 
       head = head.previous; 
       temp.previous = null; 
      } 

      size--; 
      return value; 

     } else { 
      return null; 
     } 

    } 

    public boolean isEmpty() { 
     return head == null; 
    } 

    public int getSize() { 
     return size; 
    } 

    @Override 
    public String toString() { 

     StringBuilder sb = new StringBuilder(); 

     if (!isEmpty()) { 

      Node<Type> current = head; 

      while (current != null) { 

       if (size == 1) { 
        sb.append(current.value).append(" <- head/tail\n"); 
       } else if (current == head) { 
        sb.append(current.value).append(" <- head\n"); 
       } else if (current == tail) { 
        sb.append(current.value).append(" <- tail\n"); 
       } else { 
        sb.append(current.value).append("\n"); 
       } 

       current = current.previous; 

      } 

     } else { 
      sb.append("empty queue!\n"); 
     } 

     return sb.toString(); 

    } 

} 

水果（另一类测试通用队列）

public class Fruit { 

    private String name; 
    private String color; 

    public Fruit(String name, String color) { 
     this.name = name; 
     this.color = color; 
    } 

    @Override 
    public String toString() { 
     return "Fruit (" + name + " is " + color + ")"; 
    } 

} 

测试（试验车水果通用队列）

public class Test { 

    public static void main(String[] args) { 

     Queue<Car> queueForCars = new Queue<>(); 

     queueForCars.enqueue(new Car("John")); 
     System.out.println(queueForCars); 
     queueForCars.enqueue(new Car("Mary")); 
     System.out.println(queueForCars); 
     queueForCars.enqueue(new Car("Richard")); 
     System.out.println(queueForCars); 
     queueForCars.enqueue(new Car("David")); 
     System.out.println(queueForCars); 

     System.out.println(); 

     Queue<Fruit> queueForFruits = new Queue<>(); 

     queueForFruits.enqueue(new Fruit("Apple", "red")); 
     System.out.println(queueForFruits); 
     queueForFruits.enqueue(new Fruit("Banana", "yellow")); 
     System.out.println(queueForFruits); 
     queueForFruits.enqueue(new Fruit("Lime", "green")); 
     System.out.println(queueForFruits); 

     System.out.println(); 


    } 

} 

我的一些代码是多余的，例如，对于队列的构造，因为它们设置的默认值的队列成员，但我认为这种方式更好地了解你何时学习。我希望它能帮助你！