Queue y operaciones

Una cola en programación es una estructura de datos que sigue el principio FIFO (First In, First Out), donde el primer elemento añadido es el primero en ser eliminado. En C#, esta estructura está implementada mediante la clase genérica Queue<T>, que forma parte del espacio de nombres System.Collections.Generic.

Las colas son ideales para situaciones donde necesitamos procesar elementos en el mismo orden en que llegan, como gestionar solicitudes en un servidor, organizar tareas en un sistema de impresión o implementar algoritmos de búsqueda por niveles.

Creación de una cola

Para crear una cola en C#, podemos utilizar diferentes constructores:

// Cola vacía
Queue<string> mensajes = new Queue<string>();

// Cola inicializada con elementos de una colección existente
string[] elementosIniciales = { "mensaje1", "mensaje2", "mensaje3" };
Queue<string> mensajesPreCargados = new Queue<string>(elementosIniciales);

// Cola con capacidad inicial específica
Queue<int> numeros = new Queue<int>(10); // Capacidad inicial de 10 elementos

Operaciones básicas

La clase Queue<T> proporciona métodos esenciales para manipular los elementos:

• Enqueue: Añade un elemento al final de la cola

Queue<string> colaClientes = new Queue<string>();
colaClientes.Enqueue("Cliente 1");
colaClientes.Enqueue("Cliente 2");
colaClientes.Enqueue("Cliente 3");
// Cola: [Cliente 1, Cliente 2, Cliente 3]

• Dequeue: Elimina y devuelve el elemento del principio de la cola

string clienteAtendido = colaClientes.Dequeue(); // Devuelve "Cliente 1"
// Cola: [Cliente 2, Cliente 3]
Console.WriteLine($"Cliente atendido: {clienteAtendido}");

• Peek: Devuelve el elemento del principio sin eliminarlo

string siguienteCliente = colaClientes.Peek(); // Devuelve "Cliente 2"
// Cola: [Cliente 2, Cliente 3] (no cambia)
Console.WriteLine($"Siguiente cliente: {siguienteCliente}");

Propiedades y métodos adicionales

La clase Queue<T> también ofrece otras propiedades y métodos útiles:

• Count: Obtiene el número de elementos en la cola

int numeroClientes = colaClientes.Count; // Devuelve 2
Console.WriteLine($"Clientes en espera: {numeroClientes}");

• Clear: Elimina todos los elementos de la cola

colaClientes.Clear();
// Cola: [] (vacía)

• Contains: Determina si un elemento está en la cola

Queue<int> numeros = new Queue<int>();
numeros.Enqueue(10);
numeros.Enqueue(20);
numeros.Enqueue(30);

bool contiene20 = numeros.Contains(20); // Devuelve true
bool contiene50 = numeros.Contains(50); // Devuelve false

• ToArray: Copia los elementos de la cola a un nuevo array

Queue<int> numeros = new Queue<int>();
numeros.Enqueue(10);
numeros.Enqueue(20);
numeros.Enqueue(30);

int[] arrayNumeros = numeros.ToArray();
// arrayNumeros: [10, 20, 30]

Recorrido de una cola

Podemos recorrer todos los elementos de una cola sin modificarla usando un bucle foreach:

Queue<string> tareas = new Queue<string>();
tareas.Enqueue("Enviar correo");
tareas.Enqueue("Actualizar base de datos");
tareas.Enqueue("Generar informe");

Console.WriteLine("Tareas pendientes:");
foreach (string tarea in tareas)
{
    Console.WriteLine($"- {tarea}");
}
// La cola permanece intacta después del recorrido

Ejemplo práctico: Sistema de procesamiento de mensajes

Veamos un ejemplo sencillo de cómo utilizar una cola para procesar mensajes en orden:

using System;
using System.Collections.Generic;
using System.Threading;

public class ProcesadorMensajes
{
    private Queue<string> colaMensajes = new Queue<string>();
    
    public void AgregarMensaje(string mensaje)
    {
        colaMensajes.Enqueue(mensaje);
        Console.WriteLine($"Mensaje añadido a la cola: {mensaje}");
    }
    
