La Estructura de Datos Cola en Java

COMPARTIR EN REDES SOCIALES

En esta entrada vamos a explicar en profundidad la estructura de datos cola. Una cola es una estructura de datos que representa una cola en el mundo real, como por ejemplo, la cola para entrar a comer a un restaurante. Son de tipo FIFO, First IN First OUT, es decir, el primer elemento que entra es el primer elemento que sale.

Para poder explicar la cola realizaremos 3 implementaciones y también veremos las 2 implementaciones que tiene Java en su SDK.

Las implementaciones que realizaremos serán:

  • Cola circular con memoria estática
  • Cola con memoria dinámica
  • Cola con prioridad

Respecto al SDK de Java veremos tanto la cola normal como la cola con prioridad.

¿ Qué aspecto tiene una cola y cuales son sus principales operaciones ?

Una cola tiene el siguiente aspecto:

Representación de una Cola
Representación de una Cola

Sus principales operaciones son «encolar» y «desencolar», o en inglés «enqueue» y «dequeue». Siempre que encolamos un elemento lo hacemos por la parte de atrás de la cola, es decir, siempre lo encolamos después del último elemento. Por el contrario, cuando desencolamos lo hacemos empezando por el principio de la cola, de esta manera conseguimos que se comporte como una cola.

Como podéis observar realmente podemos representar una cola como un vector al cuál le dotamos de comportamiento para que se comporte con la especificación de la cola.

Nuestra primera implementación es una cola circular de memoria estática.

Cola Circular con Memoria Estática en Java

Antes de ver la implementación muchos os estaréis preguntando qué es una cola circular, su representación la podemos ver a continuación:

Cola Circular en Java
Cola Circular en Java

Si os fijáis una cola circular realmente es un vector representado de forma circular, donde tenemos una variable que apunta a donde empiezan los elementos y otra variable que apunta al final de los elementos. Esto nos permite encolar y desencolar los elementos sin preocuparnos de los huecos que puedan quedar vacíos y con la posibilidad de poder encolar siempre como máximo N elementos, siendo N el número máximo de elementos que podemos albergar.

¿ Cómo funcionan las variables que apuntan al inicio y al final de los elementos ?

Si partimos de una cola que se encuentra vacía ambas variables apuntarán a la posición 0, conforme vayamos insertando elementos iremos incrementando en 1 la variable que apunta al final de los elementos y conforme vayamos desencolando elementos iremos incrementando la variable de inicio en 1.

Como veis en el ejemplo «front» apunta a 0 y «rear a 4» esto quiere decir que se han encolado 5 elementos pero todavía no se ha desencolado ningún elemento, ya que si lo hubiera hecho «front» apuntaría a un valor diferente de 0.

La implementación de la Cola Circular

Veamos el código y luego expliquemos su funcionamiento:

import java.util.Optional;

public class ColaCircularMemoriaEstatica<V> {

	private final int CAPACIDAD = 20;
	private V [] items;
	private int inicio, fin;
	private int numElementos;
	
	@SuppressWarnings("unchecked")
	public ColaCircularMemoriaEstatica() {
		items = (V[])new Object[CAPACIDAD];
		inicio = 0;
		fin = 0;
		numElementos = 0;
	}
	
	public boolean push(V item) {
		boolean resultado = false;
		
		if (numElementos < CAPACIDAD) {
			this.items[fin] = item;
			this.numElementos++;
			fin = (fin + 1) % CAPACIDAD; 
		}else {
			resultado = false;
		}
		
		return resultado;
	}
	
	public Optional<V> pop() {
		Optional<V> item = Optional.empty();
		
		if (this.numElementos > 0) {
			item = Optional.of(this.items[inicio]);
			inicio = (inicio + 1) % CAPACIDAD;
			this.numElementos--;
		}
		
		return item;
	}
	
	public boolean hasNext() {
		boolean next = false;
		
		if (this.numElementos > 0) {
			next = true;
		}
		
		return next;
	}
	
	public int size() {
		return this.numElementos;
	}
	
}

Nuestra implementación es genérica y por lo tanto utiliza «Genéricos» en Java. Los atributos que utiliza son los siguientes:

