Implémentation de la file d'attente à l'aide de Stack

La file d'attente et la pile sont des structures de données assez simples que nous utilisons dans notre codage quotidien. En fait, elles peuvent être considérées comme les structures les plus simples pour gérer les données.

Tout au long de l'article, j'utiliserai DS pour faire référence à la structure des données.

Queue est un DS qui fonctionne sur le principe FIFO. Les données qui arrivent en premier sont autorisées à sortir en premier. Il existe de nombreuses façons de mettre en œuvre des files d'attente. Nous sommes libres d'utiliser des tableaux, des listes chaînées et bien d'autres. Mais ici, je suis sur le point de discuter de l'implémentation de Queue en utilisant un autre DS appelé Stack.

Maintenant, nous le savons tous, Stack est une DS qui fonctionne sur le principe LIFO. Je pense toujours à empiler les livres les uns sur les autres, alors n'hésitez pas à utiliser cette analogie si cela vous aide à visualiser.

Je suis tombé sur cette question dans hackerrank où ils nous demandaient d'implémenter Queue en utilisant 2 Stacks. Cela semble simple, n'est-ce pas ? Prenez un moment pour réfléchir à la manière dont nous pourrions y parvenir.

Vous avez peut-être trouvé des solutions car il existe de nombreuses façons de procéder. Alors pourquoi ne pas l'essayer directement ?

Question

Maintenant, pour ceux qui ont essayé et obtenu une "erreur de temps mort" et pour ceux qui n'ont pas pris la peine d'essayer, laissez-moi vous expliquer la solution la plus simple et la plus facile à ce problème.

Jetez d’abord un œil à la façon dont la pile peut être implémentée.

Comme vous pouvez le voir, j'ai implémenté une pile à l'aide d'une liste. Initialement, le constructeur initialise une liste vide. Nous poussons les données en les ajoutant à la fin de la liste. Lors de l'affichage, si nous ne fournissons pas d'index, il apparaît à la fin de la liste. Ainsi, le dernier élément à insérer est le premier à être retiré.

Maintenant, de la même manière pour la file d'attente, nous avons initialisé deux piles différentes. Un pour la mise en file d'attente et un pour la sortie de la file d'attente.

Nous utilisons enqueueStack similaire à la pile uniquement pour pousser les données à la fin de la liste. Mais pour dequeueStack, nous savons que la fonction pop de stack supprime l'élément du dernier, donc ce que nous faisons est : nous inverseons l'enqueueStack et le mettons dans dequeueStack. Ainsi, le premier élément de enqueueStack devient le dernier élément de dequeueStack, le deuxième de enqueueStack devient l'avant-dernier de dequeueStack et ainsi de suite. Alors maintenant, si nous utilisons la fonction pop pour dequeueStack, elle supprimera le premier élément que nous avons poussé, imitant ainsi la file d'attente.

Ne vous inquiétez pas si cela vous semble déroutant en ce moment ! Une fois que vous aurez vu le code, vous comprendrez de quoi je parle. En fait, jetez-y un œil dès maintenant !

Vous vous demandez peut-être à quoi servent ces contrôles supplémentaires. Comme vérifier si le dequeueStack est vide ou non. Si nous ne le vérifions pas initialement. Les éléments de enqueueStack par inversion resteront dans le dequeueStack et ce qui se passe, c'est que l'élément dequeue Stacks qui était censé être activé en premier finit maintenant par être le dernier. Donc, dequeueStack doit d’abord être vidé comme indiqué dans le code.

De la même manière, printFront imprime l'élément qui est censé être en début de file d'attente.

Après cette implémentation, nous lisons les entrées de STDIN et imprimons la sortie sur STDOUT.

Notre contribution ressemble un peu à ceci :

Et la fonction principale complète est :

J'ai essayé de mettre en œuvre cela de la manière la plus simple possible. Il pourrait y avoir plusieurs autres et meilleures façons de mettre en œuvre cela. L'un d'eux est présenté ici !

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!