    public void ProcesarMensajes()
    {
        Console.WriteLine($"Iniciando procesamiento. Mensajes en cola: {colaMensajes.Count}");
        
        while (colaMensajes.Count > 0)
        {
            string mensaje = colaMensajes.Dequeue();
            Console.WriteLine($"Procesando: {mensaje}");
            
            // Simulamos procesamiento
            Thread.Sleep(1000);
            
            Console.WriteLine($"Mensaje procesado: {mensaje}");
        }
        
        Console.WriteLine("Todos los mensajes han sido procesados.");
    }
}

Uso del procesador de mensajes:

ProcesadorMensajes procesador = new ProcesadorMensajes();

procesador.AgregarMensaje("Actualizar perfil de usuario");
procesador.AgregarMensaje("Enviar correo de confirmación");
procesador.AgregarMensaje("Generar factura");

procesador.ProcesarMensajes();

Consideraciones de rendimiento

• Las operaciones Enqueue, Dequeue y Peek tienen una complejidad de tiempo O(1), lo que las hace muy eficientes.
• Si conoces aproximadamente cuántos elementos contendrá la cola, es recomendable especificar la capacidad inicial para evitar redimensionamientos.
• Las colas no están diseñadas para búsquedas aleatorias o acceso por índice. Si necesitas estas operaciones, considera usar otras estructuras como List<T>.

Escenarios de uso comunes

Las colas son especialmente útiles en los siguientes escenarios:

• Sistemas de mensajería: Para procesar mensajes en el orden en que llegan.
• Algoritmos de búsqueda por anchura (BFS): Para explorar nodos en un grafo o árbol por niveles.
• Gestión de tareas: Para ejecutar tareas en el orden en que fueron programadas.
• Buffers: Para almacenar datos temporalmente mientras se procesan.
• Impresión y spooling: Para gestionar trabajos de impresión en orden.

Stack y operaciones

Una pila es una estructura de datos que sigue el principio LIFO (Last In, First Out), donde el último elemento añadido es el primero en ser eliminado. En C#, esta estructura está implementada mediante la clase genérica Stack<T>, que forma parte del espacio de nombres System.Collections.Generic.

Las pilas son perfectas para escenarios donde necesitamos acceder a los elementos en orden inverso a como fueron agregados, como en la gestión de llamadas a funciones, evaluación de expresiones o algoritmos de recorrido en profundidad.

Creación de una pila

Podemos crear una pila en C# utilizando diferentes constructores:

// Pila vacía
Stack<int> numeros = new Stack<int>();

// Pila inicializada con elementos de una colección existente
List<string> listaInicial = new List<string> { "elemento3", "elemento2", "elemento1" };
Stack<string> pilaDesdeColeccion = new Stack<string>(listaInicial);

// Pila con capacidad inicial específica
Stack<double> valores = new Stack<double>(20); // Capacidad inicial de 20 elementos

Operaciones básicas

La clase Stack<T> proporciona métodos fundamentales para manipular los elementos:

• Push: Añade un elemento en la parte superior de la pila

Stack<string> historial = new Stack<string>();
historial.Push("Página Inicio");
historial.Push("Página Productos");
historial.Push("Página Detalle");
// Pila: [Página Detalle, Página Productos, Página Inicio]

• Pop: Elimina y devuelve el elemento de la parte superior de la pila

string paginaActual = historial.Pop(); // Devuelve "Página Detalle"
// Pila: [Página Productos, Página Inicio]
Console.WriteLine($"Saliendo de: {paginaActual}");

• Peek: Devuelve el elemento superior sin eliminarlo

string paginaAnterior = historial.Peek(); // Devuelve "Página Productos"
// Pila: [Página Productos, Página Inicio] (no cambia)
Console.WriteLine($"Si retrocedes irás a: {paginaAnterior}");

Propiedades y métodos adicionales

La clase Stack<T> también ofrece otras propiedades y métodos útiles:

• Count: Obtiene el número de elementos en la pila

int nivelHistorial = historial.Count; // Devuelve 2
Console.WriteLine($"Profundidad del historial: {nivelHistorial}");

• Clear: Elimina todos los elementos de la pila

historial.Clear();
// Pila: [] (vacía)

• Contains: Determina si un elemento está en la pila

Stack<int> niveles = new Stack<int>();
niveles.Push(1);
niveles.Push(2);
niveles.Push(3);

