Saltar al contenido

Operaciones de una cola con dos pilas

Fácil#two-stacks#amortized~15 min

La misión

Problema

Construye una cola (queue) de tipo primero en entrar, primero en salir a partir de dos pilas (stacks), usando solo push al tope, pop del tope y lectura del tope. Procesa una lista de operaciones: ["push", x] agrega x, ["pop"] quita e informa el valor más antiguo, y ["peek"] lo informa sin quitarlo. Devuelve los valores informados en orden, e informa None cuando pop o peek encuentran la cola vacía. Cada operación debe costar O(1) de tiempo amortizado.

Ejemplos

Input:  ops = [["push", 1], ["push", 2], ["peek"], ["pop"],
               ["push", 3], ["pop"], ["pop"]]
Output: [1, 1, 2, 3]
Por qué: los valores salen en el orden en que llegaron
Input:  ops = [["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]]
Output: [7, 8]
Por qué: después de que sale el 7, el 8 es el valor más antiguo que queda
Input:  ops = [["pop"], ["push", 4], ["peek"]]
Output: [None, 4]
Por qué: caso límite: hacer pop en una cola vacía informa None

Pistas

0 / 3

Tiempo objetivo
O(m)
Espacio objetivo
O(m)

Restricciones

  • O(1) amortized time per operation
  • stacks allow only push, pop and top

¿Lo que te frena es la idea y no el código? Cola con dos pilas lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio