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

La colonne

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

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.

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.

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 :

É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 :

Étape 3

Tous les éléments sont extraits de la deuxième pile, comme le montre la figure ci-dessous Montré :

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.

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>

Nous soumettons le code de test ci-dessus dans LeetCode, et les résultats d'exécution sont les suivants suit :

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!