Créer une pile avec une file d'attente et une file d'attente avec une pile (à partir de LetCode / Implémenter la pile à l'aide de files d'attente, Implémenter la file d'attente à l'aide de piles)

(Réimprimé de Article de blog)

L'une des structures de données importantes est Stack et Queue, mais nous aborderons le problème de leur mise en œuvre.

Cependant, comme indiqué dans Cet article de commentaire, les piles et les files d'attente peuvent être représentées par des tableaux, qui sont une structure de données spéciale. N'est pas. La différence importante est l'utilisation suivante.

Extraire le dernier élément poussé dans la structure de données de la pile Extraire le premier élément poussé dans la structure de données de la file d'attente

Implémentez la classe Stack et la classe Queue avec les fonctions ci-dessus.

Implement Stack using Queues

[https://leetcode.com/problems/implement-stack-using-queues/]

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1); stack.push(2); stack.top(); // returns 2 stack.pop(); // returns 2 stack.empty(); // returns false

Notes:

You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Tout d'abord, de la mise en œuvre de stack. Comme vous pouvez le voir dans le titre du problème, vous devez implémenter la pile à l'aide de la file d'attente.

L'utilisation d'une file d'attente limite les opérations pouvant être effectuées. Le push est limité à l'arrière et le pop est limité à l'avant, car seules les opérations push to back, peek / pop de l'avant, taille et vide sont valides.

Mauvaise réponse

Si vous le faites, le test réussira même si vous ignorez l'intention du problème et utilisez stack. Mais, bien sûr, il ne sert à rien de créer une pile en utilisant stack. En python, la liste montre le comportement de la pile.

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.stack.append(x)
        

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.stack.pop()
        

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.stack[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return len(self.stack) == 0

Solution

Ce problème vous oblige à implémenter la pile à l'aide de la file d'attente, mais le point est pop. Là encore, stack récupère le dernier élément poussé, tandis que queue récupère le premier élément poussé.

En python, vous pouvez récupérer le premier élément poussé avec queue.popleft (). La solution suivante consiste à utiliser popleft pour trier la file d'attente afin que l'élément qui a été poussé plus tard arrive en premier lorsque vous exécutez push.

class MyStack:

    def __init__(self):
        self.queue = collections.deque()
        

    def push(self, x: int) -> None:
        q = self.queue
        q.append(x)
        for _ in range(len(q)-1):
            q.append(q.popleft())
        

    def pop(self) -> int:
        return self.queue.popleft()
        

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

    def empty(self) -> bool:
        return len(self.queue) == 0

Il en coûte $ O (n) $ pour le push et $ O (1) $ pour le pop.

À propos, il ne peut pas être utilisé à la demande de ce problème, mais comme décrit dans l'article suivant, il existe également une méthode pop dans collections.deque (), et le montant du calcul du temps est de $ O (1) $ à l'arrière. Il est possible de récupérer et de supprimer des éléments.

[https://note.nkmk.me/python-collections-deque/:embed:cite]

Implement Queue using Stacks

[https://leetcode.com/problems/implement-queue-using-stacks/]

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false

Notes:

You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Vient ensuite l'implémentation de Queue. Vous êtes maintenant invité à implémenter la file d'attente à l'aide de stack.

Cela limite également les opérations possibles. seules les opérations push to top, peek / pop from top, size et is empty sont valides. En d'autres termes, pour push, peek et pop, seuls list.append (x), list [-1] et list.pop () sont autorisés.

Solution

La solution suivante consiste à préparer deux piles, à les stocker dans l'inStack lors de la poussée, et à préparer un outStack qui stocke les éléments de l'inStack dans l'ordre inverse pour peek et pop, et effectuer le traitement.

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.inStack, self.outStack = [], []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.inStack.append(x)
        

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        self.peek()
        return self.outStack.pop()
        

    def peek(self) -> int:
        """
        Get the front element.
        """
        if(self.outStack == []):
            while(self.inStack != []):
                self.outStack.append(self.inStack.pop())
        return self.outStack[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.inStack) == 0 and len(self.outStack) == 0

Recommended Posts

Créer une pile avec une file d'attente et une file d'attente avec une pile (à partir de LetCode / Implémenter la pile à l'aide de files d'attente, Implémenter la file d'attente à l'aide de piles)
Créer un bloc de données à partir d'Excel à l'aide de pandas
Implémenter un modèle avec état et comportement
Créez un outil qui secoue automatiquement furigana avec html en utilisant Mecab de Python3
Créer une application Todo avec Django ④ Implémenter la fonction de création de dossier et de tâche
Créez un arbre de décision à partir de 0 avec Python et comprenez-le (5. Entropie des informations)
Créez une interface utilisateur de jeu à partir de zéro avec pygame2!
Créer un arbre phylogénétique à partir de Biopyton en utilisant ClustalW2
Créer une carte Web en utilisant Python et GDAL
Créer un arbre de décision à partir de 0 avec Python (1. Présentation)
Créez un capteur de couleur à l'aide d'une tarte à la râpe et d'une caméra
Créez une application graphique native avec Py2app et Tkinter
[Python] Générer ValueObject avec un constructeur complet à l'aide de classes de données
Créez un lot d'images et gonflez avec ImageDataGenerator
Créer une visionneuse de modèle 3D avec PyQt5 et PyQtGraph
Créez un environnement d'apprentissage automatique à partir de zéro avec Winsows 10
[Linux] Créez un auto-certificat avec Docker et apache
Créez un arbre de décision à partir de zéro avec Python et comprenez-le (3. Bibliothèque d'analyse de données édition Pandas)
Créez une caméra de surveillance WEB avec Raspberry Pi et OpenCV
Créez des applications, enregistrez des données et partagez-les avec un seul e-mail
Créons un diagramme PRML avec Python, Numpy et matplotlib.
Hash avec python et échapper à l'égosa d'un certain ministre
Python: créer un dictionnaire à partir d'une liste de clés et de valeurs
Créez un script de déploiement avec fabric et cuisine et réutilisez-le
Créer une instance GCE à partir d'une image Docker GCR à l'aide de terraform
Tirez en accéléré à partir d'une caméra PC en utilisant Python, OpenCV
Créer une page d'accueil avec django
Utiliser une imprimante avec Debian 10
Pile et file d'attente en Python
Créer un répertoire avec python
Créer une API qui renvoie les données d'un modèle à l'aide de turicreate
Créons une IA à trois voies avec Pylearn2 --Save and load model -
Créez un fichier temporaire avec django sous forme de zip et renvoyez-le
Créez une illusion rayée avec correction gamma pour Python3 et openCV3
Obtenez des données de VPS MySQL avec Python 3 et SQL Alchemy
Création et déploiement d'applications Django (PTVS) à l'aide du stockage Azure Table
Créez un lot planifié simple à l'aide de l'image Python de Docker et de parse-crontab
Créez facilement un TalkBot en utilisant Discord.py et l'API Talk d'A3RT (pya3rt).
J'ai essayé de créer des taureaux et des vaches avec un programme shell
[Remarque] Utilisation d'un écran LCD à 16 caractères à 2 chiffres (1602A) de Python avec Raspeye
Obtenez les conditions de simulation OCTA à partir d'un fichier et enregistrez avec les pandas
Créer et renvoyer un fichier CSV CP932 pour Excel avec Chalice