TAD Pila (LIFO) y TAD Cola (FIFO) en Java

Slide 1 / 6 • LIFO Discipline

TAD Pila (LIFO): Disciplina Último en Entrar, Primero en Salir

En una pila solo se puede interactuar con el extremo superior ("tope"). Todo elemento insertado se apila sobre el anterior y es el primero en ser desapilado.

Simulador Visual de Pila (LIFO) Capacidad: 5 / En uso: 3

↓ tope

30 Top Element

20

10

Tope actual 30

Tamaño (size) 3

¿Está vacía? false

Anatomía y Contrato en Java

// Contrato del TAD Pila
public interface Pila<T> {
    void push(T elemento);  // O(1)
    T pop();                // O(1)
    T peek();               // O(1)
    boolean isEmpty();      // O(1)
    int size();             // O(1)
}

// Ejemplo de uso:
Pila<Integer> p = new PilaEnlazada<>();
p.push(10);
p.push(20);
p.push(30);
int x = p.pop(); // Retorna 30 (LIFO)

Regla de oro: Una pila prohíbe el acceso por índice arbitrario (`p.get(1)` es ilegal). Esto garantiza que el último estado registrado siempre sea recuperado de forma predecible e instantánea.

Slide 2 / 6 • FIFO Discipline

TAD Cola (FIFO): Disciplina Primero en Entrar, Primero en Salir

En una cola honesta, los elementos ingresan por la parte trasera (fin / tail) y se atienden o extraen por el frente (head).

Tubería Horizontal FIFO Capacidad: 6 / En uso: 3

← frente (Salida / poll) Entrada (offer) ← fin

"Ana" Head

"Beto"

"Caro" Tail

Próximo a salir "Ana"

Último ingresado "Caro"

Tamaño 3

El Principio de Equidad (Fairness)

// Contrato del TAD Cola
public interface Cola<T> {
    boolean offer(T elemento); // encolar al final O(1)
    T poll();                  // extraer del frente O(1)
    T peek();                  // consultar frente O(1)
    boolean isEmpty();         // O(1)
    int size();                // O(1)
}

// Disciplina en acción:
Cola<String> c = new ColaEnlazada<>();
c.offer("Ana");
c.offer("Beto");
c.offer("Caro");
String atendido = c.poll(); // Retorna "Ana"

Complejidad constante: Tanto encolar como desencolar deben resolverse en $O(1)$. En una lista enlazada mantenemos punteros `frente` y `fin`. En un array se requiere una cola circular.

Slide 3 / 6 • Circular Buffer

Cola Circular sobre Array: La Aritmética Modular

Un array lineal desperdicia espacio al desencolar. La cola circular reutiliza celdas conectando el índice final con el inicial mediante la fórmula: (fin + 1) % capacidad.

Anillo de 8 Celdas (Índices 0 a 7) fin = 2 | frente = 0

¿Por qué el operador módulo (%)?

En un arreglo lineal sin ciclo:

[0] Desperdiciado

[1] Desperdiciado

[2] Frente

[3] Fin

Si no reciclamos las celdas [0] y [1], tendríamos que mover todos los elementos $O(N)$ o agotar el arreglo prematuramente.

// Inserción en Cola Circular:
fin = (fin + 1) % capacidad;
elementos[fin] = item;
size++;

// Extracción:
T item = elementos[frente];
frente = (frente + 1) % capacidad;
size--;

Slide 4 / 6 • Systems Architecture

Pilas y Colas en la Arquitectura de Software Real

Dónde residen estas estructuras en los sistemas productivos que usamos todos los días.

🥞

La Pila en Sistemas Reales

Call Stack de la JVM: Cada llamada a método crea un registro de activación (Stack Frame) con sus variables locales y dirección de retorno. Al retornar, el frame se desapila.
Deshacer / Rehacer (Undo / Redo): Dos pilas acopladas. Cada acción realizada se empuja en la pila `undoStack`. Al presionar Ctrl+Z, se desapila y se pasa a `redoStack`.
Evaluación de Expresiones Postfijas: Conversión de notación infija `(a+b)*c` a postfija `ab+c*` y resolución con una pila de operandos.
Algoritmo DFS (Búsqueda en Profundidad): Recorrido de grafos o árboles explorando ramas hasta el fondo antes de retroceder (backtracking).

🎟

La Cola en Sistemas Reales

Brokers de Mensajería (Kafka, RabbitMQ, SQS): Productores publican eventos en la cola sin bloquearse; consumidores procesan los mensajes en estricto orden de arribo.
Spooler de Impresión del Sistema Operativo: Si 10 usuarios envían documentos al mismo tiempo a una impresora, los trabajos se encolan y despachan secuencialmente.
Buffer de Paquetes en Routers: Almacena paquetes TCP/UDP cuando el ancho de banda del enlace está saturado momentáneamente.
Algoritmo BFS (Búsqueda en Amplitud): Exploración de grafos nivel por nivel usando una cola para visitar nodos vecinos contiguos.

Slide 5 / 6 • Classic Algorithm

Algoritmo de Expresiones Balanceadas con Pila

Verificación de delimitadores (), [], {} mediante apilado de aperturas y validación estricta al encontrar un cierre.

Validador Paso a Paso de Expresiones En espera

Seleccionar caso de prueba:

Tira de Caracteres (Lectura Izq → Der):

Pila de Aperturas:

Vacia

Explicación del Paso:

Selecciona una expresión y presiona "Paso Siguiente" para iniciar la lectura.

Algoritmo en Pseudocódigo Java

public boolean estaBalanceada(String s) {
    Pila<Character> p = new PilaEnlazada<>();
    
    for (char c : s.toCharArray()) {
        // Si es apertura, apilar
        if (c == '(' || c == '[' || c == '{') {
            p.push(c);
        } 
        // Si es cierre, verificar tope
        else if (c == ')' || c == ']' || c == '}') {
            if (p.isEmpty()) return false;
            char tope = p.pop();
            if (!coinciden(tope, c)) return false;
        }
    }
    // Si la pila quedó vacía, está bien
    return p.isEmpty();
}

Complejidad Óptima: Tiempo $O(N)$ porque cada caracter se procesa una única vez. Espacio $O(N)$ en el peor caso (cuando la mitad de los símbolos son aperturas).

Slide 6 / 6 • Discrete-Event Simulation

Simulación de Eventos Discretos: Dos Colas de Atención

Modelado de un sistema de atención concurrente con cola rápida y cola general avanzando en el tiempo simulado.

Centro de Atención: Dos Ventanillas Concurrentes Reloj: T = 0 seg

Caja 1: Atención Rápida (≤ 2 trámites) Libre

🧑‍💼 Esperando

Caja 2: Atención General (Trámites largos) Libre

👩‍💼 Esperando

Clientes Atendidos 0

Espera Promedio 0.0 s

En Cola Total 0

Modelado con Colas Múltiples

Las simulaciones de eventos discretos utilizan colas para responder preguntas cruciales de negocio y capacidad:

¿Cuántas ventanillas se necesitan para que la espera no supere los 5 minutos?
¿Es más eficiente una fila única con múltiples cajeros o filas separadas por cada caja?
¿Cómo impacta la variabilidad del tiempo de servicio en la acumulación de clientes?

Teoría de Colas: Demuestra matemáticamente que cuando la tasa de llegada ($\lambda$) se acerca a la tasa de servicio ($\mu$), el tamaño de la cola y el tiempo de espera crecen exponencialmente hacia el infinito.