Justificación: TreeSet es un conjunto (no admite duplicados) implementado sobre un árbol rojo-negro balanceado. Mantiene los elementos siempre ordenados por su orden natural y sus operaciones add, contains y remove son O(log n). Cumple los tres requisitos a la vez.

Por qué las demás NO valen:

• a) ArrayList → permite duplicados (no es Set) y contains es O(n) (búsqueda secuencial), no O(log n).
• b) HashSet → sí impide duplicados y es O(1) de media, pero NO mantiene ningún orden de iteración → incumple el recorrido alfabético.
• c) LinkedList → permite duplicados y contains es O(n). Falla en los tres requisitos.

Tamaño del problema: en (a) y (b) es n; en (c) es el valor de n.

(a) → O(n·log n). Dos bloques seguidos (regla de la suma, queda el dominante). Bloque 1: bucle simple → O(n). Bloque 2: el externo hace j*=2 → da log₂n vueltas; el interno da n vueltas independientes → se multiplican: n·log n. Total O(n) + O(n log n) = O(n log n).

(b) → O(n²). El interno empieza en j = i, así que para cada i da n−i vueltas: n + (n-1) + ... + 1 = n(n+1)/2 ≈ n²/2 → O(n²).

(c) → O(2ⁿ). Es la sucesión de Fibonacci con doble recursión ingenua: cada llamada genera otras dos (m3(n-1) y m3(n-2)), formando un árbol que casi se duplica por nivel → crecimiento exponencial O(2ⁿ) (más finamente O(φⁿ) con φ≈1,618). Lo eficiente sería resolverlo iterativo en O(n). Verificado: m3(0..7) = 1 1 2 3 5 8 13 21 (Fibonacci).

import java.util.Deque;
import java.util.ArrayDeque;

public static boolean equilibrada(String expr) {
    Deque<Character> pila = new ArrayDeque<>();
    for (int i = 0; i < expr.length(); i++) {
        char c = expr.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            pila.push(c);                          // apertura -> apilar
        } else if (c == ')' || c == ']' || c == '}') {
            if (pila.isEmpty()) return false;      // cierre sin apertura
            char tope = pila.pop();
            if ((c == ')' && tope != '(') ||
                (c == ']' && tope != '[') ||
                (c == '}' && tope != '{')) {
                return false;                      // no casan (cruzados)
            }
        }
        // cualquier otro caracter se ignora
    }
    return pila.isEmpty();   // true solo si NO quedan aperturas
}

Por qué una pila: el último símbolo abierto debe ser el primero en cerrarse (anidamiento LIFO); la pila guarda ese «último abierto» en su cima. Complejidad O(n) (una pasada; push/pop O(1)).

