Ir al contenido principal

Pilas y colas

Las pilas y colas son estructuras de datos fundamentales que siguen reglas específicas para el acceso y manipulación de elementos. A diferencia de los arrays o listas donde puedes acceder a cualquier elemento directamente, estas estructuras imponen un orden particular que resulta extremadamente útil en numerosos algoritmos y aplicaciones del mundo real. Su comportamiento predecible y sus operaciones eficientes las convierten en herramientas esenciales para resolver problemas complejos de programación.

Estas estructuras son la base de muchos sistemas informáticos: desde el manejo de la memoria en los programas hasta la gestión de tareas en sistemas operativos, pasando por algoritmos de navegación web y procesamiento de datos. Comprender su funcionamiento te permitirá abordar problemas de programación de manera más elegante y eficiente.

Pilas (Stack)

Una pila es una estructura de datos que sigue el principio LIFO (Last In, First Out), lo que significa que el último elemento que se añade es el primero que se retira. Imagina una pila de platos: solo puedes añadir o quitar platos de la parte superior.

Características de las pilas

Característica Descripción
Principio LIFO El último elemento añadido es el primero en salir
Punto de acceso único Solo se puede acceder al elemento superior
Operaciones principales Push (apilar), Pop (desapilar), Peek (mirar)
Acceso restringido No se puede acceder a elementos intermedios directamente
Uso de memoria eficiente Operaciones en tiempo constante O(1)

Operaciones principales de una pila

Operación Descripción Complejidad
Push(item) Añade un elemento al tope de la pila O(1)
Pop() Retira y devuelve el elemento del tope O(1)
Peek() o Top() Devuelve el elemento del tope sin retirarlo O(1)
Count Devuelve el número de elementos O(1)
Contains(item) Verifica si un elemento está en la pila O(n)

Implementación básica de pilas en C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Crear una pila de enteros
        Stack<int> numeros = new Stack<int>();
        
        Console.WriteLine("=== Operaciones básicas con pilas ===");
        
        // Push: añadir elementos
        numeros.Push(10);
        numeros.Push(20);
        numeros.Push(30);
        numeros.Push(40);
        
        Console.WriteLine($"Elementos en la pila: {numeros.Count}");
        
        // Peek: ver el elemento superior sin retirarlo
        Console.WriteLine($"Elemento en el tope: {numeros.Peek()}");
        Console.WriteLine($"Elementos después de Peek: {numeros.Count}");
        
        // Pop: retirar elementos
        Console.WriteLine($"Elemento retirado: {numeros.Pop()}");
        Console.WriteLine($"Nuevo elemento en el tope: {numeros.Peek()}");
        Console.WriteLine($"Elementos restantes: {numeros.Count}");
        
        // Verificar si la pila está vacía
        Console.WriteLine($"¿Está vacía? {numeros.Count == 0}");
    }
}

Recorrido y manipulación de pilas

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Stack<string> palabras = new Stack<string>();
        
        // Añadir palabras
        palabras.Push("Hola");
        palabras.Push("mundo");
        palabras.Push("desde");
        palabras.Push("C#");
        
        Console.WriteLine("=== Recorrido de la pila ===");
        Console.WriteLine("Orden de salida (LIFO):");
        
        // Método 1: Recorrido sin modificar la pila
        foreach (string palabra in palabras)
        {
            Console.WriteLine($"- {palabra}");
        }
        Console.WriteLine($"Elementos después del recorrido: {palabras.Count}");
        
        Console.WriteLine("\n=== Vaciado de la pila ===");
        // Método 2: Vaciar la pila usando Pop
        while (palabras.Count > 0)
        {
            string palabraRetirada = palabras.Pop();
            Console.WriteLine($"Retirada: {palabraRetirada}");
        }
        
        Console.WriteLine($"Elementos finales: {palabras.Count}");
    }
}

