Implement Queue Using Stacks

+10

Construye una cola de primero en entrar, primero en salir cuyo único almacenamiento sean dos pilas. Una pila solo puede añadir un elemento en la parte superior, quitar el elemento superior, leer el elemento superior e indicar si está vacía. La cola admite push x (añadir x al final), pop (quitar y devolver el elemento del frente), peek (devolver el elemento del frente) y empty (¿está vacía la cola?).

Recibes las operaciones en orden como ops, con args[i] que contiene el valor para una operación push y 0 para cualquier otra operación. Ejecútalas en una única cola que empieza vacía y devuelve una cadena por operación: "null" para una operación push, el número como texto para una operación pop o peek, y "true" o "false" para empty.

Función

queueOps(ops: string-array, args: integer-array) → string-array

opsstring-array: las operaciones, en el orden en que se ejecutan
argsinteger-array: el valor para cada operación push, 0 para todas las demás operaciones
Devuelvestring-array: una respuesta por operación, como texto

Restricciones

1 ≤ ops.length ≤ 2000
args.length == ops.length
Cada ops[i] es push, pop, peek o empty.
-10⁹ ≤ args[i] ≤ 10⁹ para una inserción, y args[i] == 0 para cualquier otra operación.
pop y peek solo se llaman cuando la cola contiene al menos un elemento.

Ejemplos

Entrada: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Salida: ["null", "null", "1", "1", "false"]
Explicación: Después de insertar 1 y después 2, el frente es 1, así que peek y pop devuelven "1". El 2 sigue dentro, así que empty devuelve "false".

Entrada: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Salida: ["null", "null", "4", "null", "7", "9", "true"]
Explicación: El primer pop devuelve 4, el elemento más antiguo. 9 llega mientras 7 todavía está esperando y sale después de 7 porque llegó después. Entonces la cola está vacía, así que la última respuesta es "true".

Entrada: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Salida: ["true", "null", "-3", "-3", "true"]
Explicación: La cola empieza vacía, así que la primera respuesta es "true". Un número negativo se almacena como cualquier otro: tanto peek como pop devuelven "-3", y después la cola vuelve a estar vacía.

+15 pruebas ocultas al enviar

Para ir más allá

¿Cómo añadirías una operación back que devuelva el elemento más reciente en O(1), sin romper el límite amortizado de las demás operaciones?

Solución

Una pila devuelve los elementos en el orden inverso al que llegaron, y una cola, en el mismo orden. Verter una pila en una segunda pila la invierte una vez más, lo que convierte el orden de pila en el orden de cola. La cuestión es cuándo verter: hacerlo en cada operación cuesta O(n) cada vez, mientras que verter solo cuando se vacía la segunda pila hace que cada elemento se mueva de una pila a otra una sola vez.

Reordena toda la pila en cada inserción

Intuición

Mantén todos los elementos en una sola pila, main, ordenados de modo que el elemento más antiguo quede arriba. Después, pop, peek y empty son operaciones de pila simples.

El trabajo pasa a push. Un elemento nuevo va al fondo, debajo de todo lo que ya está esperando, y una pila solo puede añadir elementos arriba. Así que mueve todos los elementos de main a la segunda pila, helper, apila el elemento nuevo en la main vacía y vuelve a moverlo todo. Cada movimiento invierte el orden; dos movimientos lo restauran, y el elemento nuevo termina debajo.

Esto es correcto, pero cada operación de apilado toca dos veces todos los elementos almacenados. Apilar 1.000 elementos seguidos cuesta aproximadamente 2 × (0 + 1 + ... + 999), cerca de un millón de movimientos, cuando una cola real necesita 1.000 pasos.

Algoritmo

Mantén dos pilas: main, con el elemento más antiguo en la parte superior, y una helper vacía.
Para push x: saca todos los elementos de main y colócalos en helper, coloca x en main y después saca todos los elementos de helper y colócalos de nuevo en main.
Para pop y peek: saca o lee el elemento superior de main.
Para empty: indica si main está vacía.
Registra cada respuesta como texto y devuelve la lista.

class TwoStackQueue:
    def __init__(self):
        self.main = []    # the oldest item is on top
        self.helper = []

    def push(self, x):
        # Move everything aside, put x at the bottom, move everything back.
        while self.main:
            self.helper.append(self.main.pop())
        self.main.append(x)
        while self.helper:
            self.main.append(self.helper.pop())

    def pop(self):
        return self.main.pop()

    def peek(self):
        return self.main[-1]

    def empty(self):
        return not self.main


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