Verificado con OpenJDK: {[a+(b-c)]*d}→true, ([)]→false, (((→false, a)→false. ✔

public class ListaDoble {
    private Nodo primero, ultimo;

    // a) insertar al final
    public void insertarFinal(int valor){
        Nodo nuevo = new Nodo(valor);
        if (primero == null){ primero = nuevo; ultimo = nuevo; return; }
        nuevo.anterior = ultimo;
        ultimo.siguiente = nuevo;
        ultimo = nuevo;
    }
    // b) insertar al principio
    public void insertarPrincipio(int valor){
        Nodo nuevo = new Nodo(valor);
        if (primero == null){ primero = nuevo; ultimo = nuevo; return; }
        nuevo.siguiente = primero;
        primero.anterior = nuevo;
        primero = nuevo;
    }
    // c) eliminar el primero cuyo dato coincida
    public boolean eliminar(int valor){
        Nodo actual = primero;
        while (actual != null){
            if (actual.dato == valor){
                if (actual.anterior != null) actual.anterior.siguiente = actual.siguiente;
                else primero = actual.siguiente;          // era el primero
                if (actual.siguiente != null) actual.siguiente.anterior = actual.anterior;
                else ultimo = actual.anterior;            // era el ultimo
                return true;
            }
            actual = actual.siguiente;
        }
        return false;
    }
    // d) imprimir del ultimo al primero
    public void imprimirAlReves(){
        Nodo actual = ultimo;
        while (actual != null){
            System.out.print(actual.dato + " ");
            actual = actual.anterior;     // retrocedo gracias a 'anterior'
        }
        System.out.println();
    }
}

d) Por qué es eficiente: como cada nodo guarda anterior y tenemos ultimo, recorrer hacia atrás es O(n) directo. En una lista simple habría que usar recursión/pila o recorrerla varias veces (O(n²)). Esa es la ventaja principal de la doble enlazada.

Verificado con OpenJDK (insertar 10,20,30 + principio 5; reverso da 30 20 10 5; borrar 20, borrar primero 5 y último 30 recolocan bien primero/ultimo). ✔

public static void quickSort(int[] a, int ini, int fin){
    if (ini >= fin) return;                 // CASO BASE
    int p = particionar(a, ini, fin);       // pivote a su sitio
    quickSort(a, ini, p - 1);               // ordena menores
    quickSort(a, p + 1, fin);               // ordena mayores
}
public static int particionar(int[] a, int ini, int fin){
    int pivote = a[ini];
    int i = ini;
    for (int j = ini + 1; j <= fin; j++)
        if (a[j] < pivote){ i++; intercambiar(a, i, j); }
    intercambiar(a, ini, i);
    return i;
}
private static void intercambiar(int[] a, int x, int y){
    int tmp = a[x]; a[x] = a[y]; a[y] = tmp;
}

b) Traza sobre [40,15,55,10,30,60,20] (pivote = primer elemento de cada trozo):

[40 15 55 10 30 60 20]  pivote=40 -> [20 15 10 30] 40 [60 55]
  [20 15 10 30]         pivote=20 -> [10 15] 20 [30]
    [10 15]             pivote=10 -> 10 [15]         ([15] base)
    [30]  base
  [60 55]               pivote=60 -> [55] 60          ([55] base)

RESULTADO: [10 15 20 30 40 55 60]

c) Complejidad: caso medio O(n log n); peor caso O(n²). El peor caso ocurre cuando el array ya está ordenado (o en orden inverso): el pivote es siempre el mínimo/máximo, una partición queda vacía y la otra con n−1 elementos → n niveles → 1+2+...+n = O(n²).

Verificado con OpenJDK: el array queda [10, 15, 20, 30, 40, 55, 60]. ✔

public class ArbolABB {
    private Nodo raiz;
    public void insertar(int valor){ raiz = insertar(raiz, valor); }
    private Nodo insertar(Nodo actual, int valor){
        if (actual == null) return new Nodo(valor);
        if (valor < actual.dato)      actual.izquierdo = insertar(actual.izquierdo, valor);
        else if (valor > actual.dato) actual.derecho   = insertar(actual.derecho, valor);
        return actual;                     // valor == dato -> duplicado, se ignora
    }
    public boolean contiene(int valor){ return contiene(raiz, valor); }
    private boolean contiene(Nodo actual, int valor){
        if (actual == null) return false;
        if (valor == actual.dato) return true;
        if (valor < actual.dato) return contiene(actual.izquierdo, valor);
        else                     return contiene(actual.derecho, valor);
    }
    public void inorden(){ inorden(raiz); System.out.println(); }
    private void inorden(Nodo actual){
        if (actual == null) return;
        inorden(actual.izquierdo);            // 1) izquierda
        System.out.print(actual.dato + " ");  // 2) raiz (EN MEDIO)
        inorden(actual.derecho);              // 3) derecha
    }
    public int contarHojas(){ return contarHojas(raiz); }
    private int contarHojas(Nodo actual){
        if (actual == null) return 0;
        if (actual.izquierdo == null && actual.derecho == null) return 1;
        return contarHojas(actual.izquierdo) + contarHojas(actual.derecho);
    }
}

b) Complejidad de contiene: equilibrado O(log n); degenerado (forma de lista) O(n). c) Propiedad del inorden: devuelve los valores ordenados de menor a mayor.

e) Insertando 50 30 70 20 40 60 80:

          50
       /      \
     30        70
    /  \      /  \
   20   40   60   80

Inorden (Izq-Raiz-Der):  20 30 40 50 60 70 80
Preorden (Raiz-Izq-Der): 50 30 20 40 70 60 80