Ejemplo práctico: validación de paréntesis

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] expresiones = {
            "(a + b) * c",
            "((a + b) * (c - d))",
            "(a + b * c",
            "a + b) * c",
            "[{()}]",
            "[{(})]"
        };
        
        Console.WriteLine("=== Validación de paréntesis ===");
        
        foreach (string expresion in expresiones)
        {
            bool esValida = ValidarParentesis(expresion);
            Console.WriteLine($"{expresion,-20} -> {(esValida ? "Válida" : "Inválida")}");
        }
    }
    
    static bool ValidarParentesis(string expresion)
    {
        Stack<char> pila = new Stack<char>();
        
        foreach (char caracter in expresion)
        {
            // Si es un paréntesis de apertura, lo apilamos
            if (caracter == '(' || caracter == '[' || caracter == '{')
            {
                pila.Push(caracter);
            }
            // Si es un paréntesis de cierre, verificamos
            else if (caracter == ')' || caracter == ']' || caracter == '}')
            {
                // Si la pila está vacía, hay un cierre sin apertura
                if (pila.Count == 0)
                    return false;
                
                char apertura = pila.Pop();
                
                // Verificar que coincidan los tipos
                if ((caracter == ')' && apertura != '(') ||
                    (caracter == ']' && apertura != '[') ||
                    (caracter == '}' && apertura != '{'))
                {
                    return false;
                }
            }
        }
        
        // La expresión es válida si la pila está vacía al final
        return pila.Count == 0;
    }
}

Colas (Queue)

Una cola es una estructura de datos que sigue el principio FIFO (First In, First Out), lo que significa que el primer elemento que se añade es el primero que se retira. Es como una cola de personas: quien llega primero, es atendido primero.

Características de las colas

Característica Descripción
Principio FIFO El primer elemento añadido es el primero en salir
Dos puntos de acceso Entrada por un extremo, salida por el otro
Operaciones principales Enqueue (encolar), Dequeue (desencolar), Peek
Orden preservado Mantiene el orden de llegada de los elementos
Procesamiento secuencial Ideal para procesar elementos en orden

Operaciones principales de una cola

Operación Descripción Complejidad
Enqueue(item) Añade un elemento al final de la cola O(1)
Dequeue() Retira y devuelve el primer elemento O(1)
Peek() Devuelve el primer elemento sin retirarlo O(1)
Count Devuelve el número de elementos O(1)
Contains(item) Verifica si un elemento está en la cola O(n)

Implementación básica de colas en C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Crear una cola de cadenas
        Queue<string> cola = new Queue<string>();
        
        Console.WriteLine("=== Operaciones básicas con colas ===");
        
        // Enqueue: añadir elementos
        cola.Enqueue("Primer cliente");
        cola.Enqueue("Segundo cliente");
        cola.Enqueue("Tercer cliente");
        cola.Enqueue("Cuarto cliente");
        
        Console.WriteLine($"Clientes en la cola: {cola.Count}");
        
        // Peek: ver el primer elemento sin retirarlo
        Console.WriteLine($"Próximo cliente: {cola.Peek()}");
        Console.WriteLine($"Clientes después de Peek: {cola.Count}");
        
        // Dequeue: atender (retirar) clientes
        Console.WriteLine($"Atendiendo a: {cola.Dequeue()}");
        Console.WriteLine($"Siguiente cliente: {cola.Peek()}");
        Console.WriteLine($"Clientes restantes: {cola.Count}");
        
        // Verificar si la cola está vacía
        Console.WriteLine($"¿Cola vacía? {cola.Count == 0}");
    }
}

Recorrido y manipulación de colas

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Queue<int> numeros = new Queue<int>();
        
        // Añadir números
        for (int i = 1; i <= 5; i++)
        {
            numeros.Enqueue(i * 10);
        }
        
        Console.WriteLine("=== Recorrido de la cola ===");
        Console.WriteLine("Orden de salida (FIFO):");
        
        // Método 1: Recorrido sin modificar la cola
        foreach (int numero in numeros)
        {
            Console.WriteLine($"- {numero}");
        }
        Console.WriteLine($"Elementos después del recorrido: {numeros.Count}");
        
        Console.WriteLine("\n=== Procesamiento de la cola ===");
        // Método 2: Procesar todos los elementos
        while (numeros.Count > 0)
        {
            int numeroAtendido = numeros.Dequeue();
            Console.WriteLine($"Procesando: {numeroAtendido}");
        }
        
        Console.WriteLine($"Elementos finales: {numeros.Count}");
    }
}

