listas - pilas y colas en java ejemplos

Colecciones Java(Estructura LIFO)

Question

Estoy buscando en el marco de colecciones de Java para una estructura LIFO (pila) sin ningún éxito. Básicamente quiero una pila realmente simple; mi opción perfecta sería un Deque, pero estoy en Java 1.5.

Me gustaría no tener que agregar otra clase a mi estructura, pero me pregunto si eso es posible:

1. ¿Hay alguna clase en el marco de Colecciones (1.5) que haga el trabajo?

2. Si no, ¿hay alguna forma de convertir una cola en una cola LIFO (también conocida como pila) sin reimplementar?

3. Si no, ¿qué Interfaz o clase debería extender para esta tarea? Supongo que mantener el camino que los tipos de Sun han hecho con el Deque es un buen comienzo.

Muchas gracias.

EDIT: Olvidé decir sobre la clase Stack: tengo mis dudas sobre esta clase cuando vi que implementa la clase Vector, y la clase Vector es un poco obsoleta, ¿no?

Answer 1

En realidad, hay una clase Stack: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Stack.html

Si no desea utilizar eso, la clase LinkedList ( http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html ) tiene addFirst y addLast y removeFirst y removeFirst métodos, por lo que es perfecto para usar como una clase de pila o cola.

Answer 2

Hay una clase Stack en la API . ¿Esto satisfará tus necesidades?

Answer 3

La clase de pila es lenta: los métodos están sincronizados + Stac k se extiende Vector sincronizado

Answer 4

Me doy cuenta de que llego tarde a la fiesta aquí, pero java.util.Collections (Java 7) tiene un ''asLifoQueue'' estático que toma un argumento Deque y devuelve (obviamente) una vista de cola LIFO del deque. No estoy seguro de qué versión se agregó.

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

Answer 5

Si bien esto fue preguntado hace un tiempo, podría ser conveniente proporcionar una respuesta JDK6 + que ahora proporcione una interfaz Deque (plataforma) que se implementa mediante la estructura de datos ArrayDeque y LinkedList se actualizó para implementar esta interfaz. También existen formularios especializados para acceso concurrente implementados por ConcurrentLinkedDeque y LinkedBlockingDeque .

Una de las ventajas de un deque es que proporciona soporte LIFO (pila) y FIFO (cola), ya que puede causar confusión en cuanto a qué métodos son para operaciones de cola y cuáles son para operaciones de pila para los recién llegados.

En mi humilde opinión, el JDK debería tener una interfaz Stack y una interfaz Queue que aún podría ser implementada por los gustos de ArrayDeque pero solo exponer el subconjunto de métodos requeridos para esa estructura, es decir, un LIFO podría definir pop() , push() y peek() , entonces en el contexto de

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

solo se exponen las operaciones de pila que detienen a alguien que accidentalmente llama a add (E) cuando se pretendía empujar (E) .

Answer 6

Solo para completar, estoy proporcionando un ejemplo de Dequeue y un LinkedList puro.

Uso de la interfaz Dequeue en combinación con LinkedList (recomendado):

    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());

Hacer una copia de seguridad de una Dequeue mediante LinkedList es excelente para el rendimiento, ya que la inserción y eliminación de elementos se realiza en tiempo constante (O (1)).

Usando LinkedList solo:

    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());

Answer 7

La respuesta más simple sería usar una ArrayList , y simplemente agregar objetos en el índice 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);

agregar objetos en el índice 0 se agregará a la parte superior de la lista y cambiará el resto de la lista. Ahora tiene una estructura de datos LIFO simple y funcional.

EDITAR: Usar LinkedList es más rápido que usar ArrayList. Entonces, usar LinkedList.addFirst () es mejor.