Implementar una cola con dos pilas da, ¿qué coste por operación?
Opciones
- O(n) cada una
- O(1) amortizado (Opción correcta)
- O(log n)
- O(n²) en total
Respuesta
O(1) amortizado
Por qué
Apila los elementos nuevos en la pila in. Para desencolar, saca de la pila out; si out está vacía, primero mueve todo de in a out, lo que invierte el orden y deja el más antiguo arriba.
Un solo movimiento puede ser caro, pero cada elemento se mueve como mucho una vez en su vida. Repartido entre todas las operaciones, el coste medio es O(1): eso es O(1) 'amortizado'.
Recuerda
Cada elemento se mueve una vez → O(1) amortizado.