Beste Implementierung der Java-Warteschlange?

Question

Ich arbeite (in Java) an einem rekursiven Bildverarbeitungsalgorithmus, der rekursiv die Pixel des Bildes nach außen von einem Mittelpunkt aus durchquert.

Leider verursacht das einen Stack Overflow. Also habe ich mich entschieden, zu einem Queue-basierten Algorithmus zu wechseln.

Nun, das ist alles in Ordnung und Dandy- aber in Anbetracht der Tatsache, dass es Warteschlange wird Tausende von Pixeln in sehr kurzer Zeit zu analysieren, während ständig knallen und drücken, OHNE einen vorhersehbaren Zustand (Es könnte überall sein zwischen 100 und 20000); Die Warteschlangenimplementierung muss über sehr schnelle Popping- und Push-Fähigkeiten verfügen. Eine verknüpfte Liste scheint attraktiv zu sein aufgrund ihrer Fähigkeit, Elemente zu sich zu schieben, ohne etwas anderes in der Liste neu anzuordnen, aber um schnell genug zu sein, würde sie leichten Zugang zu ihrem Kopf UND ihrem Schwanz benötigen (oder vorletzter Knoten, wenn es nicht doppelt verknüpft wäre. Leider kann ich keine Informationen über die zugrunde liegende Implementierung von verketteten Listen in Java finden, daher ist es schwer zu sagen, ob eine verkettete Liste wirklich der richtige Weg ist ...

Das bringt mich zu meiner Frage. Was wäre die beste Implementierung der Warteschlangenschnittstelle in Java für das, was ich vorhabe? (Ich möchte nichts anderes bearbeiten und auch nicht zugreifen, als den Kopf und das Ende der Warteschlange - ich möchte keine Neuanordnung oder irgendetwas anderes machen. Auf der anderen Seite möchte ich viel pushen und knallen, und die Warteschlange wird die Größe ziemlich ändern, so wäre die Vorbelegung ineffizient)

Answer 1

LinkedList scheint zu einem Weg zu gehen, LinkedList ist eine doppelt verknüpfte Liste, die für eine Queue Datenstruktur (FIFO) ist . Es verwaltet eine Head/Tail-Referenzen, die Sie von getFirst() und getLast() erhalten können.

Answer 2

Wenn Sie die Obergrenze der möglichen Anzahl von Elementen in der Warteschlange kennen, ist der Umlaufpuffer schneller als LinkedList, da LinkedList ein Objekt (Link) für jedes Element in der Warteschlange erstellt.

Answer 3

Schauen Sie sich die Schnittstelle Deque an, die an beiden Enden Einfügungen/Entfernungen ermöglicht. LinkedList implementiert diese Schnittstelle (wie oben erwähnt), aber zu Ihrer Verwendung könnte ein ArrayDeque besser sein - Sie werden nicht die Kosten für die Zuweisung von konstanten Objekten für jeden Knoten tragen müssen. Andererseits spielt es keine Rolle, welche Implementierung Sie verwenden.

Normale Polymorphismus-Güte kommt zum Tragen: Die Schönheit des Schreibens gegen die Deque-Schnittstelle, anstatt irgendeine spezifische Implementierung davon, ist, dass Sie Implementierungen sehr leicht umschalten können, um zu testen, welcher am besten funktioniert. Ändern Sie einfach die Zeile mit new darin, und der Rest des Codes bleibt gleich.

Answer 4

Ich glaube, Sie mit einfach einige können wie Implementierung

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

Wenn Sie jedoch nach wie vor den rekursiven Algorithmus verwenden mögen, können Sie es "tail-recursive" sein ändern, die wahrscheinlich in der JVM optimierte Stapel zu vermeiden Überläufe.

Answer 6

Wenn Sie LinkedList verwenden, seien Sie vorsichtig. Wenn Sie es wie folgt verwenden:

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

dann können Sie Queue-Definition verletzen, weil es möglich ist, andere Elemente zu entfernen, als erstes (es gibt solche Methoden in LinkedList).

Aber wenn Sie es wie folgt verwenden:

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

es in Ordnung sein sollte, da dies Heads-up für die Nutzer, die Einfügungen nur an der Front nur auf der Rückseite und Löschungen auftreten sollte.

Sie können die fehlerhafte Implementierung der Queue-Schnittstelle überwinden, indem Sie die LinkedList-Klasse auf eine PureQueue-Klasse erweitern, die UnsupportedOperationException von einer der problematischen Methoden auslöst. Oder Sie können Ansatz mit Aggression nehmen, indem Sie PureQueue mit nur einem Feld vom Typ LinkedList-Objekt, Liste erstellen, und die einzigen Methoden sind ein Standardkonstruktor, ein Kopierkonstruktor, , add(E element), remove() und element(). All diese Methoden sollten Einzeiler sein, wie zum Beispiel:

/** 
* 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

Es ist besser ArrayDeque statt LinkedList zu verwenden, wenn Stack und Queue in Java implementiert. ArrayDeque ist wahrscheinlich schneller als das Stack-Interface (während Stack Thread-sicher ist), wenn es als Stack verwendet wird, und schneller als LinkedList, wenn es als Warteschlange verwendet wird. Sehen Sie sich diesen Link Use ArrayDeque instead of LinkedList or Stack an.