Ejemplo práctico: simulador de atención al cliente

using System;
using System.Collections.Generic;

class Cliente
{
    public string Nombre { get; set; }
    public string Tipo { get; set; }
    public DateTime HoraLlegada { get; set; }
    
    public Cliente(string nombre, string tipo)
    {
        Nombre = nombre;
        Tipo = tipo;
        HoraLlegada = DateTime.Now;
    }
    
    public override string ToString()
    {
        return $"{Nombre} ({Tipo}) - {HoraLlegada:HH:mm:ss}";
    }
}

class Program
{
    static void Main()
    {
        Queue<Cliente> colaAtencion = new Queue<Cliente>();
        
        Console.WriteLine("=== Simulador de Atención al Cliente ===\n");
        
        // Llegada de clientes
        colaAtencion.Enqueue(new Cliente("Ana García", "Consulta"));
        colaAtencion.Enqueue(new Cliente("Luis Pérez", "Reclamo"));
        colaAtencion.Enqueue(new Cliente("María López", "Consulta"));
        colaAtencion.Enqueue(new Cliente("Carlos Ruiz", "Trámite"));
        
        Console.WriteLine("Clientes en espera:");
        int posicion = 1;
        foreach (Cliente cliente in colaAtencion)
        {
            Console.WriteLine($"{posicion}. {cliente}");
            posicion++;
        }
        
        Console.WriteLine($"\nTotal de clientes en cola: {colaAtencion.Count}");
        
        // Simular atención de clientes
        Console.WriteLine("\n=== Inicio de atención ===");
        int numeroAtencion = 1;
        
        while (colaAtencion.Count > 0)
        {
            Cliente clienteAtendido = colaAtencion.Dequeue();
            TimeSpan tiempoEspera = DateTime.Now - clienteAtendido.HoraLlegada;
            
            Console.WriteLine($"Atención #{numeroAtencion}:");
            Console.WriteLine($"  Cliente: {clienteAtendido.Nombre}");
            Console.WriteLine($"  Tipo: {clienteAtendido.Tipo}");
            Console.WriteLine($"  Tiempo de espera: {tiempoEspera.TotalSeconds:F1} segundos");
            Console.WriteLine($"  Clientes restantes: {colaAtencion.Count}");
            Console.WriteLine();
            
            numeroAtencion++;
            
            // Simular tiempo de atención
            System.Threading.Thread.Sleep(1000);
        }
        
        Console.WriteLine("Todos los clientes han sido atendidos.");
    }
}

Comparación entre pilas y colas

Diferencias principales

Aspecto Pila (Stack) Cola (Queue)
Principio LIFO (Last In, First Out) FIFO (First In, First Out)
Punto de acceso Solo desde el tope Entrada por atrás, salida por delante
Analogía Pila de platos Cola de personas
Uso típico Deshacer acciones, recursión Procesamiento por orden, planificación

Ejemplo comparativo

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Console.WriteLine("=== Comparación Pila vs Cola ===\n");
        
        // Datos de prueba
        string[] elementos = {"A", "B", "C", "D", "E"};
        
        // Usar pila
        Stack<string> pila = new Stack<string>();
        Console.WriteLine("Añadiendo elementos a la pila:");
        foreach (string elemento in elementos)
        {
            pila.Push(elemento);
            Console.WriteLine($"Push: {elemento}");
        }
        
        Console.WriteLine("\nRetirando elementos de la pila (LIFO):");
        while (pila.Count > 0)
        {
            Console.WriteLine($"Pop: {pila.Pop()}");
        }
        
        Console.WriteLine("\n" + new string('-', 40) + "\n");
        
        // Usar cola
        Queue<string> cola = new Queue<string>();
        Console.WriteLine("Añadiendo elementos a la cola:");
        foreach (string elemento in elementos)
        {
            cola.Enqueue(elemento);
            Console.WriteLine($"Enqueue: {elemento}");
        }
        
        Console.WriteLine("\nRetirando elementos de la cola (FIFO):");
        while (cola.Count > 0)
        {
            Console.WriteLine($"Dequeue: {cola.Dequeue()}");
        }
    }
}

