Implement Queue Using Stacks

+10

Construisez une file FIFO dont le seul espace de stockage est constitué de deux piles. Une pile ne peut qu’ajouter un élément au sommet, retirer l’élément au sommet, lire l’élément au sommet et indiquer si elle est vide. La file prend en charge push x (ajouter x à la fin), pop (retirer et renvoyer l’élément en tête), peek (renvoyer l’élément en tête) et empty (la file est-elle vide ?).

Les opérations vous sont fournies dans l’ordre dans ops, et args[i] contient la valeur pour une opération push et 0 pour toutes les autres opérations. Exécutez-les sur une seule file initialement vide et renvoyez une chaîne pour chaque opération : "null" pour une opération push, le nombre sous forme de texte pour une opération pop ou peek, et "true" ou "false" pour une opération empty.

Fonction

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

opsstring-array: les opérations, dans l’ordre où elles s’exécutent
argsinteger-array: la valeur pour chaque push, 0 pour toute autre opération
Renvoiestring-array: une réponse par opération, sous forme de texte

Contraintes

1 ≤ ops.length ≤ 2000
args.length == ops.length
Chaque ops[i] est push, pop, peek ou empty.
-10⁹ ≤ args[i] ≤ 10⁹ pour une opération d’empilement, et args[i] == 0 pour toute autre opération.
On n’appelle pop et peek que lorsque la file contient au moins un élément.

Exemples

Entrée: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Sortie: ["null", "null", "1", "1", "false"]
Explication: Après avoir empilé 1 puis 2, l’élément en tête est 1, donc peek et pop renvoient tous deux "1". Le 2 est toujours à l’intérieur, donc empty renvoie "false".

Entrée: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Sortie: ["null", "null", "4", "null", "7", "9", "true"]
Explication: Le premier retrait renvoie 4, l’élément le plus ancien. 9 arrive alors que 7 attend toujours, et il sort après 7 parce qu’il est arrivé après lui. La file d’attente est alors vide, donc la dernière réponse est "true".

Entrée: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Sortie: ["true", "null", "-3", "-3", "true"]
Explication: La file d’attente est initialement vide, donc la première réponse est "true". Un nombre négatif est stocké comme n’importe quel autre : peek et pop renvoient tous deux "-3", puis la file d’attente est de nouveau vide.

+15 tests cachés à la soumission

Pour aller plus loin

Comment ajouteriez-vous une opération back qui renvoie l’élément le plus récent en O(1), sans compromettre la borne amortie des autres ?

Solution

Une pile restitue les éléments dans l’ordre inverse de leur arrivée, tandis qu’une file les restitue dans le même ordre. Verser une pile dans une deuxième pile inverse à nouveau l’ordre, ce qui transforme l’ordre d’une pile en celui d’une file. Toute la question est de savoir quand verser : le faire à chaque opération coûte O(n) à chaque fois, tandis que ne verser que lorsque la deuxième pile est vide fait passer chaque élément d’une pile à l’autre une seule fois.

Réorganisez toute la pile à chaque empilement

Intuition

Garde chaque élément dans une seule pile, main, en les disposant de sorte que le plus ancien soit au sommet. Ainsi, pop, peek et empty sont des opérations sur une seule pile.

Le travail se concentre sur push. Un nouvel élément doit être placé en bas, sous tous ceux qui attendent déjà, et une pile ne peut ajouter des éléments qu’au sommet. Déplace donc chaque élément de main vers la deuxième pile, helper, ajoute le nouvel élément sur la pile main vide, puis remets tout en place. Chaque déplacement inverse l’ordre ; deux déplacements le rétablissent, et le nouvel élément se retrouve en dessous.

C’est correct, mais chaque opération d’ajout touche deux fois chaque élément stocké. Ajouter 1 000 éléments à la suite coûte environ 2 × (0 + 1 + ... + 999), soit près d’un million de déplacements, alors qu’une vraie file n’en nécessite que 1 000.

Algorithme

Gardez deux piles : main, avec l’élément le plus ancien au sommet, et une pile helper vide.
Pour push x : dépilez chaque élément de main vers helper, empilez x sur main, puis dépilez chaque élément de helper pour le remettre sur main.
Pour pop et peek : dépilez ou lisez l’élément au sommet de main.
Pour empty : indiquez si main est vide.
Enregistrez chaque réponse sous forme de texte et renvoyez la liste.

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

Piles d’entrée et de sortie avec transfert différé

Intuition

