Java Collections (LIFO Structure)

Je suis à la recherche dans les Collections cadre de Java pour une Structure LIFO (Pile), sans succès. Fondamentalement, je veux vraiment une simple pile; mon option idéale serait un Deque, mais je suis en Java 1.5.

Je voudrais ne pas avoir à ajouter une autre classe de ma structure, mais je me demande si c'est possible:

  1. Est-il de toute la classe dans les Collections cadre (1.5) qui fait le travail?

  2. Si non, est-il possible de transformer une File d'attente dans un dernier entré, premier sorti de la File d'attente (aka Pile) sans remise à plat?

  3. Sinon, l'Interface ou classe, ou devrais-je prolonger pour cette tâche? Je pense que garder le chemin que les gars de Soleil ont fait avec le Deque est un bon début.

Merci beaucoup.

EDIT: j'ai oublié de dire à propos de la classe de Pile: j'ai des doutes sur cette classe quand j'ai vu qu'il met en œuvre le Vecteur de la classe, et la classe Vector est un peu obsolète, n'est-ce pas?

  • Le problème principal Vecteur est que tous les accès sont synchronisés, si vous en avez besoin ou pas. C'est comme "up-to-date" comme toutes les autres collections, mais a obtenu une mauvaise réputation à cause du problème de synchronisation.
InformationsquelleAutor David Santamaria | 2008-11-19
  1. 53

    Il y a en fait une classe de Pile: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Stack.html

    Si vous ne voulez pas l'utiliser, la classe LinkedList (http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html) a addFirst et addLast et removeFirst et removeLast méthodes, le rendant parfait pour une utilisation comme une pile ou une file d'attente de la classe.

    • LinkedList aussi donne ensuite la définition d'un Deque, qui est de votre choix de la collection.
    • Oui, je pense que LinkedList est celui que je cherchais, car dans mes premier coup d'oeil à elle, je n'ai pas réaliser sur le Addfirst et removeFirst méthodes. Merci beaucoup.
    • seul problème, c'est que Deque a été mis en œuvre sur l'API de Niveau 9....
    • et LinkedList soutient également les éléments null contrairement à ArrayDeque.
    InformationsquelleAutor Eli Courtwright
  2. 8

    Pile classe est lentement: méthodes sont synchronisés + Stack s'étend synchronisé Vecteur

    InformationsquelleAutor
  3. 8

    Je me rends compte que je suis en retard à la fête ici, mais java.util.Collections (Java 7) a une statique 'asLifoQueue" qui prend une Deque argument et renvoie (évidemment) un dernier entré, premier sorti de la file d'attente de vue de la deque. Je ne suis pas sûr de ce que cette version a été ajouté.

    http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#asLifoQueue(java.util.Deque)

    InformationsquelleAutor JVMATL
  4. 7

    Il y a un Classe de pile dans l'API. Sera-ce répondre à vos besoins?

    • Désolé j'ai oublié de Dire à propos de la Pile de la Classe et de mon opinion sur le sujet, mais je pense que c'est probablement une meilleure solution que de mettre en œuvre ma propre classe. n'est-il pas?
    • Ne pas utiliser la Pile de la classe. Elle s'étend de Vecteur, qui est conservé pour la compatibilité ascendante seulement.
    InformationsquelleAutor Greg
  5. 6

    Alors que cela avait été demandé il y a un moment, il pourrait être sage de fournir un JDK6+ réponse qui fournit désormais un Deque (pont) de l'interface qui est mis en œuvre par le ArrayDeque structure de données et la LinkedList a été mis à jour pour implémenter cette interface. Spécialisé formes pour l'accès simultané existent également et sont mis en œuvre par ConcurrentLinkedDeque et LinkedBlockingDeque.

    La seule chose qui est formidable à propos d'un deque est qu'il fournit la méthode LIFO (pile) et FIFO (file d'attente), il peut causer de la confusion pour les méthodes qui sont pour les opérations de mise en attente et qui sont pour la pile des opérations pour les nouveaux arrivants.

    À mon humble avis le JDK doit avoir un Stack interface et un Queue interface qui pourraient encore être mises en œuvre par les goûts de ArrayDeque mais seulement d'exposer le sous-ensemble des méthodes nécessaires pour que la structure, c'est à dire un PRINCIPE pourrait définir pop(), push() et peek(), puis dans le contexte de

    LIFO<String> stack = new ArrayDeque<>();

    seulement empiler les opérations sont exposés, ce qui arrête quelqu'un accidentellement appel ajouter(E) quand push(E) était destiné.

    InformationsquelleAutor Brett Ryan
  6. 0

    Juste par souci d'exhaustivité, je suis en fournissant une file d'attente et un pur LinkedList exemple.

    À l'aide de la Résorption de l'interface en combinaison avec une LinkedList (recommandé):

        Deque<String> dequeue = new LinkedList<>();
    dequeue.add("first");
    dequeue.add("last");

    //returns "last" without removing it
    System.out.println(dequeue.peekLast());

    //removes and returns "last"
    System.out.println(dequeue.pollLast());

    Sauvegarde d'une file d'attente par une LinkedList est idéal pour la performance, puisque l'insertion et la suppression d'éléments de il est fait en temps constant (O(1)).

    À l'aide d'une LinkedList seul:

        LinkedList<String> list = new LinkedList<>();
    list.add("first");
    list.add("last");

    //returns "last" without removing it
    System.out.println(list.getLast());

    //removes and returns "last"
    System.out.println(list.removeLast());
    • Le post original a l'aide d'une File d'attente qui était évidemment FIFO et non de ce PRINCIPE, j'ai donc mis à jour ma réponse.
    InformationsquelleAutor Ivo
  7. -2

    [EN CAS DE RÉPONSE INCORRECTE EN TERME DE PERFORMANCE]
    Je suis le seul à en garder pour les gens à apprendre que ce n'est pas une bonne solution.

    Réponse la plus simple serait d'utiliser un ArrayList, et juste ajouter des objets à l'indice 0. 

    List<String> arrayList = new ArrayList<>();
arrayList.add(0, "three");
arrayList.add(0, "two");
arrayList.add(0, "one");

//Prints: [one, two, three]
System.out.println(arrayList);

    ajout d'objets à 0 indice de l'ajouter en haut de la liste, et décale le reste de la liste. Maintenant vous avez un simple fonctionnement LIFO structure de données.

    EDIT: à l'Aide d'une LinkedList est plus rapide que d'utiliser une ArrayList. Donc, en utilisant LinkedList.addFirst() est mieux.

    • Ce n'est pas une bonne idée en terme de performance, en raison de l'évolution. Une LinkedList serait beaucoup mieux ici.
    InformationsquelleAutor Ahmed Rezk