¿Mejor implementación de Java Queue?

Question

Estoy trabajando (en Java) en un algoritmo de procesamiento de imágenes recursivas que atraviesa recursivamente los píxeles de la imagen, hacia afuera desde un punto central.

Desafortunadamente, eso causa un desbordamiento de la pila. Así que he decidido cambiar a un algoritmo basado en cola.

Ahora, todo está bien, pero teniendo en cuenta que se trata de cola, se analizarán MILES de píxeles en un período de tiempo muy corto, mientras se estacionan y empujan constantemente, SIN mantener un estado predecible (Podría estar en cualquier parte entre la longitud 100 y 20000); La implementación de la cola necesita tener habilidades de estallido y empuje significativamente rápidas.

Una lista vinculada parece atractiva debido a su capacidad de empujar elementos hacia sí misma sin reorganizar nada más en la lista, pero para que sea lo suficientemente rápida, necesitaría un fácil acceso tanto a su cabeza, como a su cola (o penúltimo nodo si no estuviera doblemente vinculado). Tristemente, aunque no puedo encontrar ninguna información relacionada con la implementación subyacente de listas enlazadas en Java, entonces es difícil decir si una lista vinculada es realmente el camino a seguir ...

Esto me lleva a mi pregunta. ¿Cuál sería la mejor implementación de la interfaz Queue en Java para lo que pretendo hacer? (No deseo editar ni siquiera acceder a nada que no sea la cabeza y la cola de la cola, no deseo hacer ningún tipo de reorganización ni nada. Por otro lado, ESTOY intentando hacer un montón de empujones y apareciendo, y la cola cambiará de tamaño un poco, por lo que la asignación previa sería ineficiente)

Answer 1

LinkedList parece ser un camino por recorrer, LinkedList es una lista doblemente enlazada, que es buena para una estructura de datos en cola (FIFO) . Mantiene las referencias de Cabeza/Cola, que puede obtener por getFirst() y getLast().

Answer 2

Si conoce el límite superior de la posible cantidad de elementos en la cola, el búfer circular es más rápido que LinkedList, ya que LinkedList crea un objeto (enlace) para cada elemento en la cola.

Answer 3

Compruebe la interfaz Deque, que proporciona inserciones/eliminaciones en ambos extremos. LinkedList implementa esa interfaz (como se mencionó anteriormente), pero para su uso, un ArrayDeque puede ser mejor; no incurrirá en el costo de las asignaciones constantes de objetos para cada nodo. Por otra parte, puede no importar qué implementación usas.

La bondad del polimorfismo normal viene a jugar: la belleza de escribir contra la interfaz Deque, en lugar de cualquier implementación específica de la misma, es que puedes cambiar fácilmente las implementaciones para probar cuál funciona mejor. Simplemente cambie la línea con new y el resto del código permanece igual.

Answer 4

Creo que se puede algún día con tan simple como la aplicació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

Sin embargo, si aún desea utilizar el algoritmo recursivo, se puede cambiar que sea "tail-recursive" que probablemente se optimiza en la JVM para evitar pila desborda

Answer 6

Si usa LinkedList tenga cuidado. Si lo usa así:

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

entonces usted puede violar definición de cola, ya que es posible eliminar otros elementos que primero (hay tales métodos en LinkedList).

Pero si lo usa de esta manera:

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

debería estar bien, ya que este es el heads-up a los usuarios que las inserciones deben ocurrir solamente en la parte trasera y supresiones solamente en la parte delantera.

Puede superar la implementación defectuosa de la interfaz Queue extendiendo la clase LinkedList a una clase PureQueue que lanza UnsupportedOperationException de cualquiera de los métodos ofensivos. O puede realizar un acercamiento con agregación creando PureQueue con solo un campo que escriba tipo LinkedList object, list, y los únicos métodos serán un constructor predeterminado, un constructor de copia, isEmpty(), size(), add(E element), remove() y element(). Todos estos métodos deben ser de una sola línea, como por ejemplo:

/** 
* 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 mejor utilizar ArrayDeque en lugar de LinkedList en la aplicación de la pila y cola en Java. Es probable que ArrayDeque sea más rápido que la interfaz Stack (mientras que Stack es seguro para subprocesos) cuando se usa como una pila, y más rápido que LinkedList cuando se usa como una cola. Eche un vistazo a este enlace Use ArrayDeque instead of LinkedList or Stack.