Verificado con OpenJDK: inorden = 20 30 40 50 60 70 80, preorden = 50 30 20 40 70 60 80, hojas = 4 (20,40,60,80). ✔

import java.util.*;
import java.util.stream.Collectors;

class Producto {
    private String nombre; private double precio;
    public Producto(String nombre, double precio){ this.nombre=nombre; this.precio=precio; }
    public String getNombre(){ return nombre; }
    public double getPrecio(){ return precio; }
    public String toString(){ return nombre + " (" + precio + "€)"; }
}
public class GestionInventario {
    public static double precioMedio(List<Producto> inv){
        if (inv.isEmpty()) return 0;
        double suma = 0;
        for (Producto p : inv) suma += p.getPrecio();
        return suma / inv.size();
    }
    public static Producto masCaro(List<Producto> inv){
        if (inv.isEmpty()) return null;
        Producto mejor = inv.get(0);
        for (Producto p : inv)
            if (p.getPrecio() > mejor.getPrecio()) mejor = p;
        return mejor;                      // devuelve el OBJETO
    }
    public static List<String> nombresCaros(List<Producto> inv){
        return inv.stream()
                  .filter(p -> p.getPrecio() > 20)
                  .map(Producto::getNombre)
                  .collect(Collectors.toList());
    }
    public static void main(String[] args){
        List<Producto> inv = new ArrayList<>();
        inv.add(new Producto("Teclado", 18.0));
        inv.add(new Producto("Monitor", 120.0));
        inv.add(new Producto("Raton", 25.5));
        System.out.println("Precio medio: " + precioMedio(inv));  // 54.5
        System.out.println("Mas caro: " + masCaro(inv));          // Monitor (120.0EUR)
        System.out.println("Caros (>20): " + nombresCaros(inv));  // [Monitor, Raton]
    }
}

Salida verificada con OpenJDK: Precio medio: 54.5 · Mas caro: Monitor (120.0€) · Caros (>20): [Monitor, Raton]. (Media = (18+120+25.5)/3 = 163.5/3 = 54.5.) ✔

public interface Cola<T> {
    void encolar(T e);
    T desencolar();
    T frente();
    boolean estaVacia();
    int tamano();
}

import java.util.NoSuchElementException;
public class ColaArray<T> implements Cola<T> {
    private Object[] datos;
    private int frente, fin, n;
    public ColaArray(int capacidad){
        if (capacidad <= 0) capacidad = 8;
        datos = new Object[capacidad]; frente = 0; fin = 0; n = 0;
    }
    public void encolar(T e){
        if (n == datos.length) redimensionar(datos.length * 2);
        datos[fin] = e;
        fin = (fin + 1) % datos.length;      // avance circular
        n++;
    }
    @SuppressWarnings("unchecked")
    public T desencolar(){
        if (estaVacia()) throw new NoSuchElementException("Cola vacia");
        T e = (T) datos[frente];
        datos[frente] = null;                // ayuda al recolector
        frente = (frente + 1) % datos.length;
        n--;
        return e;
    }
    @SuppressWarnings("unchecked")
    public T frente(){
        if (estaVacia()) throw new NoSuchElementException("Cola vacia");
        return (T) datos[frente];
    }
    public boolean estaVacia(){ return n == 0; }
    public int tamano(){ return n; }
    private void redimensionar(int nueva){
        Object[] nuevo = new Object[nueva];
        for (int i = 0; i < n; i++)
            nuevo[i] = datos[(frente + i) % datos.length];   // recoloca en orden logico
        datos = nuevo; frente = 0; fin = n;
    }
    public static void main(String[] args){
        Cola<String> c = new ColaArray<>(3);      // tipo = interfaz
        c.encolar("A"); c.encolar("B");
        c.encolar("C"); c.encolar("D");           // el 4o fuerza redimension
        System.out.println("frente = " + c.frente() + ", tamano = " + c.tamano());
        System.out.print("Saliendo (FIFO): ");
        while (!c.estaVacia()) System.out.print(c.desencolar() + " ");
        System.out.println();
    }
}

