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 :
Les méthodes courantes de Queue sont les suivantes :
Avec ces connaissances préalables, regardons le sujet d’aujourd’hui.
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…
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 decette 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.
Poussez d'abord l'élément dans la première pile, comme indiqué dans la figure ci-dessous :
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 :
Tous les éléments sont extraits de la deuxième pile, comme le montre la figure ci-dessous Montré :
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.
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 :
Il y a deux petits détails qui nécessitent une attention particulière pendant tout le processus de mise en œuvre :
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!