bool contiene2 = niveles.Contains(2); // Devuelve true
bool contiene5 = niveles.Contains(5); // Devuelve false

• ToArray: Copia los elementos de la pila a un nuevo array

Stack<char> caracteres = new Stack<char>();
caracteres.Push('A');
caracteres.Push('B');
caracteres.Push('C');

char[] arrayCaracteres = caracteres.ToArray();
// arrayCaracteres: ['C', 'B', 'A'] (orden inverso a la inserción)

Recorrido de una pila

Podemos recorrer todos los elementos de una pila sin modificarla usando un bucle foreach:

Stack<string> libros = new Stack<string>();
libros.Push("El principito");
libros.Push("1984");
libros.Push("Don Quijote");

Console.WriteLine("Libros (del más reciente al más antiguo):");
foreach (string libro in libros)
{
    Console.WriteLine($"- {libro}");
}
// La pila permanece intacta después del recorrido

Ejemplo práctico: Verificador de paréntesis balanceados

Un uso común de las pilas es verificar si una expresión tiene paréntesis balanceados:

using System;
using System.Collections.Generic;

public class VerificadorParentesis
{
    public bool EstanBalanceados(string expresion)
    {
        Stack<char> pila = new Stack<char>();
        
        foreach (char c in expresion)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                // Si es un paréntesis de apertura, lo añadimos a la pila
                pila.Push(c);
            }
            else if (c == ')' || c == ']' || c == '}')
            {
                // Si la pila está vacía, no hay paréntesis de apertura correspondiente
                if (pila.Count == 0)
                    return false;
                
                // Obtenemos el último paréntesis de apertura
                char ultimo = pila.Pop();
                
                // Verificamos si coincide con el paréntesis de cierre actual
                if ((c == ')' && ultimo != '(') ||
                    (c == ']' && ultimo != '[') ||
                    (c == '}' && ultimo != '{'))
                {
                    return false;
                }
            }
        }
        
        // Si la pila está vacía, todos los paréntesis están balanceados
        return pila.Count == 0;
    }
}

Uso del verificador de paréntesis:

VerificadorParentesis verificador = new VerificadorParentesis();

string expresion1 = "((a + b) * [c - d])";
string expresion2 = "((a + b) * [c - d}";
string expresion3 = "((a + b) * [c - d";

Console.WriteLine($"'{expresion1}' está balanceada: {verificador.EstanBalanceados(expresion1)}");
Console.WriteLine($"'{expresion2}' está balanceada: {verificador.EstanBalanceados(expresion2)}");
Console.WriteLine($"'{expresion3}' está balanceada: {verificador.EstanBalanceados(expresion3)}");

// Resultado:
// '((a + b) * [c - d])' está balanceada: True
// '((a + b) * [c - d}' está balanceada: False
// '((a + b) * [c - d' está balanceada: False

Ejemplo: Inversión de elementos

Las pilas son ideales para invertir el orden de elementos:

public static List<T> InvertirLista<T>(List<T> lista)
{
    Stack<T> pila = new Stack<T>(lista);
    return new List<T>(pila);
}

// Uso:
List<int> original = new List<int> { 1, 2, 3, 4, 5 };
List<int> invertida = InvertirLista(original);
// invertida: [5, 4, 3, 2, 1]

Consideraciones de rendimiento

• Las operaciones Push, Pop y Peek tienen una complejidad de tiempo O(1), lo que las hace muy eficientes.
• Si conoces aproximadamente cuántos elementos contendrá la pila, es recomendable especificar la capacidad inicial para evitar redimensionamientos.
• Las pilas no están diseñadas para búsquedas aleatorias o acceso por índice. Si necesitas estas operaciones, considera usar List<T>.

Escenarios de uso comunes

Las pilas son especialmente útiles en los siguientes escenarios:

• Gestión de llamadas a funciones: El sistema utiliza una pila para recordar el punto de retorno cuando se llama a una función.
• Evaluación de expresiones: Para convertir expresiones infix a postfix o evaluar expresiones postfix.
• Algoritmos de recorrido en profundidad (DFS): Para explorar ramas completas antes de retroceder.
• Historial de navegación: Para implementar funcionalidades de "atrás" en navegadores o aplicaciones.
• Deshacer/rehacer operaciones: Para mantener un historial de acciones que se pueden deshacer.