Salida verificada con OpenJDK: frente = A, tamano = 4 y Saliendo (FIFO): A B C D (sale primero la A: FIFO correcto, la redimensión conservó el orden). Además comprobado que desencolar sobre vacía lanza NoSuchElementException. ✔

e) Programar contra la interfaz → bajo acoplamiento y polimorfismo (cambiar la implementación sin tocar al cliente). Array circular → O(1) amortizado (solo se mueve un índice; la redimensión O(n) ocasional se reparte).

public static void mergeSort(int[] a, int ini, int fin){
    if (ini >= fin) return;               // CASO BASE: 0 o 1 elemento
    int medio = (ini + fin) / 2;
    mergeSort(a, ini, medio);             // mitad izquierda
    mergeSort(a, medio + 1, fin);         // mitad derecha
    mezclar(a, ini, medio, fin);          // fusiona las dos mitades
}
public static void mezclar(int[] a, int ini, int medio, int fin){
    int[] aux = new int[fin - ini + 1];
    int i = ini, j = medio + 1, k = 0;
    while (i <= medio && j <= fin){
        if (a[i] <= a[j]) aux[k++] = a[i++];   // "<=" hace el algoritmo ESTABLE
        else              aux[k++] = a[j++];
    }
    while (i <= medio) aux[k++] = a[i++];
    while (j <= fin)   aux[k++] = a[j++];
    for (int p = 0; p < aux.length; p++)
        a[ini + p] = aux[p];
}

b) Traza sobre [40,15,55,10,30,60,20]. División (medio=(0+6)/2=3):

[40 15 55 10 30 60 20]  -> [40 15 55 10] y [30 60 20]
 [40 15 55 10] -> [40 15] y [55 10]  -> [40][15] [55][10]
 [30 60 20]    -> [30 60] y [20]     -> [30][60] [20]

Mezclas (de abajo a arriba), estado del array completo:
 [0..1] 40,15 -> [15,40]           15 40 55 10 30 60 20
 [2..3] 55,10 -> [10,55]           15 40 10 55 30 60 20
 [0..3] mezcla -> [10,15,40,55]    10 15 40 55 30 60 20
 [4..5] 30,60 -> [30,60]           10 15 40 55 30 60 20
 [4..6] mezcla -> [20,30,60]       10 15 40 55 20 30 60
 [0..6] mezcla -> [10..60]         10 15 20 30 40 55 60

c) Complejidad: O(n log n) en mejor, medio y peor caso; espacial O(n) (array auxiliar). Siempre O(n log n) porque parte exactamente por la mitad (altura log n independiente de los datos). Estable: iguales conservan su orden relativo, garantizado por a[i] <= a[j].

Verificado con OpenJDK: resultado [10, 15, 20, 30, 40, 55, 60]. ✔

a) f1 → O(n²) (O(n) + doble bucle n·n). f2 → O(log n) (i=i/2 desde n hasta 0 → log₂n vueltas). f3 → O(n²) (interno j<i → 0+1+...+(n-1)=n(n-1)/2).

b) Búsqueda binaria completada → O(log n):

public static int busquedaBinaria(int[] a, int clave){
    int ini = 0, fin = a.length - 1;
    while (ini <= fin){                        // (1) <=
        int medio = ini + (fin - ini) / 2;
        if (a[medio] == clave) return medio;       // (2) medio
        else if (a[medio] < clave) ini = medio + 1;// (3) medio + 1
        else fin = medio - 1;                      // (4) medio - 1
    }
    return -1;
}

c) sumaFilas → O(n²):

public static int[] sumaFilas(int[][] m){
    int n = m.length;
    int[] r = new int[n];
    for (int i = 0; i < n; i++){        // n filas
        int s = 0;
        for (int j = 0; j < n; j++)     // n columnas por fila
            s += m[i][j];
        r[i] = s;
    }
    return r;
}

Verificado con OpenJDK: sobre [2,5,8,12,16,23,38,56,72,91], busquedaBinaria(a,23)=5 y busquedaBinaria(a,17)=-1; sumaFilas({{1,2,3},{4,5,6},{7,8,9}})=[6,15,24]. ✔

