Maison > Java > JavaBase > le corps du texte

Comment implémenter une file d'attente avec deux piles ?

coldplay.xixi
Libérer: 2020-10-26 17:54:47
avant
3384 Les gens l'ont consulté

La colonne

Tutoriel Java Basic présente comment utiliser deux piles pour implémenter une file d'attente .

Comment implémenter une file d'attente avec deux piles ?

La file d'attente et la pile sont deux structures de données très importantes dans les ordinateurs Après l'étude précédente ("Queue", "Stack"), nous savons en termes. de leurs caractéristiques respectives, la file d'attente est premier entré, premier sorti (FIFO) et la pile est premier entré, dernier sorti (FILO). Alors, comment utiliser la pile pour implémenter la file d'attente ? Il s'agit d'une question d'entretien classique, nous allons donc la mettre en œuvre dans cet article.

Avant de commencer officiellement, passons en revue les méthodes courantes de piles et de files d'attente.

Les méthodes couramment utilisées de Stack sont les suivantes :

  • push() : méthode push, ajoutant des éléments en haut de la pile
  • pop() : La méthode pop supprime l'élément en haut de la pile et renvoie l'élément ;
  • peek() : interroge l'élément en haut de la pile et ne supprime pas l'élément.

Comment implémenter une file dattente avec deux piles ?

Les méthodes courantes de Queue sont les suivantes :

  • offer() : méthode de mise en file d'attente, ajouter à la fin de l'élément de file d'attente ;
  • poll() : méthode dequeue, supprime et renvoie l'élément de la tête de la file d'attente ;
  • peek() : interroge l'élément de tête de la file d'attente et ne supprime pas l'élément.

Comment implémenter une file dattente avec deux piles ?Avec ces connaissances préalables, regardons le sujet d’aujourd’hui.

Description du problème

Utilisez deux piles pour implémenter une file d'attente. La file d'attente est déclarée comme suit. Veuillez implémenter ses deux fonctions, appendTail et deleteHead, pour terminer respectivement les fonctions d'insertion d'un entier à la fin de la file d'attente et de suppression d'un entier en tête de la file d'attente. file d'attente, l'opération deleteHead renvoie -1.

Exemple 1 :

Entrée :

["CQueue","appendTail","deleteHead","deleteHead"]

[ [],[3],[],[]]

Sortie : [null,null,3,-1]

Exemple 2 :

Entrée :

["CQueue", "deleteHead", "appendTail", "appendTail", "deleteHead", "deleteHead"]

[[],[],[5],[2],[ ],[]]

Sortie : [null,-1,null,null,5,2]

Indice :

1

Jusqu'à 10000 appels à appendTail et deleteHead seront effectués

leetcode : leetcode-cn.com/problems/yo…

Idée de question de solution

Le sens de cette question est en fait facile à comprendre, c'est-à-dire changer la pile premier entré, dernier sorti en une file d'attente premier entré, premier sorti. La question donne également quelques indices : "Utilisez deux piles pour implémenter une file d'attente". L'idée centrale de​​cette question est "un négatif fait un positif". Nous utilisons d'abord une pile pour stocker des éléments (le premier élément à saisir est en bas de la pile), puis ajoutons les éléments. dans la première pile Passer à la nouvelle pile. À ce moment, le premier élément entré est en haut de la pile. Ensuite, lorsque la deuxième pile est utilisée pour le sortir, l'ordre d'exécution complet devient premier entré, premier sorti. .

Ensuite, implémentons l'ensemble du processus graphiquement.

Étape 1

Poussez d'abord l'élément dans la première pile, comme indiqué dans la figure ci-dessous : Comment implémenter une file dattente avec deux piles ?

Étape 2

Poussez l'élément dans la première pile, comme indiqué ci-dessous : Les éléments d'une pile sont déplacés vers la deuxième pile, comme indiqué dans la figure ci-dessous : Comment implémenter une file dattente avec deux piles ?

Étape 3

Tous les éléments sont extraits de la deuxième pile, comme le montre la figure ci-dessous Montré : Comment implémenter une file dattente avec deux piles ?

Résumé

Comme le montre l'image ci-dessus, l'ordre d'ajout d'éléments est 1, 2, 3 et l'ordre final de saut après deux piles est également 1, 2, 3, de sorte que nous implémentons la file d'attente (premier entré, premier sorti) à travers deux piles. Comment implémenter une file dattente avec deux piles ?

Code d'implémentation

Ensuite, nous utiliserons du code pour implémenter les idées ci-dessus :

class CQueue {
    Stack<integer> inputStack; // 入栈的容器(添加时操作)
    Stack<integer> outputStack; // 出栈和查询的栈容器

    public CQueue() {
        inputStack = new Stack();
        outputStack = new Stack();
    }    // 添加操作
    public void appendTail(int value) {
        inputStack.push(value);
    }    // 删除操作
    public int deleteHead() {        if (!outputStack.isEmpty()) {            // 出栈容器不为空
            return outputStack.pop();
        } else if (!inputStack.isEmpty()) {            // 入栈 stack 全部转移到出栈 stack
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}复制代码</integer></integer>
Copier après la connexion

Nous soumettons le code de test ci-dessus dans LeetCode, et les résultats d'exécution sont les suivants suit :Comment implémenter une file dattente avec deux piles ?

Notes

Il y a deux petits détails qui nécessitent une attention particulière pendant tout le processus de mise en œuvre :

  1. La première pile est uniquement responsable de pousser dans la pile (stocker temporairement les données), la deuxième pile est uniquement responsable du popping (la séquence d'exécution finale de la file d'attente
  2. Chaque fois que la pile 2 est poppée, tous les éléments doivent être sortis avant d'être ajoutés à partir de la pile 1 (); Ajouter) de nouvelles données Lorsque toutes les données de la pile 2 n'ont pas été poussées hors de la pile, les éléments de la pile 1 ne peuvent pas être poussés dans la pile 2. Cela entraînera une confusion dans l'ordre d'exécution des éléments.

Résumé

Dans cet article, nous utilisons deux piles premier entré, dernier sorti et implémentons la fonctionnalité premier entré, premier sorti de la file d'attente grâce à l'idée de ​​​​"les négatifs font les positifs", mais une attention particulière est requise Lorsque la deuxième pile, qui est le conteneur pop-up, n'est pas vide (pile), les éléments de la première pile ne peuvent pas être ajoutés à la deuxième pile pour éviter. confondre l'ordre d'exécution du programme.

Recommandations d'apprentissage gratuites associées : Tutoriel de base Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:juejin.im
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!