private final int CAPACIDAD = 20;
private V [] items;
private int inicio, fin;
private int numElementos;
  1. Una constante que establecerá el número máximo de elementos que podrá albergar nuestra cola.
  2. Un array estático de tipo «V» que almacenará los elementos de la cola.
  3. Dos variables enteras que nos servirán para saber donde tenemos que encolar y desencolar los elementos de nuestra cola circular.
  4. Una variable entera que servirá para saber cuantos elementos tenemos en nuestra cola en un momento determinado.

El constructor de nuestra cola será el siguiente:

@SuppressWarnings("unchecked")
public ColaCircularMemoriaEstatica() {
    items = (V[])new Object[CAPACIDAD];
    inicio = 0;
    fin = 0;
    numElementos = 0;
}

En el constructor realizamos las siguientes acciones:

  1. Inicializamos nuestro array de memoria estática a la «CAPACIDAD» deseada, en nuestro caso 20.
  2. Apuntamos «inicio» y «fin» a 0, ya que nuestra cola no contiene todavía elementos.
  3. Establecemos el número de elementos a 0.

Veamos el método «encolar»:

public boolean push(V item) {
    boolean resultado = false;
    
    if (numElementos < CAPACIDAD) {
        this.items[fin] = item;
        this.numElementos++;
        fin = (fin + 1) % CAPACIDAD; 
    }else {
        resultado = false;
    }
    
    return resultado;
}

Nuestro método encolar funciona de la siguiente manera, si el número de elementos que contiene nuestra cola es menor que nuestra capacidad, insertamos el elemento en la posición a donde apunta nuestra variable fin, incrementamos el valor del número de elementos en 1 e incrementamos el valor de fin en 1 aplicándole el módulo para que cuando llegue a 20 vuelva a valer 0.

Si ya hemos alcanzado el número de elementos máximo devolvemos false para informar al usuario de que no hemos podido almacenar el elemento.

Nuestro método desencolar es el siguiente:

public Optional<V> pop() {
    Optional<V> item = Optional.empty();
    
    if (this.numElementos > 0) {
        item = Optional.of(this.items[inicio]);
        inicio = (inicio + 1) % CAPACIDAD;
        this.numElementos--;
    }
    
    return item;
}

Devolvemos un valor «Optional», ya que puede ser que no tengamos elementos en la cola, por lo tanto, inicializamos «item» a un «Optional» vacío y en caso de que «numElementos» sea mayor que 0, metemos en nuestro «Optional» el elemento y avanzamos inicio en 1 unidad aplicándole el módulo para que cuando llegue a 20 vuelva a ser 0. También decrementamos el número de elementos en 1.

Por último tenemos 2 métodos que nos permitirán iterar sobre la cola, uno que nos devuelve el número de elemento actual de la cola y otro que nos devuelve un boolean indicando sí quedan elementos en la cola:

public boolean hasNext() {
    boolean next = false;
    
    if (this.numElementos > 0) {
        next = true;
    }
    
    return next;
}

public int size() {
    return this.numElementos;
}

¿ Cómo se utiliza nuestra Cola ?

Veamos el código insertando «Productos»:

public class Producto {

	private int id;
	private String nombre;

	public Producto(int id, String nombre) {
		super();
		this.id = id;
		this.nombre = nombre;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getNombre() {
		return nombre;
	}

	public void setNombre(String nombre) {
		this.nombre = nombre;
	}

	@Override
	public String toString() {
		return "Producto [id=" + id + ", nombre=" + nombre + "]";
	}
}

Y nuestro main:

import java.util.Optional;

public class Main {

