6 Pilas y colas¶

Introducción¶

Una cola es un tipo de dato que sigue el principio FIFO (first in, first out) que implica que el primer elemento en ser insertado en la cola es también el primero en ser eliminado de la misma.

En el mundo real podemos encontrar este ejemplo en las colas de un banco, la cadena de impresión de documentos, etc. En el caso de la cola en el banco, la primera persona en llegar es también la primera en irse (suponiendo una única ventanilla) y en los documentos a imprimir, la impresora imprime según el orden de llegada.

Queue<E> es una interfaz que hereda de Collection que proporciona operaciones para trabajar con una cola. Veamos alguna de ellas:

boolean add(E e): inserta el elemento al final de la cola.
E element(): Devuelve, pero no elimina, el principio de la cola. Lanza la excepción NoSuchElementException si la cola está vacía.
E peek():Devuelve, pero no elimina, el principio de la cola. Devuelve null si la cola está vacía.
E poll(): Devuelve y elimina el principio de la cola. Devuelve null si la cola está vacía.
E remove(): Devuelve y elimina el principio de la cola. Lanza la excepción NoSuchElementException si la cola está vacía.

Deque<E> representa una cola de doble extremo, lo que significa que se puede insertar y eliminar elementos desde ambos extremos de la cola. El nombre Deque es una abreviatura de Double Ended Queue. Admite, por lo tanto, la implementación de la cola FIFO como la implementación de la pila LIFO, que implica que el último elemento que se ha insertado, es el primero en ser eliminado: LIFO (last in, first out).

Deque hereda de Queue, por lo que tiene todos sus métodos y además añade los suyos propios.Veamos algunos de ellos:

void addFirst(E e): inserta el elemento al principio.
void addLast(E e): inserta el elemento al final.
E getFirst(): Devuelve, pero no elimina, el primer elemento. Lanza la excepción NoSuchElementException si el Deque está vacío.
E getLast(): Devuelve, pero no elimina, el último elemento. Lanza la excepción NoSuchElementException si el Deque está vacío.
E peekFirst(): Devuelve, pero no elimina, el primer elemento. Devuelve null si el Deque está vacío.
E peekLast(): Devuelve, pero no elimina, el último elemento. Devuelve null si el Deque está vacío.
E pollFirst(): Devuelve y elimina el primer elemento. Devuelve null si el Deque está vacío.
E pollLast(): Devuelve y elimina el último elemento. Devuelve null si el Deque está vacío.
E removeFirst(): Devuelve y elimina el primer elemento. Lanza la excepción NoSuchElementException si el Deque está vacío.
E removeLast(): Devuelve y elimina el último elemento. Lanza la excepción NoSuchElementException si el Deque está vacío.

Clase ArrayDeque¶

La clase ArrayDeque<E> implementa la interfaz Deque y por lo tanto, también Queue, ya que Deque hereda de Queue.

ColaConsola ColaPilaConsola Pila

import java.util.ArrayDeque;
import java.util.Queue;

public class ShowQueue{
    public void show(){
        Queue<Vehicle> queue = new ArrayDeque();

        queue.add(new Vehicle("9685KMX", 4, "azul"));
        queue.add(new Vehicle("1235GTR", 2, "rojo"));
        queue.add(new Vehicle("7314QWE", 4, "verde"));

        System.out.println(queue.element()); //(1)!
        System.out.println(queue.peek());//(2)!
        System.out.println(queue.poll());//(3)!
        System.out.println(queue.remove());//(4)!
        System.out.println(queue.remove());//(5)!
        System.out.println(queue.peek());//(6)!
        System.out.println(queue.poll());//(7)!
        System.out.println(queue.element());//(8)!
        System.out.println(queue.remove());//(9)!
    }

    public static void main(String[] args){
        new ShowQueue().show();
    }
}

1. Devuelve pero no elimina 9685KMX 1. Devuelve pero no elimina: 9685KMX 1. Devuelve y elimina: 9685KMX 1. Devuelve y elimina: 1235GTR 1. Devuelve y elimina el último, se queda la cola vacía: 7314QWE 1. Devuelve null 1. Devuelve null 1. Lanza NoSuchElementException porque la cola está vacía 1. Lanza NoSuchElementException porque la cola está vacía

Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
Vehicle [registration=1235GTR, wheelCount=2, speed=0.0, colour=rojo]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]
null
null
Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.ArrayDeque.getFirst(ArrayDeque.java:402)
    at java.base/java.util.ArrayDeque.element(ArrayDeque.java:551)
    at tema11_Colecciones.pilasYColas.ShowQueue.show(ShowQueue.java:21)
    at tema11_Colecciones.pilasYColas.ShowQueue.main(ShowQueue.java:28)

import java.util.ArrayDeque;
import java.util.Deque;

public class ShowDeque{
    public void show(){
        Queue<Vehicle> deque = new ArrayDeque();

        deque.add(new Vehicle("9685KMX", 4, "azul"));
        deque.add(new Vehicle("1235GTR", 2, "rojo"));
        deque.add(new Vehicle("7314QWE", 4, "verde"));

        System.out.println(deque.element()); //(1)!
        System.out.println(deque.peek());//(2)!
        System.out.println(deque.poll());//(3)!
        System.out.println(deque.remove());//(4)!
        System.out.println(deque.remove());//(5)!
        System.out.println(deque.peek());//(6)!
        System.out.println(deque.poll());//(7)!
        System.out.println(deque.element());//(8)!
        System.out.println(deque.remove());//(9)!
    }

    public static void main(String[] args){
        new ShowDeque().show();
    }
}

Devuelve pero no elimina 7314QWE
Devuelve pero no elimina: 7314QWE
Devuelve y elimina: 7314QWE
Devuelve y elimina: 1235GTR
Devuelve y elimina el último, se queda la pila vacía: 9685KMX
Devuelve null
Devuelve null
Lanza NoSuchElementException porque la pila está vacía
Lanza NoSuchElementException porque la pila está vacía

Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]
Vehicle [registration=7314QWE, wheelCount=4, speed=0.0, colour=verde]
Vehicle [registration=1235GTR, wheelCount=2, speed=0.0, colour=rojo]
Vehicle [registration=9685KMX, wheelCount=4, speed=0.0, colour=azul]
null
null
Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.ArrayDeque.getLast(ArrayDeque.java:413)
    at tema11_Colecciones.pilasYColas.ShowDeque.show(ShowDeque.java:21)
    at tema11_Colecciones.pilasYColas.ShowDeque.main(ShowDeque.java:28)

Clase Collections¶

La clase Collections contiene numerosos métodos estáticos para utilizar con todo tipo de colecciones, como por ejemplo, para añadir, buscar, copiar, reemplazar, ordenar, obtener el máximo o el mínimo, etc.