Se requiere implementar una estructura de datos tipo cola que soporte tres operaciones:

• enqueue(v): inserta un valor al final de la cola.
• dequeue(): elimina y devuelve el elemento en el frente de la cola.
• max(): devuelve el valor máximo actual en la cola.

El objetivo es minimizar la complejidad temporal de la operación max(), idealmente a O(1).

Enfoque basado en dos pilas

Una solución eficaz consiste en representar la cola mediante dos pilas: entrada y salida. La operación enqueue se realiza sobre la pila entrada, mientras que dequeue consume elementos de la pila salida. Si salida está vacía, se transfieren todos los elementos de entrada a salida (invirtiendo su orden).

Para mantener el máximo en tiempo constante, cada pila debe ser capaz de reportar su valor máximo actual en O(1). Esto se logra modificando la implementación de la pila para rastrear dinámicamenet el máximo durante las operaciones de inserción y eliminación.

Implementación de la pila con seguimiento del máximo

Cada pila mantiene un arreglo adicional que registra, para cada posición, el índicee del máximo anterior. Al insertar un nuevo elemento, si este supera al máximo actual, se actualiza el puntero al nuevo máximo y se guarda el anterior. Al eliminar, si el elemento retirado era el máximo, se restaura el máximo previo usendo el registro guardado.

class MaxStack {
    private static final int CAPACITY = 20;
    private int[] values = new int[CAPACITY];
    private int[] prevMaxIndex = new int[CAPACITY];
    private int top = -1;
    private int maxIdx = -1;

    public void push(int value) {
        if (top + 1 >= CAPACITY) throw new RuntimeException("Capacidad excedida");
        top++;
        values[top] = value;
        if (maxIdx == -1 || value > values[maxIdx]) {
            prevMaxIndex[top] = maxIdx;
            maxIdx = top;
        } else {
            prevMaxIndex[top] = -1;
        }
    }

    public int pop() {
        if (top == -1) throw new RuntimeException("Pila vacía");
        int val = values[top];
        if (top == maxIdx) {
            maxIdx = prevMaxIndex[top];
        }
        top--;
        return val;
    }

    public int getMax() {
        return maxIdx == -1 ? Integer.MIN_VALUE : values[maxIdx];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

Implementación de la cola usando dos pilas con máximo

class MaxQueue {
    private MaxStack entrada = new MaxStack();
    private MaxStack salida = new MaxStack();

    public void enqueue(int value) {
        entrada.push(value);
    }

    public int dequeue() {
        if (salida.isEmpty()) {
            while (!entrada.isEmpty()) {
                salida.push(entrada.pop());
            }
        }
        return salida.pop();
    }

    public int max() {
        int maxEntrada = entrada.getMax();
        int maxSalida = salida.getMax();
        return Math.max(maxEntrada, maxSalida);
    }

    public boolean isEmpty() {
        return entrada.isEmpty() && salida.isEmpty();
    }
}

Ejemplo de uso

public class Main {
    public static void main(String[] args) {
        MaxQueue q = new MaxQueue();
        q.enqueue(6);
        q.enqueue(1);
        q.enqueue(9);
        q.enqueue(7);
        q.enqueue(4);
        q.enqueue(5);
        q.enqueue(0);
        q.enqueue(2);

        while (!q.isEmpty()) {
            System.out.println("Máximo actual: " + q.max() + ", Elemento extraído: " + q.dequeue());
        }
    }
}

Salida esperada:

Máximo actual: 9, Elemento extraído: 6
Máximo actual: 9, Elemento extraído: 1
Máximo actual: 9, Elemento extraído: 9
Máximo actual: 7, Elemento extraído: 7
Máximo actual: 5, Elemento extraído: 4
Máximo actual: 5, Elemento extraído: 5
Máximo actual: 2, Elemento extraído: 0
Máximo actual: 2, Elemento extraído: 2