Implement Stack using Queues

+10

Construis une pile dernier entré, premier sorti dont le seul espace de stockage est constitué de files. Une file ne peut qu’ajouter un élément à la fin, supprimer ou lire l’élément en tête et indiquer sa taille. La pile prend en charge push x (placer x au sommet), pop (supprimer et renvoyer l’élément au sommet), top (renvoyer l’élément au sommet sans le supprimer) et empty (la pile est-elle vide ?).

Les opérations arrivent dans l’ordre dans ops, et args[i] contient la valeur à utiliser pour un push, et 0 dans les autres cas. Exécute-les sur une pile vide et renvoie une chaîne par opération : "null" pour un push, le nombre sous forme de texte pour un pop ou un top, et "true" ou "false" pour empty.

Fonction

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

opsstring-array: les opérations, dans l’ordre où elles sont exécutées
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 ≤ 1000
args.length == ops.length
Chaque ops[i] est push, pop, top ou empty.
-10⁹ ≤ args[i] ≤ 10⁹ pour une opération d’insertion, et args[i] == 0 pour toute autre opération.
pop et top ne sont appelés que lorsque la pile contient au moins un élément.

Exemples

Entrée: ops = ["push", "push", "top", "pop", "empty"]args = [1, 2, 0, 0, 0]
Sortie: ["null", "null", "2", "2", "false"]
Explication: 2 est entré en dernier, il est donc au sommet : top et pop renvoient tous deux "2". Le 1 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", "7", "null", "9", "4", "true"]
Explication: Le premier pop renvoie 7, l’élément le plus récent. 9 se place ensuite au-dessus de 4 et sort avant lui, donc les pop suivants renvoient "9" et "4", et la pile finit vide.

Entrée: ops = ["empty", "push", "top", "pop", "empty"]args = [0, -3, 0, 0, 0]
Sortie: ["true", "null", "-3", "-3", "true"]
Explication: La pile est vide au départ, donc la première réponse est "true". Une valeur négative est stockée comme n’importe quelle autre : top et pop renvoient tous deux "-3", et la pile est de nouveau vide.

Pour aller plus loin

Peux-tu conserver une seule file, mais déplacer le travail de l’ajout vers le retrait, afin que l’ajout soit en O(1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une file d’attente libère les éléments du plus ancien au plus récent, une pile du plus récent au plus ancien, et une file d’attente ne vous montre jamais l’élément situé à l’arrière. Votre seul outil consiste à défiler depuis l’avant et à enfiler à l’arrière, ce qui fait tourner la file. Faites-la tourner pour amener l’élément le plus récent à l’avant, soit lorsque vous devez le lire, soit juste après son arrivée.

Deux files d’attente, extraire l’élément le plus récent lors du dépilement

Intuition

Garde les éléments dans une file main dans leur ordre d’arrivée, de sorte que le plus récent soit à l’arrière et qu’un push corresponde à un seul enqueue. Un pop déplace chaque autre élément dans une seconde file, spare, jusqu’à ce qu’il n’en reste qu’un : le plus récent. Retire-le de la file et échange les files, puisque spare contient alors le reste dans son ordre d’origine. Un top effectue le même parcours, mais ajoute aussi le plus récent à spare.

Chaque pop ou top déplace une fois chaque élément stocké : 500 push, chacun suivi d’un top, coûtent 1 + 2 + ... + 500, soit environ 125 000 déplacements.

Algorithme

Conservez deux files : main avec les éléments dans leur ordre d’arrivée, et une spare vide.
Pour push x : ajoutez x à main.
Pour pop et top : déplacez les éléments de main vers spare jusqu’à ce qu’il n’en reste qu’un, puis retirez-le de la file pour obtenir la réponse. Pour top, ajoutez-le aussi à spare. Échangez les files.
Pour empty : indiquez si main est vide.

from collections import deque

class QueueStack:
    def __init__(self):
        self.main = deque()    # the oldest item at the front, the newest at the back
        self.spare = deque()   # empty between operations

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

    def _move_all_but_newest(self):
        # Pass every item except the newest to the spare queue, in order.
        while len(self.main) > 1:
            self.spare.append(self.main.popleft())

    def pop(self):
        self._move_all_but_newest()
        newest = self.main.popleft()
        self.main, self.spare = self.spare, self.main
        return newest

    def top(self):
        self._move_all_but_newest()
        newest = self.main.popleft()
        self.spare.append(newest)   # top keeps the item
        self.main, self.spare = self.spare, self.main
        return newest

    def empty(self):
        return not self.main

def stackOps(ops, args):
    stack = QueueStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(stack.pop()))
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append("true" if stack.empty() else "false")
    return result

