3.2 Colas

Una cola es una estructura de datos lineal que sigue el principio FIFO (First In, First Out), es decir, el primer elemento en entrar es el primero en salir. Similar una fila en un banco, la primera persona que llega es la primera en ser atendida.

Gráficamente se vería de la siguiente forma:

Figura 3.2.1 Funcionamiento general de una cola

3.2.1 Representación en memoria

En el tema 1.4 manejo de memoria se explicó la relación entre la memoria de la computadora y las estrcuturas de datos, para el caso de la cola, al ser esta una estructura de datos, el manejo de memoria se maneja según lo ya explicado, es decir si la pila se implementa a través de arreglos (Estructuras estáticas) el manejo de memoria será forma estática (no cambia), pero si la pila se implementa a través de una estrucutura dinámica (listas) el manejo de memoria será de forma dinámica (Puede cambiar durante la ejecución del programa).

3.2.2 Operaciones básicas

  1. Orden: Los elementos se añaden por un extremo (final de la cola) y se eliminan por el otro (frente de la cola).
  2. Operaciones:
    1. Enqueue: Agregar un elemento al final de la cola.
    2. Dequeue: Eliminar y devolver el elemento del frente de la cola.
    3. Peek: Obtener el valor del elemento del frente sin eliminarlo.
    4. IsEmpty: Verificar si la cola está vacía.
    5. IsFull: Verificar si la cola está llena (en colas de tamaño fijo).

3.2.3 aplicaciones

Las colas se usan en...

Implementación de colas con la clase ArrayDeque

Java ya tiene una clase una clase que nos permite implemntar colas de forma sencilla, incluyendo las funciones antes mencionandas al igual que otras adicionales. La creación de una pila en java se hace de la siguiente manera:

                            
import java.util.ArrayDeque;

public class Cola {
    public static void main(String[] args) {
        System.out.println("Hola mundo");

        ArrayDeque< String> cola = new ArrayDeque<>();

         //Ingresamon elementos con el metodo add()
         cola.add("Luffy"); // La pila contiene:                    [Luffy]
         cola.add("Zoro");  // La pila contiene:              [Zoro, Luffy]
         cola.add("Nami");  // La pila contiene:        [Nami, Zoro, Luffy]
         cola.add("Sanji"); // La pila contiene: [sanji, Nami, Zoro, Luffy]
                                //                   fin               inicio
 
        System.out.println(cola);
        
        //Si quitamos dos elementos
        cola.poll(); // La cola contiene [sanji, Nami, Zoro]
        cola.poll(); // La cola contiene       [sanji, Nami]
        //                                     fin    inicio
        
        System.out.println(cola);
    }    
}                            
                

Implementación de una pila con un TDA

Definición del TDA (Clase Personaje)

                            
public class Personaje {

String nombre;
String ocupacion;
String cargo;

public Personaje(String n, String o, String c){
    nombre = n;
    ocupacion = o;
    cargo = c;
}

public String getPersonaje(){
    return nombre+" "+ocupacion+" "+cargo;
}

public void setPersonaje(String n, String o, String c){
    nombre = n;
    ocupacion = o;
    cargo = c;
}
}                            
                

Definición de una cola TDA (tipo Personaje)

                            
import java.util.ArrayDeque;

public class ColaTDA {

    public static void main(String[] args) {
        
        ArrayDeque< Personaje > cola = new ArrayDeque<>();
        //Forma 1 de agregar un elmento a la lista personalizada        
  
        //Agregar elementos a la Cola personalizada
        cola.add(new Personaje("Boa Hancock", "Pirata", "capitana"));
        cola.add(new Personaje("Sanji", "Pirata", "Cocinero"));

        ArrayDeque< Personaje> marines = new ArrayDeque<>();
        marines.add(new Personaje("Garp", "Marin","Vicealmirante"));
        marines.add(new Personaje("Kizaru", "Marin","Almirante"));
        marines.add(new Personaje("Akainu", "Marin", "Almirante de flota"));

        //Como es un cola de objetos, no se puede acceder directamente a la
        //información pasando como argumento la lista al mótodo print
        //Se debe realizar a travez de los métodos definidos para tal propósito

        //acceder a Kizaru
        
        for (Personaje personaje : marines) {
            System.out.println(personaje.getPersonaje());
        }
        
        //ahora elminamos un elemento de la cola con el metodo poll(), 
        //(El primero que fue ingresado)
        
        marines.poll();
        
        // Y ahora mostramos los elementos restantes en la cola
        System.out.println("\nElementos actuales en la cola: \n");
        for (Personaje personaje : marines) {
            System.out.println(personaje.getPersonaje());
        }
    }
}