	public static void main(String[] args) {
		// Creamos la cola
		ColaCircularMemoriaEstatica<Producto> colaProductos = new ColaCircularMemoriaEstatica<>();

		// Creamos los productos
		Producto producto1 = new Producto(1, "Teclado");
		Producto producto2 = new Producto(2, "Pantalla");
		Producto producto3 = new Producto(3, "Raton");
		Producto producto4 = new Producto(4, "Tarjeta Gráfica");
		Producto producto5 = new Producto(5, "Disco Duro");
		Producto producto6 = new Producto(6, "Memoria RAM");

		// Encolamos 2 productos
		colaProductos.push(producto1);
		colaProductos.push(producto2);

		// Obtenemos un producto
		Optional<Producto> p = colaProductos.pop();

		if (p.isPresent()) {
			System.out.println(p.get());
		}

		// Obtenemos otro producto
		p = colaProductos.pop();

		if (p.isPresent()) {
			System.out.println(p.get());
		}

		// Insertamos otro producto
		colaProductos.push(producto3);

		// Lo obtenemos
		p = colaProductos.pop();

		if (p.isPresent()) {
			System.out.println(p.get());
		}

		// Insertamos 20 elementos

		colaProductos.push(producto1);
		colaProductos.push(producto2);
		colaProductos.push(producto3);
		colaProductos.push(producto4);
		colaProductos.push(producto5);
		colaProductos.push(producto1);
		colaProductos.push(producto2);
		colaProductos.push(producto3);
		colaProductos.push(producto4);
		colaProductos.push(producto5);
		colaProductos.push(producto1);
		colaProductos.push(producto2);
		colaProductos.push(producto3);
		colaProductos.push(producto4);
		colaProductos.push(producto5);
		colaProductos.push(producto1);
		colaProductos.push(producto2);
		colaProductos.push(producto3);
		colaProductos.push(producto4);
		colaProductos.push(producto5);

		// Los obtenemos con el while

		while (colaProductos.hasNext()) {
			p = colaProductos.pop();

			System.out.println(p.get());
		}

	}

}

Esta es nuestra salida:

Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]
Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]
Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]
Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]

Una vez hemos visto la cola circular vamos a ver la cola con Memoria Dinámica basada en Nodos.

Cola con Memoria Dinámica Basada en Nodos

Esta cola funciona de la misma forma que la anterior con respecto al funcionamiento pero su implementación es diferente, ya que está basada en memoria dinámica y nodos.

Veamos la clase Nodo y la implementación de la Cola para luego explicar ambas clases.

La clase Nodo

public class Nodo<V> {

	private V item;
	private int prioridad;
	private Nodo<V> next;

	public Nodo(V item, Nodo<V> next) {
		super();
		this.next = next;
		this.item = item;
	}

	public Nodo(V item, int prioridad, Nodo<V> next) {
		super();
		this.item = item;
		this.prioridad = prioridad;
		this.next = next;
	}

	public Nodo<V> getNext() {
		return next;
	}

	public void setNext(Nodo<V> next) {
		this.next = next;
	}

	public V getItem() {
		return item;
	}

	public void setItem(V item) {
		this.item = item;
	}

	public int getPrioridad() {
		return prioridad;
	}

	public void setPrioridad(int prioridad) {
		this.prioridad = prioridad;
	}

}

Nuestra Cola con Memoria Dinámica

import java.util.Optional;

public class ColaMemoriaDinamica<V> {

	private Nodo<V> inicio;
	private Nodo<V> fin;
	private int numElementos;
	
	public ColaMemoriaDinamica() {
		this.inicio = null;
		this.fin = null;
		this.numElementos = 0;
	}
	
	public void push(V item) {
		Nodo<V> nodo = new Nodo<>(item, null);
		
		if (inicio == null) {
			inicio = nodo;
			fin = nodo;
		}else {
			fin.setNext(nodo);
			fin = nodo;
		}
		
		this.numElementos++;
	}
	
	public Optional<V> pop(){
		Optional<V> item = Optional.empty();
		
		if (this.numElementos > 0) {
			item = Optional.of(inicio.getItem());
			this.numElementos--;
				
			inicio = inicio.getNext();
		}
		
		return item;
	}
	
	public boolean hasNext() {
		boolean next = false;
		
		if (inicio != null) {
			next = true;
		}
		
		return next;
	}
	
	public int size() {
		return this.numElementos;
	}
	
}

Con respecto a la clase Nodo esta contiene 3 atributos, uno de ellos, el de prioridad de momento lo vamos a ignorar, ya que lo utilizaremos después para nuestra cola con prioridad. Los atributos que nos interesan aquí son:

  1. private V item: Aquí almacenaremos nuestro elemento. Fijaos que utilizamos Genéricos «V».
  2. private Nodo next: Se tratará de un puntero hacia el siguiente nodo.

Veamos los atributos de la clase cola:

private Nodo<V> inicio;
private Nodo<V> fin;
private int numElementos;