class NodoP {
    int dato; NodoP siguiente;
    NodoP(int dato){ this.dato = dato; }
}
public class PilaEnlazada {
    private NodoP cima;   // tope
    private int n;
    public void apilar(int v){            // a) inserta por la CABEZA -> O(1)
        NodoP nuevo = new NodoP(v);
        nuevo.siguiente = cima;
        cima = nuevo;
        n++;
    }
    public int desapilar(){               // b)
        if (cima == null) throw new RuntimeException("Pila vacia");
        int v = cima.dato;
        cima = cima.siguiente;
        n--;
        return v;
    }
    public int cima(){                    // c)
        if (cima == null) throw new RuntimeException("Pila vacia");
        return cima.dato;
    }
    public boolean estaVacia(){ return cima == null; }   // d)
    public int tamano(){ return n; }                      // d)
    public static String invertir(String s){              // e)
        PilaEnlazada p = new PilaEnlazada();
        for (int i = 0; i < s.length(); i++) p.apilar(s.charAt(i));
        StringBuilder sb = new StringBuilder();
        while (!p.estaVacia()) sb.append((char) p.desapilar());
        return sb.toString();
    }
    public static void main(String[] args){
        PilaEnlazada p = new PilaEnlazada();
        p.apilar(1); p.apilar(2); p.apilar(3);
        System.out.print("LIFO: cima=" + p.cima() + " -> ");
        while (!p.estaVacia()) System.out.print(p.desapilar() + " ");
        System.out.println("
invertir("Java") = " + invertir("Java"));
    }
}

Salida verificada con OpenJDK: LIFO: cima=3 -> 3 2 1 (sale primero el último apilado) y invertir("Java") = avaJ. ✔

f) apilar/desapilar tocan solo la cabeza → O(1). La pila es natural para deshacer/invertir por su orden LIFO: lo último en entrar es lo primero en salir.

// a) exponenciacion rapida -> O(log exp)
public static long potencia(long base, int exp){
    if (exp == 0) return 1;                 // CASO BASE
    long mitad = potencia(base, exp / 2);   // una sola llamada recursiva
    if (exp % 2 == 0) return mitad * mitad;         // par
    else              return base * mitad * mitad;  // impar
}
// b) suma de digitos
public static int sumaDigitos(int n){
    n = Math.abs(n);
    if (n < 10) return n;                   // CASO BASE: un digito
    return n % 10 + sumaDigitos(n / 10);    // ultimo digito + resto
}
// c) palindromo por los extremos
public static boolean esPalindromo(String s, int ini, int fin){
    if (ini >= fin) return true;                  // CASO BASE: se cruzaron
    if (s.charAt(ini) != s.charAt(fin)) return false;
    return esPalindromo(s, ini + 1, fin - 1);     // avanza al centro
}
// llamada: esPalindromo("reconocer", 0, "reconocer".length()-1)

d) Traza de potencia(2,10) = 1024 (solo 5 llamadas, no 10):

potencia(2,10) par   -> m*m    con m=potencia(2,5)
potencia(2,5)  impar -> 2*m*m  con m=potencia(2,2)
potencia(2,2)  par   -> m*m    con m=potencia(2,1)
potencia(2,1)  impar -> 2*m*m  con m=potencia(2,0)
potencia(2,0)        -> 1      (caso base)

Vuelta:
 potencia(2,0)=1
 potencia(2,1)=2*1*1 = 2
 potencia(2,2)=2*2   = 4
 potencia(2,5)=2*4*4 = 32
 potencia(2,10)=32*32= 1024  <-

Verificado con OpenJDK: potencia(2,10)=1024, potencia(3,4)=81; sumaDigitos(9876)=30; esPalindromo("reconocer")=true, esPalindromo("java")=false. ✔

public interface Conjunto<T> {
    boolean anadir(T e);     // true si NO estaba
    boolean contiene(T e);
    boolean eliminar(T e);   // true si estaba y se quito
    int     tamano();
    boolean estaVacio();
}

class NodoC<T> { T dato; NodoC<T> siguiente; NodoC(T dato){ this.dato = dato; } }

