Triển khai tốt nhất hàng đợi Java?

Question

Tôi đang làm việc (trong Java) trên một thuật toán xử lý hình ảnh đệ quy đệ quy đi qua các điểm ảnh của hình ảnh, ra ngoài từ một điểm trung tâm.

Thật không may, điều đó gây ra tràn ngăn xếp. Vì vậy, tôi đã quyết định chuyển sang thuật toán dựa trên Hàng đợi.

Bây giờ, điều này là tốt và dandy- nhưng xem xét thực tế là hàng đợi sẽ phân tích TROUSANDS pixel trong một khoảng thời gian rất ngắn, trong khi liên tục bật và đẩy, KHÔNG duy trì trạng thái dự đoán được (Có thể ở bất kỳ đâu giữa độ dài 100 và 20000); Việc thực hiện hàng đợi cần phải có khả năng đẩy và đẩy nhanh đáng kể.

Danh sách liên kết có vẻ hấp dẫn do khả năng tự đẩy các phần tử mà không cần sắp xếp lại bất kỳ thứ gì khác trong danh sách, nhưng để đủ nhanh, cần truy cập dễ dàng cả đầu và đuôi của nó (hoặc nút thứ hai đến cuối nếu nó không được liên kết kép). Đáng buồn thay, mặc dù tôi không thể tìm thấy bất kỳ thông tin nào liên quan đến việc triển khai danh sách liên kết bên dưới trong Java, do đó thật khó để nói rằng danh sách được liên kết có thực sự là cách hay không ...

Điều này mang lại cho tôi câu hỏi của mình. Điều gì sẽ là việc thực hiện tốt nhất giao diện Queue trong Java cho những gì tôi định làm? (Tôi không muốn chỉnh sửa hoặc thậm chí truy cập bất cứ thứ gì khác ngoài đầu và đuôi của hàng đợi - tôi không muốn làm bất kỳ loại sắp xếp lại nào, hoặc bất kỳ thứ gì. Về phía tôi, tôi có ý định làm nhiều việc và popping, và hàng đợi sẽ thay đổi kích thước khá một chút, vì vậy preallocating sẽ không hiệu quả)

Answer 1

LinkedList dường như là một cách để đi, LinkedList là danh sách được liên kết gấp đôi, tốt cho cấu trúc dữ liệu Queue (FIFO) . Nó duy trì một tài liệu tham khảo Head/Tail, mà bạn có thể nhận được bởi getFirst() và getLast().

Answer 2

Nếu bạn biết giới hạn trên của số lượng mặt hàng có thể có trong hàng đợi, bộ đệm tròn nhanh hơn LinkedList, vì LinkedList tạo đối tượng (liên kết) cho mỗi mục trong hàng đợi.

Answer 3

Kiểm tra giao diện Deque, cung cấp cho chèn/xóa ở cả hai đầu. LinkedList thực hiện giao diện đó (như đã đề cập ở trên), nhưng để bạn sử dụng, một ArrayDeque có thể tốt hơn - bạn sẽ không phải chịu chi phí phân bổ đối tượng không đổi cho mỗi nút. Sau đó, một lần nữa, nó có thể không quan trọng mà thực hiện bạn sử dụng.

Tính chất đa nguyên bình thường đến chơi: vẻ đẹp của văn bản chống lại giao diện Deque, thay vì bất kỳ triển khai cụ thể nào của nó, là bạn có thể dễ dàng chuyển đổi triển khai để kiểm tra cái nào hoạt động tốt nhất. Chỉ cần thay đổi dòng với new trong đó và phần còn lại của mã vẫn giữ nguyên.

Answer 4

Tôi nghĩ bạn có thể một số với đơn giản như thực hiện

package DataStructures; 

public class Queue<T> { 

    private Node<T> root; 

    public Queue(T value) { 
     root = new Node<T>(value); 
    } 

    public void enque(T value) { 
     Node<T> node = new Node<T>(value); 
     node.setNext(root); 
     root = node; 
    } 

    public Node<T> deque() { 

     Node<T> node = root; 
     Node<T> previous = null; 

     while(node.next() != null) { 
     previous = node; 
     node = node.next(); 
     } 
     node = previous.next(); 
     previous.setNext(null); 
     return node; 
    } 

    static class Node<T> { 

     private T value; 
     private Node<T> next; 

     public Node (T value) { 
     this.value = value; 
     } 

     public void setValue(T value) { 
     this.value = value; 
     } 

     public T getValue() { 
     return value; 
     } 

     public void setNext(Node<T> next) { 
     this.next = next; 
     } 

     public Node<T> next() { 
     return next; 
     } 
    } 
} 

Answer 5

Tuy nhiên, nếu bạn vẫn muốn sử dụng các thuật toán đệ quy, bạn có thể thay đổi nó được "tail-recursive" mà có lẽ được tối ưu hóa trong JVM để tránh chồng tràn.

Answer 6

Nếu bạn sử dụng LinkedList cẩn thận. Nếu bạn sử dụng nó như thế này:

LinkedList<String> queue = new LinkedList<String>(); 

sau đó bạn có thể vi phạm định nghĩa hàng đợi, bởi vì nó có thể loại bỏ các yếu tố khác ngoài đầu tiên (có những phương pháp như vậy trong LinkedList).

Nhưng nếu bạn sử dụng nó như thế này:

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

nó phải được ok, vì đây là heads-up cho những người dùng chèn nên chỉ xảy ra ở mặt sau và xóa bỏ chỉ ở phía trước.

Bạn có thể khắc phục lỗi triển khai thực hiện giao diện Hàng đợi bằng cách mở rộng lớp LinkedList thành lớp PureQueue ném UnsupportedOperationException của bất kỳ phương pháp vi phạm nào. Hoặc bạn có thể tiếp cận với aggreagation bằng cách tạo PureQueue chỉ với một trường là đối tượng LinkedList, danh sách và phương thức duy nhất sẽ là một hàm tạo mặc định, một hàm tạo bản sao, isEmpty(), size(), add(E element), remove() và element(). Tất cả các phương pháp đó phải là một lớp lót, ví dụ:

/** 
* Retrieves and removes the head of this queue. 
* The worstTime(n) is constant and averageTime(n) is constant. 
* 
* @return the head of this queue. 
* @throws NoSuchElementException if this queue is empty. 
*/ 
public E remove() 
{ 
    return list.removeFirst(); 
} // method remove() 

Answer 7

Tốt hơn nên sử dụng ArrayDeque thay vì LinkedList khi triển khai Stack và Queue trong Java. ArrayDeque có khả năng nhanh hơn Stack interface (trong khi Stack là thread-safe) khi được sử dụng như một stack, và nhanh hơn LinkedList khi được sử dụng như một hàng đợi. Hãy xem liên kết này Use ArrayDeque instead of LinkedList or Stack.