Meilleure implémentation de Java Queue?

Si vous utilisez LinkedList soyez prudent. Si vous l'utilisez comme ceci:

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

Ensuite, vous pouvez violer la définition de la file d'attente, car il est possible de supprimer d'autres éléments que first (Il existe de telles méthodes dans LinkedList).

, Mais si vous l'utilisez comme ceci:

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

Cela devrait être correct, car cela indique aux utilisateurs que les insertions ne devraient se produire qu'à l'arrière et les suppressions uniquement à l'avant.

Vous pouvez surmonter l'implémentation défectueuse de L'interface de file d'attente en Classe LinkedList à une classe PureQueue qui lance UnsupportedOperationException de l'une des méthodes incriminées. Ou vous pouvez adopter une approche avec aggreagation en créant PureQueue avec un seul champ qui est de type LinkedList object, list, et les seules méthodes seront un constructeur par défaut, un constructeur de copie, isEmpty(), size(), add(E element), remove(), et element(). Toutes ces méthodes devraient être des one-liners, comme par exemple:

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

Consultez l'interface Deque, qui prévoit des insertions/suppressions aux deux extrémités. LinkedList implémente cette interface (comme mentionné ci-dessus), mais pour votre utilisation, un ArrayDeque peut être meilleur-vous n'encourrez pas le coût des allocations d'objets constants pour chaque nœud. Là encore, peu importe l'implémentation que vous utilisez.

La bonté du polymoprhisme normal vient jouer: la beauté de l'écriture contre L'interface Deque, plutôt que toute implémentation spécifique de celle-ci, est que vous pouvez très facilement changer d'implémentations pour tester celle qui fonctionne le mieux. Il suffit de changer la ligne avec new, et le reste du code reste le même.

Si vous connaissez la limite supérieure de la quantité possible d'éléments dans la file d'attente, le tampon circulaire est plus rapide que LinkedList, car LinkedList crée un objet (lien) pour chaque élément de la file d'attente.

Il est préférable D'utiliser ArrayDeque au lieu de LinkedList lors de l'implémentation de la pile et de la file D'attente en Java. ArrayDeque est susceptible d'être plus rapide que L'interface Stack (alors que Stack est thread-safe) lorsqu'il est utilisé comme une pile, et plus rapide que LinkedList lorsqu'il est utilisé comme une file d'attente. Jetez un oeil à ce lien Utilisez ArrayDeque au lieu de LinkedList ou Stack.

Je pense que vous pouvez certains avec simple comme l'implémentation

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;
      }
   }
}

Cependant, si vous voulez continuer à utiliser l'algorithme récursif, vous pouvez le changer "queue-récursive", ce qui est probablement optimisé dans la JVM pour éviter les débordements de pile.