Tendremos:

  1. Un nodo inicio. Apuntará al primer nodo de nuestra cola o a «null» si nuestra cola está vacía.
  2. Un nodo fin. Apuntará al último nodo de nuestra cola o a «null» si nuestra cola está vacía.
  3. Por último un entero que nos servirá para almacenar el número de elementos que tiene nuestra cola.

Veamos el constructor de nuestra clase:

public ColaMemoriaDinamica() {
    this.inicio = null;
    this.fin = null;
    this.numElementos = 0;
}

Simplemente apuntamos «inicio» a «null», «fin» a «null» y inicializamos «numElementos» a «0».

La operación encolar:

public void push(V item) {
    Nodo<V> nodo = new Nodo<>(item, null);
    
    if (inicio == null) {
        inicio = nodo;
        fin = nodo;
    }else {
        fin.setNext(nodo);
        fin = nodo;
    }
    
    this.numElementos++;
}

Nuestra operación encolar siempre crea un nuevo nodo que contendrá nuestro elemento, si «inicio == null» es porque nuestra cola está vacía, por lo tanto, apuntamos tanto «inicio» como «fin» al nuevo nodo, en caso contrario encadenamos nuestro nodo después de «fin» y hacemos fin nuestro nuevo nodo. De esta forma conseguimos ir añadiendo elementos en nuestra cola.

Inserción de un elemento en nuestra Cola
Inserción de un elemento en nuestra Cola

La operación desencolar:

public Optional<V> pop(){
    Optional<V> item = Optional.empty();
    
    if (this.numElementos > 0) {
        item = Optional.of(inicio.getItem());
        this.numElementos--;
            
        inicio = inicio.getNext();
    }
    
    return item;
}

Al igual que en nuestra implementación anterior devolvemos un «Optional», si el número de elementos es mayor que 0 hacemos el item al que apunta inicio nuestro Optional para devolverlo, luego decrementamos el número de elementos en 1 y hacemos que inicio pase a ser el siguiente nodo, de esta forma liberamos el nodo al que apuntaba inicio antes de pasar al siguiente nodo.

Por último como en el caso anterior tenemos nuestras funciones para iterar sobre la cola:

public boolean hasNext() {
    boolean next = false;
    
    if (inicio != null) {
        next = true;
    }
    
    return next;
}

public int size() {
    return this.numElementos;
}

¿ Cómo se utiliza nuestra Cola ?

import java.util.Optional;

public class MainColaDinamica {

	public static void main(String[] args) {
		//creamos la cola dinámica
		ColaMemoriaDinamica<Producto> colaProductos = new ColaMemoriaDinamica<>();

		//Creamos los productos
		Producto producto1 = new Producto(1, "Teclado");
		Producto producto2 = new Producto(2, "Pantalla");
		Producto producto3 = new Producto(3, "Raton");
		Producto producto4 = new Producto(4, "Tarjeta Gráfica");
		Producto producto5 = new Producto(5, "Disco Duro");
		Producto producto6 = new Producto(6, "Memoria RAM");

		//Insertamos 2 productos
		colaProductos.push(producto1);
		colaProductos.push(producto2);
		
		//Los obtenemos mediante un while
		Optional<Producto> item = null;

		while (colaProductos.hasNext()) {
			item = colaProductos.pop();
			System.out.println(item.get());
		}

		//Insertamos 20 productos
		colaProductos.push(producto1);
		colaProductos.push(producto2);
		colaProductos.push(producto3);
		colaProductos.push(producto4);
		colaProductos.push(producto5);
		colaProductos.push(producto1);
		colaProductos.push(producto2);
		colaProductos.push(producto3);
		colaProductos.push(producto4);
		colaProductos.push(producto5);
		colaProductos.push(producto1);
		colaProductos.push(producto2);
		colaProductos.push(producto3);
		colaProductos.push(producto4);
		colaProductos.push(producto5);
		colaProductos.push(producto1);
		colaProductos.push(producto2);
		colaProductos.push(producto3);
		colaProductos.push(producto4);
		colaProductos.push(producto5);

		//Los obtenemos
		while (colaProductos.hasNext()) {
			item = colaProductos.pop();

			System.out.println(item.get());
		}
	}
}

La salida de nuestro código

Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]
Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]
Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]
Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]

