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(); 


    } 

} 

我的一些代碼是多餘的，例如，對於隊列的構造，因爲它們設置的默認值的隊列成員，但我認爲這種方式更好地瞭解你何時學習。我希望它能幫助你！