public class ConjuntoLista<T> implements Conjunto<T> {
    private NodoC<T> primero;
    private int n;
    public boolean anadir(T e){
        if (contiene(e)) return false;          // sin duplicados
        NodoC<T> nuevo = new NodoC<>(e);
        nuevo.siguiente = primero;              // insercion por la cabeza -> O(1)
        primero = nuevo; n++;
        return true;
    }
    public boolean contiene(T e){
        NodoC<T> act = primero;
        while (act != null){
            if (act.dato.equals(e)) return true;   // equals, no ==
            act = act.siguiente;
        }
        return false;
    }
    public boolean eliminar(T e){
        NodoC<T> act = primero, ant = null;
        while (act != null){
            if (act.dato.equals(e)){
                if (ant == null) primero = act.siguiente;   // era el PRIMERO
                else ant.siguiente = act.siguiente;
                n--; return true;
            }
            ant = act; act = act.siguiente;
        }
        return false;
    }
    public int tamano(){ return n; }
    public boolean estaVacio(){ return n == 0; }

    public static void main(String[] args){
        Conjunto<String> c = new ConjuntoLista<>();   // tipo = interfaz
        System.out.println(c.anadir("rojo"));    // true
        System.out.println(c.anadir("verde"));   // true
        System.out.println(c.anadir("rojo"));    // false (duplicado)
        System.out.println(c.contiene("verde")); // true
        System.out.println(c.tamano());          // 2
        System.out.println(c.eliminar("rojo"));  // true
        System.out.println(c.eliminar("azul"));  // false
        System.out.println(c.tamano());          // 1
        System.out.println(c.estaVacio());       // false
    }
}

Salida verificada con OpenJDK: true, true, false, true, 2, true, false, 1, false. ✔

e) La interfaz permite cambiar la implementación (p.ej. a HashSet) sin tocar al cliente. Complejidad con lista: contiene, anadir y eliminar son O(n) (hay que recorrer); un HashSet las haría O(1).

public static void insertionSort(int[] a){
    for (int i = 1; i < a.length; i++){
        int clave = a[i];             // elemento a insertar
        int j = i - 1;
        while (j >= 0 && a[j] > clave){   // desplaza los mayores
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = clave;             // hueco donde entra la clave
    }
}

b) Traza sobre [29,10,14,37,13,25] (estado al final de cada i):

inicial       -> [29, 10, 14, 37, 13, 25]
i=1 clave=10  -> [10, 29, 14, 37, 13, 25]
i=2 clave=14  -> [10, 14, 29, 37, 13, 25]
i=3 clave=37  -> [10, 14, 29, 37, 13, 25]   (37 ya es mayor, el while no entra)
i=4 clave=13  -> [10, 13, 14, 29, 37, 25]   (13 baja hasta la posicion 1)
i=5 clave=25  -> [10, 13, 14, 25, 29, 37]
final         -> [10, 13, 14, 25, 29, 37]

c) Complejidad: mejor (ya ordenado) O(n); peor (al revés) O(n²); medio O(n²); espacial O(1) (in situ). Estable por la condición a[j] > clave (los iguales no se mueven).

Traza verificada con OpenJDK (coincide exactamente con la tabla). ✔

a) f1 → O(n·log n) (externo i*3 → log₃n vueltas × interno n). f2 → O(n) (es el factorial: una llamada por nivel hasta n≤1). f3 → O(n·log n) (bloque1 O(n) + bloque2 n×log₂n; domina el segundo).

b) Búsqueda lineal completada:

public static int busquedaLineal(int[] a, int clave){
    for (int i = 0; i < a.length; i++){    // (1) <
        if (a[i] == clave) return i;       // (2) ==   (3) i
    }
    return -1;                             // (4) -1
}

Complejidad: mejor caso O(1) (clave en posición 0); peor caso O(n) (al final o no está). No requiere array ordenado.

c) maxPorColumna → O(n²):

public static int[] maxPorColumna(int[][] m){
    int n = m.length;
    int[] res = new int[n];
    for (int col = 0; col < n; col++){
        int max = m[0][col];               // primer elemento de la columna
        for (int fila = 1; fila < n; fila++)
            if (m[fila][col] > max) max = m[fila][col];
        res[col] = max;
    }
    return res;
}