Pilas de entrada y salida con transferencia diferida

Intuición

Asigna tareas distintas a las pilas. Cada inserción se realiza en inbox, en O(1). Las extracciones y las consultas del elemento superior leen de outbox, cuyo elemento superior siempre es el elemento más antiguo de la cola.

Cuando outbox está vacío y se solicita una extracción o una consulta del elemento superior, vierte todo el contenido de inbox en él. El elemento más nuevo sale primero de inbox, así que queda en el fondo de outbox, y el más antiguo queda arriba. Vierte el contenido solo cuando outbox está vacío: mientras todavía contenga elementos, estos son más antiguos que cualquier elemento de inbox, así que deben salir primero. En el segundo ejemplo, 4 y 7 se vierten para la primera extracción; 9 espera entonces en inbox hasta que 7 haya salido.

Una sola extracción puede mover muchos elementos, pero cuenta el trabajo por elemento: cada valor se inserta en inbox una vez, se mueve a outbox una vez y se extrae una vez. Por lo tanto, n operaciones cuestan O(n) en total, lo que equivale a O(1) amortizado por operación. La cola está vacía cuando ambas pilas están vacías.

Algoritmo

Mantén dos pilas vacías, inbox y outbox.
Para push x: inserta x en inbox.
Para pop o peek: si outbox está vacía, extrae cada elemento de inbox y lo inserta en outbox. Después, extrae o lee la parte superior de outbox.
Para empty: indica si ambas pilas están vacías.
Registra cada respuesta como texto y devuelve la lista.

class TwoStackQueue:
    def __init__(self):
        self.inbox = []    # new items go on top
        self.outbox = []   # the oldest item is on top

    def push(self, x):
        self.inbox.append(x)

    def _refill(self):
        # Only when the outbox is empty: pouring the inbox over reverses it,
        # so the oldest item lands on top.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._refill()
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

Errores comunes y casos límite

La mayoría de los errores se deben a verter los elementos en el momento equivocado o a revisar solo una pila.

Verter inbox en outbox mientras outbox todavía contiene elementos. Los nuevos elementos quedan encima de los anteriores y salen primero, lo que altera el orden de la cola. En el segundo ejemplo, 9 saldría antes que 7.
Informar que outbox está empty basándose solo en outbox. Justo después de una operación push, el nuevo elemento está en inbox, así que la cola no está vacía aunque outbox sí lo esté.
Olvidar que peek necesita el mismo rellenado que pop. Una operación peek justo después de las primeras operaciones push encuentra outbox vacío.
Usar una cola de una biblioteca o leer el fondo de una pila mediante un índice. La idea es obtener el orden de la cola usando solo operaciones de pila.
Devolver números o valores booleanos en vez de texto. Cada respuesta es una cadena, incluido "null" para una operación push.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de una cola construida a partir de dos pilas?

Push es O(1). Pop y peek son O(1) amortizado: una llamada puede mover todos los elementos de una pila a la otra, pero cada elemento se mueve como máximo una vez en su vida, así que n operaciones cuestan O(n) en total. Las dos pilas juntas contienen cada elemento una sola vez, por lo que el espacio es O(n).

¿Qué significa aquí O(1) amortizado?

Significa que el costo promedio por operación a lo largo de toda la secuencia es constante, aunque una sola operación pueda ser lenta. Un pop que vierte 1,000 elementos se compensa con las 1,000 inserciones baratas anteriores, porque esos elementos nunca volverán a verterse. Ninguna secuencia de n operaciones cuesta más de aproximadamente 4n pasos de pila.

¿Por qué necesitas dos pilas y no una?

Una pila solo expone su elemento más reciente, y una cola necesita el más antiguo. Para llegar al fondo de una pila, hay que retirar todo lo que hay encima, y esos elementos necesitan un lugar donde esperar: la segunda pila. Al mover los elementos de una pila a otra, se invierte su orden, y esa inversión es lo que convierte «el más reciente primero» en «el más antiguo primero».

¿Puedes implementar una pila usando colas en su lugar?

Sí, pero las formas habituales no ofrecen ningún ahorro amortizado. Una opción común utiliza una cola: después de añadir un elemento nuevo, toma cada elemento anterior del frente y añádelo al final, de modo que el elemento nuevo termine al frente. Eso hace que push sea O(n) y pop sea O(1).

Python

def queueOps(ops, args):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

ops = ["push", "push", "peek", "pop", "empty"]
args = [1, 2, 0, 0, 0]

Esperado

["null", "null", "1", "1", "false"]