Colas#
Objetivos#
Comprender el concepto y las características de la estructura de datos Cola.
Implementar colas en Java utilizando arreglos y nodos (listas enlazadas).
Practicar el uso de operaciones básicas como enqueue y dequeue.
Aplicar la estructura de colas en ejemplos prácticos.
Introducción#
En la programación y ciencias de la computación, una cola (Queue) es una estructura de datos lineal que sigue el principio FIFO (First In, First Out). Esto significa que el primer elemento en entrar es el primero en salir, tal como una fila en una tienda o en un banco. La cola tiene dos operaciones principales:
Encolar (enqueue): añadir un elemento al final de la cola.
Desencolar (dequeue): eliminar el elemento al frente de la cola.
Las colas son muy utilizadas en problemas relacionados con sistemas de gestión de tareas, simulaciones y procesamiento de datos, entre otros.
Concepto de Cola#
Una cola es una colección ordenada de elementos donde el acceso es restringido. Se caracteriza por:
Inserción de elementos al final (también llamado «cola» o «final»).
Eliminación de elementos desde el frente (el primero en entrar).
El comportamiento FIFO es ideal en situaciones donde se requiere un procesamiento por orden de llegada. Las colas tienen una amplia variedad de implementaciones, incluyendo colas circulares, colas de prioridad, y doble cola (deque), pero aquí nos enfocaremos en la cola básica.
Implementaciones de Colas en Java#
Usando Arreglos#
La implementación de colas con arreglos es directa, pero tiene una desventaja: el tamaño de la cola es fijo y si no se utiliza adecuadamente puede haber desperdicio de espacio. A continuación, se muestra cómo se puede implementar una cola usando arreglos:
class ColaArray {
private int[] cola;
private int frente;
private int finalCola;
private int capacidad;
// Constructor para inicializar la cola
public ColaArray(int tamano) {
capacidad = tamano;
cola = new int[capacidad];
frente = 0;
finalCola = -1;
}
// Método para encolar (agregar) un elemento
public void enqueue(int elemento) {
if (finalCola == capacidad - 1) {
System.out.println("Cola llena");
return;
}
cola[++finalCola] = elemento;
}
// Método para desencolar (eliminar) un elemento
public int dequeue() {
if (estaVacia()) {
System.out.println("Cola vacía");
return -1;
}
return cola[frente++];
}
// Verificar si la cola está vacía
public boolean estaVacia() {
return frente > finalCola;
}
// Método para obtener el frente de la cola sin desencolarlo
public int frente() {
if (estaVacia()) {
System.out.println("Cola vacía");
return -1;
}
return cola[frente];
}
}
public class Main {
public static void main(String[] args) {
ColaArray cola = new ColaArray(5);
cola.enqueue(10);
cola.enqueue(20);
cola.enqueue(30);
System.out.println("Desencolado: " + cola.dequeue());
System.out.println("Frente actual: " + cola.frente());
}
}
Modifica el anterior código: agrega más elementos, elimina, imprime, etc. Además, crea objetos y prueba la clase
// Prueba tu código aquí
Explicación del código:#
enqueue(): Añade un nuevo elemento al final de la cola. Si la cola está llena, se muestra un mensaje.
dequeue(): Elimina y devuelve el elemento al frente de la cola. Si la cola está vacía, devuelve -1.
frente(): Devuelve el elemento del frente sin eliminarlo.
estaVacia(): Comprueba si la cola está vacía.
Desventaja:
En este caso, una vez que se ha encolado y desencolado un número determinado de elementos, la cola deja de funcionar correctamente porque los índices
frenteyfinalColasiguen incrementándose sin reusarse. Esto puede solucionarse con una cola circular.
Usando Nodos (Listas Enlazadas)#
Otra forma eficiente de implementar una cola es mediante una lista enlazada donde los nodos almacenan datos y una referencia al siguiente nodo en la cola. Este enfoque no tiene un tamaño fijo como los arreglos y se adapta mejor al uso dinámico de la memoria.
class Nodo {
int dato;
Nodo siguiente;
// Constructor del nodo
public Nodo(int dato) {
this.dato = dato;
this.siguiente = null;
}
}
class ColaListaEnlazada {
private Nodo frente, finalCola;
// Constructor para inicializar la cola
public ColaListaEnlazada() {
this.frente = null;
this.finalCola = null;
}
// Método para encolar un elemento
public void enqueue(int dato) {
Nodo nuevoNodo = new Nodo(dato);
if (finalCola == null) {
frente = finalCola = nuevoNodo;
} else {
finalCola.siguiente = nuevoNodo;
finalCola = nuevoNodo;
}
}
// Método para desencolar un elemento
public int dequeue() {
if (frente == null) {
System.out.println("Cola vacía");
return -1;
}
int dato = frente.dato;
frente = frente.siguiente;
if (frente == null) {
finalCola = null;
}
return dato;
}
// Verificar si la cola está vacía
public boolean estaVacia() {
return frente == null;
}
// Método para obtener el frente de la cola sin desencolarlo
public int frente() {
if (frente == null) {
System.out.println("Cola vacía");
return -1;
}
return frente.dato;
}
}
public class Main {
public static void main(String[] args) {
ColaListaEnlazada cola = new ColaListaEnlazada();
cola.enqueue(10);
cola.enqueue(20);
cola.enqueue(30);
System.out.println("Frente actual: " + cola.frente());
System.out.println("Desencolado: " + cola.dequeue());
System.out.println("Frente actual después de desencolar: " + cola.frente());
}
}
Explicación del código:#
Nodo: Cada nodo de la cola contiene el dato y una referencia al siguiente nodo.
enqueue(): Inserta un nuevo nodo al final de la cola.
dequeue(): Elimina y devuelve el nodo al frente.
estaVacia(): Comprueba si la cola está vacía.
Ventaja:
La lista enlazada permite crear colas dinámicas de tamaño ilimitado, ya que no depende de un tamaño de arreglo fijo.
// Prueba tu código aquí
Usando la interfaz de Java#
Colas#
Utilizando la clase de java Queue.java, implementen una cola con el tema que más les guste.
Figura 41 Here is my figure caption!#
Figura 42 Here is my figure caption!#
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
public class Fila<T> implements Queue<T> {
private LinkedList<T> elementos;
public Fila() {
elementos = new LinkedList<>();
}
@Override
public boolean add(T e) {
return elementos.add(e); // Agrega un elemento al final de la cola
}
@Override
public boolean offer(T e) {
return elementos.add(e); // Similar a add, pero no lanza una excepción si falla
}
@Override
public T remove() {
if (elementos.isEmpty()) {
throw new NoSuchElementException("La cola está vacía");
}
return elementos.removeFirst(); // Remueve el primer elemento de la cola
}
@Override
public T poll() {
return elementos.isEmpty() ? null : elementos.removeFirst(); // Devuelve y remueve el primer elemento o null si está vacía
}
@Override
public T element() {
if (elementos.isEmpty()) {
throw new NoSuchElementException("La cola está vacía");
}
return elementos.getFirst(); // Devuelve el primer elemento sin removerlo
}
@Override
public T peek() {
return elementos.isEmpty() ? null : elementos.getFirst(); // Devuelve el primer elemento o null si está vacía
}
@Override
public int size() {
return elementos.size(); // Devuelve el tamaño de la cola
}
@Override
public boolean isEmpty() {
return elementos.isEmpty(); // Verifica si la cola está vacía
}
@Override
public boolean contains(Object o) {
return elementos.contains(o); // Verifica si la cola contiene el elemento
}
@Override
public Iterator<T> iterator() {
return elementos.iterator(); // Devuelve un iterador para recorrer los elementos de la cola
}
@Override
public Object[] toArray() {
return elementos.toArray(); // Convierte la cola a un array de objetos
}
@Override
public <U> U[] toArray(U[] a) {
return elementos.toArray(a); // Convierte la cola a un array de un tipo específico
}
@Override
public boolean remove(Object o) {
return elementos.remove(o); // Remueve un objeto de la cola
}
@Override
public boolean containsAll(Collection<?> c) {
return elementos.containsAll(c); // Verifica si la cola contiene todos los elementos de la colección dada
}
@Override
public boolean addAll(Collection<? extends T> c) {
return elementos.addAll(c); // Agrega todos los elementos de la colección dada a la cola
}
@Override
public boolean removeAll(Collection<?> c) {
return elementos.removeAll(c); // Remueve todos los elementos de la colección dada de la cola
}
@Override
public boolean retainAll(Collection<?> c) {
return elementos.retainAll(c); // Retiene solo los elementos presentes en la colección dada
}
@Override
public void clear() {
elementos.clear(); // Limpia todos los elementos de la cola
}
@Override
public String toString() {
return elementos.toString(); // Convierte la lista de elementos a una cadena y la devuelve
}
}
public class Main {
public static void main(String[] args) {
Fila<String> fila = new Fila<>();
// Agregar elementos a la cola
fila.add("Sebas");
fila.add("tian");
fila.add("Aguilera");
System.out.println(fila);
// Ver el primer elemento sin removerlo
System.out.println("Primer elemento: " + fila.peek());
// Remover el primer elemento de la cola
System.out.println("Elemento removido: " + fila.remove());
// Verificar si contiene el número 2
System.out.println("¿Contiene el número 2? " + fila.contains(2));
// Ver el tamaño de la cola
System.out.println("Tamaño de la cola: " + fila.size());
System.out.println(fila);
}
}
new Main().main(null);
[Sebas, tian, Aguilera]
Primer elemento: Sebas
Elemento removido: Sebas
¿Contiene el número 2? false
Tamaño de la cola: 2
[tian, Aguilera]
Colas Prioritarias#
Figura 43 Ejemplo pila prioritaria de números.#
Figura 44 Método de organización de las pilas prioritarias.#
Utilizando la clase de java PriorityQueue.java, implementen una cola con el tema que más les guste.
Figura 45 Here is my figure caption!#
// Prueba tu código aquí
Otros Tipos de Colas#
Colas Circulares#
Cola de Doble Extremo#
Aplicación de Colas#
Las colas son útiles en muchos problemas de la vida real y en la programación. Algunos ejemplos incluyen:
Gestión de tareas en sistemas operativos: Las colas gestionan tareas que se deben procesar de acuerdo al orden de llegada.
Sistemas de impresión: Una impresora puede utilizar una cola para manejar múltiples trabajos de impresión en orden.
Sistemas de soporte al cliente: Para atender solicitudes de los clientes en orden de llegada.
Simulaciones: En simulaciones de procesos industriales, como líneas de ensamblaje o tráfico.
Ejercicio: Aplicación de Pilas y Colas a un Problema de Interés#
Taller 6
El objetivo de este taller es que los estudiantes apliquen las estructuras de datos Pilas (Stacks) y Colas (Queues) a un problema real de su interés. Deberán analizar y proponer una solución que emplee ambas estructuras, identificar las ventajas y desventajas de cada una, y decidir cuál es más adecuada para resolver el problema en cuestión.
Instrucciones
Escoge un problema: Piensa en un problema de la vida real o de un ámbito que te apasione, que pueda modelarse con una estructura de datos como una pila o una cola. Algunos ejemplos pueden ser:
Gestión de tareas en una aplicación de productividad.
Organización de tickets en una cola de atención al cliente.
Control de operaciones matemáticas (como evaluaciones de expresiones).
Sistemas de llamadas en una central telefónica.
Gestión de pacientes en una sala de espera de hospital.
Un videojuego donde se maneja el inventario de objetos del jugador.
Sugerencias de Problemas
Si tienes dificultades para encontrar un problema que te apasione, aquí tienes algunas sugerencias:
Sistema de colas en un banco: Simula la llegada de clientes a un banco y cómo son atendidos según una cola o una pila.
Sistema de deshacer y rehacer en un editor de texto: Modela las operaciones de deshacer (ctrl+z) y rehacer (ctrl+y) utilizando una pila.
Entrega de paquetes en una empresa de logística: Modela el sistema de organización y entrega de paquetes según una cola o una pila.
Simulación de un parqueadero: Simula cómo entran y salen los autos de un parqueadero usando una pila o una cola.
Juego de cartas: Modela el manejo de una baraja de cartas, donde el jugador extrae o apila cartas en función de una pila o una cola.
Plantea el problema: Define claramente cuál es el problema que quieres resolver. Algunos elementos a considerar:
¿Qué tipo de datos se gestionan?
¿Cómo deben ser organizados los datos?
¿Cuál es el orden de procesamiento de los datos (último en entrar, primero en salir; o primero en entrar, primero en salir)?
Describe el uso de una pila (Stack): Explica cómo resolverías tu problema usando una Pila. Describe en detalle:
¿Por qué utilizarías una pila?
¿Cuál sería la lógica detrás de la solución basada en LIFO (Last In, First Out)?
¿Qué tipo de operaciones harías con la pila? (inserción, eliminación, consulta)
Ventajas y desventajas de este enfoque en tu problema.
Describe el uso de una cola (Queue): Explica cómo resolverías tu problema utilizando una Cola. Describe en detalle:
¿Por qué utilizarías una cola?
¿Cuál sería la lógica detrás de la solución basada en FIFO (First In, First Out)?
¿Qué tipo de operaciones harías con la cola? (inserción, eliminación, consulta)
Ventajas y desventajas de este enfoque en tu problema.
Comparación: Realiza una comparación entre ambos enfoques (uso de pila vs. uso de cola):
¿Cuál estructura de datos es más eficiente o apropiada para resolver el problema que escogiste?
¿Existen limitaciones o problemas específicos con cada enfoque?
¿Cuál es tu recomendación final sobre cuál estructura de datos es la mejor para este caso y por qué?
Conclusiones: Reflexiona sobre lo que has aprendido en este proceso. Considera las siguientes preguntas:
¿Qué te ha aportado aplicar estos conceptos a un problema de tu interés?
¿Cómo las diferentes estructuras de datos permiten resolver problemas de manera más o menos eficiente?
¿Qué aprendiste sobre el proceso de elegir la estructura de datos adecuada para un problema específico?
Entregables
Descripción del problema: Explicación clara del problema elegido.
Solución basada en pila: Descripción detallada del uso de la pila para resolver el problema, incluyendo sus ventajas y desventajas.
Solución basada en cola: Descripción detallada del uso de la cola para resolver el problema, incluyendo sus ventajas y desventajas.
Comparación entre ambos enfoques: Comparación estructurada entre las dos soluciones.
Conclusiones: Reflexión personal sobre el ejercicio, los aprendizajes obtenidos y el proceso de decisión.
Criterios de Evaluación
Creatividad y originalidad del problema propuesto.
Claridad en la descripción del problema y en la solución propuesta con pilas y colas.
Profundidad de la comparación entre ambas estructuras de datos.
Reflexión y análisis en las conclusiones.
Conclusiones#
La estructura de datos cola es una herramienta fundamental en programación, con aplicaciones en numerosos sistemas y algoritmos. Entender su implementación tanto con arreglos como con nodos (listas enlazadas) es esencial para trabajar eficientemente en proyectos que requieran gestionar el orden de ejecución o procesamiento. Su principio FIFO la hace ideal para situaciones en las que el primer elemento en ingresar debe ser el primero en ser procesado.