Facundo Uferer
🇦🇷 🇺🇸
Contact

Part of: Java for Beginners › The Stack and Queue ADTs: Linear Structures

Linear Data Structures

Stack ADT (LIFO) and Queue ADT (FIFO) in Java

1 of 6
Slide 1 / 6 • LIFO Discipline

Stack ADT (LIFO): Last-In, First-Out Access

In a stack you can only interact with the top. Elements are placed on top and are the first to be popped out.

Simulador Visual de Pila (LIFO) Capacidad: 5 / En uso: 3
↓ top
30 Top Element
20
10
Tope actual 30
Tamaño (size) 3
¿Está vacía? false
Acción: Estado inicial cargado con [10, 20, 30]. Tope en 30.

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

Queue ADT (FIFO): First-In, First-Out Discipline

In a fair queue, elements enter at the rear (tail) and are served or removed from the front (head).

Tubería Horizontal FIFO Capacidad: 6 / En uso: 3
← front (Salida / poll) Entrada (offer) ← rear
"Ana" Head
"Beto"
"Caro" Tail
Próximo a salir "Ana"
Último ingresado "Caro"
Tamaño 3
Cola lista. "Ana" es atendida primero por ser la primera en llegar (FIFO).

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

Circular Queue on Arrays: Modular Arithmetic

A linear array wastes slots when dequeuing. The circular queue wraps indices around using: (rear + 1) % capacity.

Anillo de 8 Celdas (Índices 0 a 7) fin = 2 | frente = 0
Aritmética Modular (fin + 1) % 8 Índice: 2 → 3 A [0] B [1] C [2] — [3] — [4] — [5] — [6] — [7]
El índice de fin avanza en sentido horario. Al llegar a 7, la operación (7 + 1) % 8 regresa suavemente a 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

Stacks and Queues in Real Software Architecture

Where these structures live across everyday production platforms and runtime environments.

🥞

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

Balanced Expression Validator using a Stack

Validating delimiters (), [], {} by pushing openings and checking matching closures against stack top.

Validador Paso a Paso de Expresiones En espera
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

Discrete-Event Simulation: Dual Service Queues

Modeling concurrent service desks with fast and standard customer queues over simulated ticks.

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
Sistema en tiempo cero. Agrega clientes o avanza el reloj para simular llegadas y atenciones.

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.