Attribuez des rôles distincts aux piles. Chaque opération push ajoute un élément à inbox, en O(1). Les opérations pop et peek lisent dans outbox, dont le sommet correspond toujours à l’élément le plus ancien de la file.

Lorsque outbox est vide et qu’une opération pop ou peek est effectuée, transférez-y tout le contenu de inbox. L’élément le plus récent sort d’abord de inbox : il se retrouve donc au fond de outbox, tandis que l’élément le plus ancien se retrouve au sommet. Ne transférez les éléments que lorsque outbox est vide : tant qu’il contient des éléments, ceux-ci sont plus anciens que tous ceux de inbox et doivent donc sortir en premier. Dans le deuxième exemple, 4 et 7 sont transférés avant la première opération pop ; 9 attend ensuite dans inbox jusqu’à ce que 7 soit sorti.

Une seule opération pop peut déplacer de nombreux éléments, mais comptez plutôt le travail effectué pour chaque élément : chaque valeur est ajoutée une fois à inbox, déplacée une fois vers outbox et retirée une fois. n opérations coûtent donc O(n) au total, soit O(1) en coût amorti par opération. La file est vide lorsque les deux piles sont vides.

Algorithme

Conservez deux piles vides, inbox et outbox.
Pour push x : empilez x sur inbox.
Pour pop ou peek : si outbox est vide, dépilez chaque élément de inbox pour l'empiler sur outbox. Ensuite, dépilez ou lisez l'élément au sommet de outbox.
Pour empty : indiquez si les deux piles sont vides.
Enregistrez chaque réponse sous forme de texte et renvoyez la liste.

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

Pièges et cas limites

La plupart des bogues viennent d’un transfert effectué au mauvais moment ou du fait de ne vérifier qu’une seule pile.

Transférer inbox dans outbox alors que outbox contient encore des éléments. Les nouveaux éléments se retrouvent au-dessus des anciens et sortent en premier, ce qui rompt l’ordre de la file. Dans le deuxième exemple, 9 sortirait avant 7.
Signaler que la file est empty en vérifiant uniquement outbox. Juste après un push, le nouvel élément se trouve dans inbox : la file n’est donc pas vide, même si outbox l’est.
Oublier que peek nécessite le même rechargement que pop. Un peek effectué juste après les premiers push trouve outbox vide.
Utiliser une file de bibliothèque ou lire le bas d’une pile à l’aide d’un index. Le but est d’obtenir l’ordre d’une file en utilisant uniquement des opérations sur les piles.
Renvoyer des nombres ou des booléens au lieu de texte. Chaque réponse est une chaîne, y compris "null" pour un push.

Questions fréquentes4

Quelle est la complexité temporelle d'une file construite à partir de deux piles ?

L’empilement (push) est en O(1). Le dépilement (pop) et la consultation du sommet (peek) sont en O(1) amorti : un seul appel peut déplacer chaque élément d’une pile à l’autre, mais chaque élément n’est déplacé qu’une seule fois au cours de sa vie, donc n opérations coûtent O(n) au total. Les deux piles contiennent ensemble chaque élément une seule fois, donc l’espace est en O(n).

Que signifie O(1) amorti ici ?

Cela signifie que le coût moyen par opération sur l’ensemble de la séquence est constant, même si une opération isolée peut être lente. Un dépilement qui transfère 1 000 éléments est compensé par les 1 000 empilements peu coûteux qui le précèdent, car ces éléments ne seront plus jamais transférés. Aucune séquence de n opérations ne coûte plus d’environ 4n étapes de pile.

Pourquoi avez-vous besoin de deux piles et non d’une seule ?

Une pile ne donne accès qu’à son élément le plus récent, tandis qu’une file nécessite son élément le plus ancien. Pour atteindre le fond d’une pile, il faut retirer tout ce qui se trouve au-dessus, et ces éléments ont besoin d’un endroit où attendre : c’est le rôle de la deuxième pile. Le déplacement des éléments inverse leur ordre, et c’est cette inversion qui transforme « le plus récent en premier » en « le plus ancien en premier ».

Peux-tu plutôt implémenter une pile à l’aide de files d’attente ?

Oui, mais les méthodes habituelles ne permettent aucune économie amortie. Une méthode courante utilise une seule file : après avoir ajouté un nouvel élément, retirer chaque élément plus ancien du début et l’ajouter à la fin, de sorte que le nouvel élément se retrouve au début. Cela rend push O(n) et pop O(1).

Python

def queueOps(ops, args):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

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