Implement Queue Using Stacks

+10

Costruisci una coda FIFO la cui unica struttura di archiviazione sia costituita da due pile. Una pila può solo aggiungere un elemento in cima, rimuovere l’elemento in cima, leggere l’elemento in cima e indicare se è vuota. La coda supporta push x (aggiunge x in fondo), pop (rimuove e restituisce l’elemento in testa), peek (restituisce l’elemento in testa) e empty (la coda è vuota?).

Ricevi le operazioni in ordine come ops, con args[i] che contiene il valore per un’operazione push e 0 per ogni altra operazione. Esegui le operazioni su un’unica coda inizialmente vuota e restituisci una stringa per ogni operazione: "null" per un’operazione push, il numero come testo per un’operazione pop o peek e "true" oppure "false" per empty.

Funzione

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

opsstring-array: le operazioni, nell'ordine in cui vengono eseguite
argsinteger-array: il valore per ogni push, 0 per ogni altra operazione
Restituiscestring-array: una risposta per operazione, come testo

Vincoli

1 ≤ ops.length ≤ 2000
args.length == ops.length
Ogni ops[i] è push, pop, peek o empty.
-10⁹ ≤ args[i] ≤ 10⁹ per un'operazione di inserimento, e args[i] == 0 per qualsiasi altra operazione.
pop e peek vengono chiamate solo quando la coda contiene almeno un elemento.

Esempi

Input: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Output: ["null", "null", "1", "1", "false"]
Spiegazione: Dopo aver inserito 1 e poi 2, il fronte è 1, quindi peek e pop restituiscono entrambi "1". Il 2 è ancora all'interno, quindi empty restituisce "false".

Input: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Output: ["null", "null", "4", "null", "7", "9", "true"]
Spiegazione: Il primo pop restituisce 4, l'elemento più vecchio. 9 arriva mentre 7 è ancora in attesa e ne esce dopo 7 perché è arrivato dopo di lui. La coda è quindi vuota, perciò l'ultima risposta è "true".

Input: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Output: ["true", "null", "-3", "-3", "true"]
Spiegazione: La coda inizia vuota, quindi la prima risposta è "true". Un numero negativo viene memorizzato come qualsiasi altro: peek e pop restituiscono entrambi "-3", e poi la coda è di nuovo vuota.

+15 test nascosti all’invio

Per approfondire

Come aggiungeresti un'operazione back che restituisce l'elemento più recente in O(1), senza compromettere il limite ammortizzato delle altre?

Soluzione

Uno stack restituisce gli elementi nell’ordine inverso rispetto a quello in cui sono arrivati, mentre una coda li restituisce nello stesso ordine. Versare uno stack in un secondo stack inverte nuovamente l’ordine, trasformando così l’ordine dello stack in quello della coda. La questione è quando versare: farlo a ogni operazione costa O(n) ogni volta, mentre versare solo quando il secondo stack si svuota fa sì che ogni elemento venga spostato una sola volta.

Riordina l'intero stack a ogni inserimento

Intuizione

Tieni ogni elemento in un unico stack, main, disposto in modo che l'elemento più vecchio sia in cima. In questo modo, pop, peek ed empty sono operazioni su un singolo stack.

Il lavoro si sposta su push. Un nuovo elemento va in fondo, sotto tutto ciò che è già in attesa, e uno stack può aggiungere elementi solo in cima. Quindi sposta ogni elemento da main sul secondo stack, helper, inserisci il nuovo elemento nello stack main vuoto e sposta di nuovo tutto. Ogni spostamento inverte l'ordine, due spostamenti lo ripristinano e il nuovo elemento finisce sotto.

È corretto, ma ogni push tocca due volte ogni elemento memorizzato. Inserire 1.000 elementi di fila costa circa 2 × (0 + 1 + ... + 999), quasi un milione di spostamenti, mentre una vera coda richiede 1.000 passaggi.

Algoritmo

Mantieni due pile: main, con l'elemento più vecchio in cima, e una helper vuota.
Per push x: sposta ogni elemento da main a helper, inserisci x in main, poi sposta ogni elemento da helper di nuovo in main.
Per pop e peek: rimuovi o leggi l'elemento in cima a main.
Per empty: indica se main è vuota.
Registra ogni risposta come testo e restituisci l'elenco.

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