Une file d’attente, effectuer une rotation après chaque ajout

Intuition

Gardez la file toujours dans l’ordre d’une pile, avec l’élément le plus récent à l’avant. Ainsi, pop correspond à un retrait de la file, top lit l’élément à l’avant, et la deuxième file n’est pas nécessaire. Un nouvel élément x rejoint l’arrière, derrière les éléments plus anciens, qui sont déjà dans l’ordre du plus récent au plus ancien. Retirez l’élément à l’avant et ajoutez-le à l’arrière size-1 fois : à chaque étape, un élément plus ancien passe derrière x, en conservant leur ordre, si bien que x se retrouve à l’avant.

Dans le premier exemple, empiler 2 sur [1] donne [1, 2], et une rotation donne [2, 1]. Empiler sur k éléments coûte k rotations ; push est donc en O(n), et le reste en O(1).

Algorithme

Conservez une seule file dont l’avant correspond toujours au sommet de la pile.
Pour push x : enfilez x, puis répétez size-1 fois : défiler l’élément en tête et le remettre dans la file.
Pour pop : défiler l’élément en tête et le renvoyer.
Pour top : renvoyer l’élément en tête sans le retirer.
Pour empty : indiquer si la file est vide.

from collections import deque

class QueueStack:
    def __init__(self):
        self.queue = deque()   # the newest item is always at the front

    def push(self, x):
        self.queue.append(x)
        # Rotate the older items behind x, so x comes out first.
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self):
        return self.queue.popleft()

    def top(self):
        return self.queue[0]

    def empty(self):
        return not self.queue

def stackOps(ops, args):
    stack = QueueStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(stack.pop()))
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append("true" if stack.empty() else "false")
    return result

Pièges et cas limites

Faire tourner size fois au lieu de size-1. Un tour complet laisse x à l’arrière, donc le prochain retrait renvoie l’élément le plus ancien.
Faire tourner avant d’ajouter x. Les éléments plus anciens tournent en cercle et x se retrouve toujours à l’arrière.
Avec deux files, ne pas remettre l’élément sur top. Le prochain retrait renvoie alors l’élément qui se trouve en dessous.
Avec deux files, ne pas les intervertir. Les éléments restent dans spare, et empty renvoie "true" trop tôt.
Renvoyer des nombres ou des booléens. Chaque réponse est une chaîne, y compris "null" pour un ajout.

Questions fréquentes3

Quelle est la complexité temporelle d'une pile construite à partir de files ?

Avec une seule file qui effectue une rotation à chaque insertion, l’insertion est en O(n) et le retrait, l’accès au sommet et la vérification du vide sont en O(1). Avec deux files qui déplacent les éléments à chaque retrait, l’insertion est en O(1) et le retrait ainsi que l’accès au sommet sont en O(n). Dans les deux cas, chaque élément est stocké une seule fois, donc l’espace est en O(n).

Pourquoi une pile à partir de files est-elle plus lente qu’une file à partir de piles ?

Verser une pile dans une autre inverse son ordre : un seul versement transforme donc l’ordre d’une pile en ordre de file, et chaque élément n’est déplacé qu’une seule fois au cours de son existence. Déplacer des éléments entre des files préserve leur ordre, donc aucun transfert ne les inverse. C’est pourquoi une opération coûte toujours O(n) ici.

Est-ce que l’opération coûteuse doit être push ou pop ?

Fais payer le coût à l’opération la moins fréquente. Si la pile est lue avec top et pop beaucoup plus souvent qu’elle ne grandit, effectue une rotation lors de l’empilement afin que chaque lecture soit en O(1). Si de nombreux empilements surviennent avant quelques dépilements, garde l’empilement en O(1) et déplace les éléments au moment du dépilement.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

["null", "null", "2", "2", "false"]