Casos de uso comunes

Cuándo usar pilas:

  • Deshacer operaciones (Ctrl+Z en editores)
  • Navegación web (botón "Atrás" del navegador)
  • Evaluación de expresiones matemáticas
  • Manejo de llamadas a funciones (call stack)
  • Algoritmos de recorrido en profundidad

Cuándo usar colas:

  • Procesamiento de tareas en orden de llegada
  • Sistemas de impresión (cola de documentos)
  • Algoritmos de recorrido en anchura
  • Simulaciones de sistemas de atención
  • Buffers de comunicación entre procesos

Implementación personalizada simple

using System;
using System.Collections.Generic;

// Implementación simple de una pila usando List<T>
class MiPila<T>
{
    private List<T> elementos = new List<T>();
    
    public void Push(T item)
    {
        elementos.Add(item);
    }
    
    public T Pop()
    {
        if (elementos.Count == 0)
            throw new InvalidOperationException("La pila está vacía");
        
        T item = elementos[elementos.Count - 1];
        elementos.RemoveAt(elementos.Count - 1);
        return item;
    }
    
    public T Peek()
    {
        if (elementos.Count == 0)
            throw new InvalidOperationException("La pila está vacía");
        
        return elementos[elementos.Count - 1];
    }
    
    public int Count => elementos.Count;
}

// Implementación simple de una cola usando List<T>
class MiCola<T>
{
    private List<T> elementos = new List<T>();
    
    public void Enqueue(T item)
    {
        elementos.Add(item);
    }
    
    public T Dequeue()
    {
        if (elementos.Count == 0)
            throw new InvalidOperationException("La cola está vacía");
        
        T item = elementos[0];
        elementos.RemoveAt(0);
        return item;
    }
    
    public T Peek()
    {
        if (elementos.Count == 0)
            throw new InvalidOperationException("La cola está vacía");
        
        return elementos[0];
    }
    
    public int Count => elementos.Count;
}

class Program
{
    static void Main()
    {
        Console.WriteLine("=== Implementaciones personalizadas ===");
        
        // Probar pila personalizada
        MiPila<int> miPila = new MiPila<int>();
        miPila.Push(1);
        miPila.Push(2);
        miPila.Push(3);
        
        Console.WriteLine($"Pila - Tope: {miPila.Peek()}");
        Console.WriteLine($"Pila - Pop: {miPila.Pop()}");
        Console.WriteLine($"Pila - Elementos: {miPila.Count}");
        
        // Probar cola personalizada
        MiCola<string> miCola = new MiCola<string>();
        miCola.Enqueue("Primero");
        miCola.Enqueue("Segundo");
        miCola.Enqueue("Tercero");
        
        Console.WriteLine($"Cola - Frente: {miCola.Peek()}");
        Console.WriteLine($"Cola - Dequeue: {miCola.Dequeue()}");
        Console.WriteLine($"Cola - Elementos: {miCola.Count}");
    }
}

Resumen

Las pilas y colas son estructuras de datos fundamentales que proporcionan formas específicas y eficientes de gestionar colecciones de elementos. Las pilas, con su comportamiento LIFO, son perfectas para operaciones que requieren acceso al elemento más reciente, como sistemas de deshacer o manejo de llamadas a funciones. Las colas, con su comportamiento FIFO, son ideales para procesar elementos en el orden en que llegaron, como sistemas de atención o procesamiento de tareas.

Estas estructuras son la base de muchos algoritmos avanzados y sistemas informáticos. Su comprensión te permitirá diseñar soluciones más elegantes y eficientes para problemas que requieren un control específico sobre el orden de procesamiento de datos. En el siguiente tema exploraremos las estructuras definidas por el usuario con struct, que te permitirán crear tipos de datos personalizados para representar información de manera más organizada.

Volver arriba