La Cola Dinámica con Prioridad

La última implementación que vamos a ver va a ser la Cola Dinámica con Prioridad, esta Cola funciona de forma ligeramente diferente a las anteriores, ya que se basa en prioridades. Podemos verla como la cola de una discoteca donde existen algunos clientes que son VIP y que por lo tanto, no tienen que hacer cola. Por lo tanto, el concepto es que los elementos con mayor prioridad siempre se insertarán en la cabeza de la Cola y después los otros elementos se irán insertando de forma descendente con respecto a su prioridad. Un ejemplo lo podemos ver a continuación:

Cola con Prioridad
Cola con Prioridad

Por lo demás su funcionamiento es igual, siempre se desencola el elemento al que apunta «inicio».

Los nodos serán objetos de nuestra clase Nodo pero ahora utilizando la prioridad:

La clase Nodo

public class Nodo<V> {

	private V item;
	private int prioridad;
	private Nodo<V> next;

	public Nodo(V item, Nodo<V> next) {
		super();
		this.next = next;
		this.item = item;
	}

	public Nodo(V item, int prioridad, Nodo<V> next) {
		super();
		this.item = item;
		this.prioridad = prioridad;
		this.next = next;
	}

	public Nodo<V> getNext() {
		return next;
	}

	public void setNext(Nodo<V> next) {
		this.next = next;
	}

	public V getItem() {
		return item;
	}

	public void setItem(V item) {
		this.item = item;
	}

	public int getPrioridad() {
		return prioridad;
	}

	public void setPrioridad(int prioridad) {
		this.prioridad = prioridad;
	}

}

La implementación de la Cola Dinámica con Prioridad

import java.util.Optional;

public class ColaDinamicaConPrioridad<V> {

	private Nodo<V> inicio;
	private Nodo<V> fin;
	private int numElementos;

	public ColaDinamicaConPrioridad() {
		this.inicio = null;
		this.fin = null;
		this.numElementos = 0;
	}

	public void push(V item, int prioridad) {
		Nodo<V> nodo = new Nodo<>(item, prioridad, null);

		if (inicio == null) {
			inicio = nodo;
			fin = nodo;
		} else {
			// Buscamos su lugar
			Nodo<V> aux = inicio;

			// Miramos si tenemos que insertar al principio
			if (aux.getPrioridad() < prioridad) {
				inicio = nodo;
				inicio.setNext(aux);
			} else {
				Nodo<V> penultimoElemento = null;

				while (aux != null && aux.getPrioridad() >= prioridad) {
					penultimoElemento = aux;
					aux = aux.getNext();
				}

				// Aqui ya tenemos donde tenemos que insertar
				penultimoElemento.setNext(nodo);
				nodo.setNext(aux);
			}

		}
		
		this.numElementos++;
	}
	
	public Optional<V> pop(){
		Optional<V> item = Optional.empty();
		
		if (this.numElementos > 0) {
			item = Optional.of(inicio.getItem());
			this.numElementos--;
				
			inicio = inicio.getNext();
		}
		
		return item;
	}
	
	public boolean hasNext() {
		boolean next = false;
		
		if (inicio != null) {
			next = true;
		}
		
		return next;
	}
	
	public int size() {
		return this.numElementos;
	}
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Nodo<V> aux = inicio;
		
		while (aux != null) {
			sb.append(aux.getItem()+ ", Prioridad: " + aux.getPrioridad() + "\n");
			aux = aux.getNext();
		}
		
		return sb.toString();
	}

}

Nuestra cola utiliza los mismos atributos de clase que la implementación anterior y el constructor es idéntico. ¿ Qué cambia realmente ?

La operación encolar:

public void push(V item, int prioridad) {
    Nodo<V> nodo = new Nodo<>(item, prioridad, null);

    if (inicio == null) {
        inicio = nodo;
        fin = nodo;
    } else {
        // Buscamos su lugar
        Nodo<V> aux = inicio;

        // Miramos si tenemos que insertar al principio
        if (aux.getPrioridad() < prioridad) {
            inicio = nodo;
            inicio.setNext(aux);
        } else {
            Nodo<V> penultimoElemento = null;

            while (aux != null && aux.getPrioridad() >= prioridad) {
                penultimoElemento = aux;
                aux = aux.getNext();
            }

            // Aqui ya tenemos donde tenemos que insertar
            penultimoElemento.setNext(nodo);
            nodo.setNext(aux);
        }

    }
    
    this.numElementos++;
}

