linkedlist - La mejor implementación de Java Queue?

priority queue java

Question

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

Desafortunadamente, eso causa un desbordamiento de 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 (Puede estar entre 100 y 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 para 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 a la cola). -último nodo si no estaba 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 popping, y la cola cambiará de tamaño bastante, por lo que la asignación previa sería ineficaz)

Answer 1

Consulte 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 normal del polimoprismo viene a jugar: la belleza de la escritura 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 2

Creo que se puede mejorar con una implementación similar

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 3

Es mejor utilizar ArrayDeque en lugar de LinkedList al implementar Stack and Queue 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 en lugar de LinkedList o Stack .

Answer 4

Si conoce el límite superior de la cantidad posible 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 5

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

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

a continuación, puede violar la definición de cola, porque es posible eliminar otros elementos que primero (existen tales métodos en LinkedList).

Pero si lo usa así:

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

debería estar bien, ya que esto es cara a cara para los usuarios que las inserciones deberían ocurrir solo en la parte posterior y las eliminaciones solo en la parte frontal.

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 es tipo objeto LinkedList, list, y los únicos métodos serán un constructor predeterminado, un constructor de copia, isEmpty() , size() , add(E element) , remove() y element() . Todos esos métodos deberían 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 6

Sin embargo, si aún desea usar el algoritmo recursivo, puede cambiarlo para que sea "tail-recursive" que probablemente esté optimizado en la JVM para evitar desbordamientos de pila.

Answer 7

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