Operaciones de una cola con dos pilas
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
Volcar una pila en otra invierte el orden de sus valores. Después de volcar una pila de llegadas, ¿qué valor queda en el tope?
Usa una pila para los valores entrantes y una segunda para atender los pops y peeks. La verdadera pregunta es cuándo volcar de la primera a la segunda.
Vuelca solo cuando la pila de salida está vacía, y entonces pasa todo. Mientras la pila de salida tenga valores, su tope siempre es el valor más antiguo que sigue en la cola.
- Tiempo objetivo
- O(m)
- Espacio objetivo
- O(m)
Restricciones
- O(1) amortized time per operation
- stacks allow only push, pop and top
Solución
Los valores nuevos van a una pila de entrada. Los pops y peeks leen de una pila de salida, y solo cuando la salida está vacía se vuelca en ella toda la entrada, lo que invierte las llegadas para que el más antiguo quede en el tope. Volcar en una pila de salida que todavía tiene valores enterraría valores más antiguos debajo de otros más nuevos, así que la verificación de vacío es lo que mantiene el orden correcto. Cada valor entra y sale de una pila como máximo dos veces, así que m operaciones cuestan O(m) en total, es decir, O(1) amortizado por operación. El espacio es O(n) por los valores guardados.
def run_queue(ops):
inbox, outbox, out = [], [], []
for op in ops:
if op[0] == "push":
inbox.append(op[1])
continue
if not outbox:
while inbox: # reverse once: the oldest ends on top
outbox.append(inbox.pop())
if not outbox:
out.append(None) # the queue is empty
elif op[0] == "pop":
out.append(outbox.pop())
else:
out.append(outbox[-1])
return out
print(run_queue([["push", 1], ["push", 2], ["peek"], ["pop"], ["push", 3], ["pop"], ["pop"]])) # -> [1, 1, 2, 3]
print(run_queue([["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]])) # -> [7, 8]
print(run_queue([["pop"], ["push", 4], ["peek"]])) # -> [None, 4]¿Lo que te frena es la idea y no el código? Cola con dos pilas lo explica.