Tenemos los siguientes casos de uso:

  • Que inicio sea igual a null, por lo tanto nuestra cola está vacía. Lo insertamos y apuntamos «inicio» y «fin» al nodo.
  • Que inicio no sea igual a null, es decir que ya tenemos elementos insertados:
    • Que el elemento que tenemos en la cola actualmente al que apunta inicio sea de menor prioridad que el que queremos insertar. Por lo tanto, ponemos como primer elemento el nuevo nodo y a este le encadenamos el que estaba antes al inicio.
    • En caso contrario tenemos que buscar la posición donde lo deberíamos insertar, por lo tanto, vamos recorriendo nodos siempre y cuando la prioridad de estos nodos sea mayor que la de nuestro nuevo nodo, cuando encontremos un nodo cuya prioridad es menor que la de nuestro nuevo nodo lo tenemos que insertar justo antes de este. Para ello utilizamos 2 punteros auxiliares, uno que apunta al nodo que estamos recorriendo en cada iteración y otro que apunta al nodo anterior. De esta forma una vez encontrado el nodo con menor prioridad solo tenemos que insertar nuestro nuevo nodo en el nodo anterior del nodo con menor prioridad y encadenar a nuestro nuevo nodo el nodo que estábamos recorriendo.

La operación de desencolar es idéntica a la de la implementación anterior ya que esta no cambia y simplemente aquí hemos añadido un método «toString» que nos permite visualizar la cola en todo momento:

public String toString() {
    StringBuilder sb = new StringBuilder();
    Nodo<V> aux = inicio;
    
    while (aux != null) {
        sb.append(aux.getItem()+ ", Prioridad: " + aux.getPrioridad() + "\n");
        aux = aux.getNext();
    }
    
    return sb.toString();
}

Nuestra clase Main

import java.util.Optional;

public class MainColaPrioridad {

	public static void main(String [] args) {
		//Creamos la cola
		ColaDinamicaConPrioridad<Producto> colaProductos = new ColaDinamicaConPrioridad<>();
		
		//Creamos los productos
		Producto producto1 = new Producto(1, "Teclado");
		Producto producto2 = new Producto(2, "Pantalla");
		Producto producto3 = new Producto(3, "Raton");
		Producto producto4 = new Producto(4, "Tarjeta Gráfica");
		Producto producto5 = new Producto(5, "Disco Duro");
		Producto producto6 = new Producto(6, "Memoria RAM");
		
		//Insertamos productos y vamos mostrando la cola en cada inserción
		colaProductos.push(producto1, 1);
		System.out.println(colaProductos);
		colaProductos.push(producto2, 4);
		System.out.println(colaProductos);
		
		colaProductos.push(producto5, 2);
		System.out.println(colaProductos);
		
		colaProductos.push(producto3, 7);
		System.out.println(colaProductos);
		colaProductos.push(producto4, 3);
		System.out.println(colaProductos);
		
		//Obtenemos todos los elementos
		Optional<Producto> p = null;

		while (colaProductos.hasNext()) {
			p = colaProductos.pop();
			System.out.println(p.get());
		}
	}
	
}

La salida de nuestro programa

Producto [id=1, nombre=Teclado], Prioridad: 1

Producto [id=2, nombre=Pantalla], Prioridad: 4
Producto [id=1, nombre=Teclado], Prioridad: 1

Producto [id=2, nombre=Pantalla], Prioridad: 4
Producto [id=5, nombre=Disco Duro], Prioridad: 2
Producto [id=1, nombre=Teclado], Prioridad: 1

Producto [id=3, nombre=Raton], Prioridad: 7
Producto [id=2, nombre=Pantalla], Prioridad: 4
Producto [id=5, nombre=Disco Duro], Prioridad: 2
Producto [id=1, nombre=Teclado], Prioridad: 1

Producto [id=3, nombre=Raton], Prioridad: 7
Producto [id=2, nombre=Pantalla], Prioridad: 4
Producto [id=4, nombre=Tarjeta Gráfica], Prioridad: 3
Producto [id=5, nombre=Disco Duro], Prioridad: 2
Producto [id=1, nombre=Teclado], Prioridad: 1