Stack di input e output con trasferimento differito

Intuizione

Assegna lavori separati agli stack. Ogni push va in inbox, in O(1). Le operazioni di pop e peek leggono da outbox, il cui elemento in cima è sempre l'elemento più vecchio della coda.

Quando outbox è vuoto e arriva un pop o un peek, versa al suo interno tutto il contenuto di inbox. L'elemento più recente esce per primo da inbox, quindi finisce in fondo a outbox, mentre quello più vecchio finisce in cima. Versa il contenuto solo quando outbox è vuoto: finché contiene elementi, questi sono più vecchi di qualsiasi elemento in inbox, quindi devono uscire per primi. Nel secondo esempio, 4 e 7 vengono trasferiti per il primo pop; poi 9 resta in attesa in inbox finché 7 non è uscito.

Una singola operazione di pop può spostare molti elementi, ma considera il lavoro per elemento: ogni valore viene inserito in inbox una volta, spostato in outbox una volta e rimosso con pop una volta. n operazioni hanno quindi un costo complessivo di O(n), pari a O(1) ammortizzato per operazione. La coda è vuota quando entrambi gli stack sono vuoti.

Algoritmo

Mantieni due pile vuote, inbox e outbox.
Per push x: inserisci x in inbox.
Per pop o peek: se outbox è vuota, sposta ogni elemento di inbox in outbox estraendolo. Poi estrai o leggi l'elemento in cima a outbox.
Per empty: indica se entrambe le pile sono vuote.
Registra ogni risposta come testo e restituisci l'elenco.

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

Trappole e casi limite

La maggior parte dei bug deriva dal versare al momento sbagliato o dal controllare un solo stack.

Versare inbox in outbox mentre outbox contiene ancora degli elementi. I nuovi elementi finiscono sopra quelli più vecchi ed escono per primi, alterando l'ordine della coda. Nel secondo esempio, 9 uscirebbe prima di 7.
Segnalare che outbox è empty basandosi solo su outbox. Subito dopo un push, il nuovo elemento si trova in inbox, quindi la coda non è vuota anche se outbox lo è.
Dimenticare che peek richiede lo stesso riempimento di pop. Un peek subito dopo i primi push trova outbox vuoto.
Usare una coda di una libreria o leggere il fondo di uno stack tramite indice. L'obiettivo è ottenere l'ordine di una coda usando solo le operazioni sugli stack.
Restituire numeri o valori booleani invece di testo. Ogni risposta è una stringa, incluso "null" per un push.

Domande frequenti4

Qual è la complessità temporale di una coda costruita con due stack?

Push è O(1). Pop e peek sono O(1) ammortizzato: una chiamata può spostare ogni elemento da uno stack all’altro, ma ciascun elemento viene spostato al massimo una volta nel corso della sua vita, quindi n operazioni costano complessivamente O(n). I due stack contengono insieme ogni elemento una sola volta, quindi lo spazio è O(n).

Che cosa significa O(1) ammortizzato in questo caso?

Significa che il costo medio per operazione sull'intera sequenza è costante, anche se una singola operazione può essere lenta. Un'operazione di rimozione che estrae 1.000 elementi è compensata dalle 1.000 operazioni di inserimento economiche che l'hanno preceduta, perché quegli elementi non verranno mai più estratti. Nessuna sequenza di n operazioni costa più di circa 4n passaggi sulla pila.

Perché hai bisogno di due pile e non di una?

Un singolo stack espone solo l'elemento più recente, mentre una coda ha bisogno di quello più vecchio. Per raggiungere il fondo di uno stack, bisogna rimuovere tutto ciò che si trova sopra, e quegli elementi hanno bisogno di un posto dove aspettare: il secondo stack. Spostare gli elementi da uno stack all'altro ne inverte l'ordine, ed è proprio questa inversione che trasforma «il più recente per primo» in «il più vecchio per primo».

Riesci invece a implementare uno stack usando delle code?

Sì, ma i metodi abituali non offrono alcun risparmio ammortizzato. Un metodo comune usa una coda: dopo aver aggiunto un nuovo elemento, prendi ogni elemento più vecchio dalla parte anteriore e aggiungilo in fondo, così il nuovo elemento finisce in testa. In questo modo, push richiede O(n) e pop richiede O(1).

Python

def queueOps(ops, args):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

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