Verificado con OpenJDK: con {{1,9,4},{7,2,8},{3,5,6}} devuelve [7, 9, 8]; f1(27)=81=3·27 y f1(81)=324=4·81 (confirma n·log₃n); fact(5)=120. ✔

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;

public class ColaDosPilas<T> {
    private Deque<T> entrada = new ArrayDeque<>();   // se apila al encolar
    private Deque<T> salida  = new ArrayDeque<>();   // se saca al desencolar

    public void encolar(T e){ entrada.push(e); }     // a)

    private void trasvasar(){                          // SOLO si salida vacia
        if (salida.isEmpty()){
            while (!entrada.isEmpty())
                salida.push(entrada.pop());            // el mas antiguo queda arriba
        }
    }
    public T desencolar(){                             // b)
        trasvasar();
        if (salida.isEmpty()) throw new NoSuchElementException("cola vacia");
        return salida.pop();
    }
    public T frente(){                                 // c)
        trasvasar();
        if (salida.isEmpty()) throw new NoSuchElementException("cola vacia");
        return salida.peek();
    }
    public boolean estaVacia(){ return entrada.isEmpty() && salida.isEmpty(); }  // d)
    public int tamano(){ return entrada.size() + salida.size(); }               // d)

    public static void main(String[] args){            // e)
        ColaDosPilas<Integer> c = new ColaDosPilas<>();
        c.encolar(1); c.encolar(2); c.encolar(3);
        System.out.println(c.frente());     // 1
        System.out.println(c.desencolar()); // 1
        c.encolar(4);
        System.out.println(c.desencolar()); // 2
        System.out.println(c.desencolar()); // 3
        System.out.println(c.desencolar()); // 4
        System.out.println(c.estaVacia());  // true
    }
}

Salida verificada con OpenJDK: 1, 1, 2, 3, 4, true. El caso interesante: encolar 4 después de trasvasar 2,3 a salida → el 4 se queda en entrada y no se mezcla; sale respetando 1,2,3,4. ✔

f) Un desencolar puntual puede costar O(n) (trasvase completo), pero cada elemento se apila/desapila un número constante de veces en toda su vida (máx. 4 operaciones O(1)) → coste amortizado O(1).

// a) Torres de Hanoi
public static void hanoi(int n, char origen, char aux, char destino){
    if (n == 1){                                    // CASO BASE
        System.out.println("mover disco 1 de " + origen + " a " + destino);
        return;
    }
    hanoi(n - 1, origen, destino, aux);             // 1) subtorre n-1 a auxiliar
    System.out.println("mover disco " + n + " de " + origen + " a " + destino);
    hanoi(n - 1, aux, origen, destino);             // 3) subtorre n-1 al destino
}
// b) Maximo comun divisor (Euclides)
public static int mcd(int a, int b){
    if (b == 0) return a;          // CASO BASE
    return mcd(b, a % b);          // CASO RECURSIVO
}
// c) Inversion in-place recursiva
public static void invertir(int[] a, int ini, int fin){
    if (ini >= fin) return;        // CASO BASE
    int t = a[ini]; a[ini] = a[fin]; a[fin] = t;   // intercambia extremos
    invertir(a, ini + 1, fin - 1); // avanza al centro
}

d) Traza de hanoi(3,'A','B','C') — 7 movimientos:

1: mover disco 1 de A a C
2: mover disco 2 de A a B
3: mover disco 1 de C a B
4: mover disco 3 de A a C
5: mover disco 1 de B a A
6: mover disco 2 de B a C
7: mover disco 1 de A a C   -> total = 2^3 - 1 = 7

mcd(48,36) a mano: mcd(48,36) → mcd(36,12) → mcd(12,0) → 12. invertir({1,2,3,4,5}, 0, 4) → [5,4,3,2,1] (intercambios 1↔5, 2↔4, el 3 queda fijo).

Verificado con OpenJDK: Hanói imprime esos 7 movimientos exactos; mcd(48,36)=12 y mcd(1071,462)=21; invertir da [5, 4, 3, 2, 1]. ✔