Producto [id=3, nombre=Raton]
Producto [id=2, nombre=Pantalla]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]
Producto [id=1, nombre=Teclado]

¿ Cómo utilizar la Cola del SDK de Java ?

Java también tiene disponible una Cola que podemos utilizar, esta también es genérica y muy fácil de utilizar:

import java.util.LinkedList;
import java.util.Queue;

public class MainColaJavaSDK {

	public static void main(String[] args) {
		//Creamos la cola
		Queue<Producto> colaProductos = new LinkedList<>();
		
		//Creamos los productos
		Producto producto1 = new Producto(1, "Teclado");
		Producto producto2 = new Producto(2, "Pantalla");
		Producto producto3 = new Producto(3, "Raton");
		Producto producto4 = new Producto(4, "Tarjeta Gráfica");
		Producto producto5 = new Producto(5, "Disco Duro");
		Producto producto6 = new Producto(6, "Memoria RAM");
		
		//Encolamos los productos
		colaProductos.add(producto1);
		colaProductos.add(producto2);
		colaProductos.add(producto3);
		colaProductos.add(producto4);
		colaProductos.add(producto5);
		colaProductos.add(producto6);
		
		//Obtenemos los elementos
		while (!colaProductos.isEmpty()) {
			Producto p = colaProductos.poll();
			System.out.println(p);
		}
	}

}

La salida de nuestro programa

Producto [id=1, nombre=Teclado]
Producto [id=2, nombre=Pantalla]
Producto [id=3, nombre=Raton]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=5, nombre=Disco Duro]
Producto [id=6, nombre=Memoria RAM]

¿ Cómo utilizar la Cola con Prioridad del SDK de Java?

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class MainColaJavaSDK {

	public static void main(String[] args) {
		//Creamos la cola
		Queue<Producto> colaProductos = new PriorityQueue<>(10, new ComparadorProductos());
		
		//Creamos los productos
		Producto producto1 = new Producto(1, "Teclado");
		Producto producto2 = new Producto(2, "Pantalla");
		Producto producto3 = new Producto(3, "Raton");
		Producto producto4 = new Producto(4, "Tarjeta Gráfica");
		Producto producto5 = new Producto(5, "Disco Duro");
		Producto producto6 = new Producto(6, "Memoria RAM");
		
		//Encolamos los productos
		colaProductos.add(producto1);
		colaProductos.add(producto2);
		colaProductos.add(producto3);
		colaProductos.add(producto4);
		colaProductos.add(producto5);
		colaProductos.add(producto6);
		
		//Obtenemos los elementos
		while (!colaProductos.isEmpty()) {
			Producto p = colaProductos.poll();
			System.out.println(p);
		}
	}

}

Se trata de una cola normal, pero que cuando se inicializa se le pasa una clase que servirá para comparar los productos y establecer la prioridad. Esta clase la tenemos que crear nosotros:

import java.util.Comparator;

public class ComparadorProductos implements Comparator<Producto> {

	@Override
	public int compare(Producto p1, Producto p2) {
		if (p2.getId() > p1.getId()) {
			return 1;
		}else if (p2.getId() < p1.getId()) {
			return -1;
		}else {
			return 0;
		}
	}

}

De esta forma conseguimos lo mismo que con nuestra implementación de la Cola Dinámica con Prioridad.

La salida de nuestro programa

Producto [id=6, nombre=Memoria RAM]
Producto [id=5, nombre=Disco Duro]
Producto [id=4, nombre=Tarjeta Gráfica]
Producto [id=3, nombre=Raton]
Producto [id=2, nombre=Pantalla]
Producto [id=1, nombre=Teclado]

Y esta ha sido nuestra entrada sobre la estructura de datos cola en Java.

Os dejo enlaces a la documentación de Java:

Espero que os haga gustado y recordad:

  • Suscribiros para que os lleguen las nuevas entradas (es gratis!!!!).
  • Dejad algún comentario en el blog (es gratis!!!)
  • Compartir en redes sociales (es gratis!!!)

Un saludo


COMPARTIR EN REDES SOCIALES

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *