Utiliser une file d'attente pour inverser une pile

Présentation

La file d'attente et la pile sont toutes deux des structures de données linéaires utilisées pour stocker des données. La pile utilise le principe LIFO pour insérer et supprimer des éléments. La file d'attente utilise le principe FIFO. Dans ce tutoriel, nous allons apprendre à utiliser les files d'attente pour inverser une pile. L'inversion signifie que le dernier élément de la pile devient le premier, et ainsi de suite.

Qu'est-ce qu'une pile ?

Les piles dans les structures de données sont inspirées de piles réelles. Il utilise la logique du dernier entré, premier sorti (LIFO), ce qui signifie que le dernier élément entré dans la pile sera supprimé en premier. Dans une pile, les éléments sont insérés par le haut et ne peuvent être supprimés que par le haut. La pile n'a qu'un seul point de terminaison.

Dans la vraie vie, empiler des journaux est un exemple de pile. Le journal retiré de la pile est le dernier à y être déposé.

Fonctionnalité de base de la pile

• push() - Il insérera un élément de pile par le haut.

  Syntaxe − stack_name.push (type d'élément)

• pop() - Cela supprimera les éléments du haut de la pile.

  Syntaxe − stack_name.pop()

• size() - Il renverra la taille de la pile.

  Syntaxe − stack_name.size()

• top() - Il renvoie une référence à l'élément supérieur de la pile.

  Syntaxe − stack_name.top()

Qu'est-ce qu'une file d'attente ?

Le concept de file d'attente dans la structure de données provient des files d'attente de la vie réelle. Dans la file d'attente, les éléments sont insérés depuis le backend et supprimés du frontend. Les deux extrémités de la file d’attente sont ouvertes et fonctionnent selon le principe du premier entré, premier sorti (FIFO). Ce principe signifie que l'élément inséré en premier sera d'abord supprimé de la file d'attente.

Fonctions de base de la file d'attente

• push() - Insère des éléments dans le backend de la file d'attente.

  Syntaxe − queue_name.push (type de données)

• pop() - Supprime un élément du début de la file d'attente.

  Syntaxe − queue_name.pop()

• front() - Obtenez une référence au premier élément de la file d'attente.

  Syntaxe − queue_name.front()

• size()* - Renvoie la taille de la file d'attente.

  Syntaxe − queue_name.size()

Pile inversée à l'aide de la file d'attente

Tout d'abord, comprenons ce qu'est l'inversion de pile à travers un exemple.

Stack before reversing: [2,5,6,7]
Stack Reversed: [7,6,5,2]

Logique - Nous utilisons une pile avec des éléments et une file d'attente vide. Extrayez les éléments de la pile un par un et insérez-les dans la file d'attente jusqu'à ce que tous les éléments aient été insérés. Maintenant, l'élément de file d'attente est supprimé et réinséré dans la pile vide. Finition.

Algorithme

Étape 1 : Insérez des éléments dans la pile.

Étape 2 : Obtenez une file d’attente vide.

Étape 3 : Poussez les éléments de la pile un par un dans la file d'attente vide.

Étape 4 : La pile est maintenant vide.

Étape 5 : extrayez les éléments de la file d'attente un par un et placez-les sur la pile.

Étape 6 : La pile est inversée.

Exemple

Exemple ci-dessous.

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
//function to reverse a queue
void reverse(queue<int> &q) {
   
   //Declaring a stack s
   stack<int> s;
   
   //inserting Queue elements into stack
   while (!q.empty()) {
      s.push(q.front());
      q.pop();
   }
   
   //Again pushing the elements into queue from back
   while (!s.empty()) {
      q.push(s.top());
      s.pop();
   }
}

void printQueue(queue<int> q) {
   
   while(!q.empty()) {
      cout<<q.front()<<" ";
      q.pop();
   }
   cout<<endl;
}

int main() {
   queue<int> q;
   //pushing elements into the Queue
   for(int i=1;i<=5;i++) {
      q.push(i);
   }
   cout<<"Initial Queue is: ";
   printQueue(q);
   
   reverse(q);
   
   cout<<"Reversed Queue is: ";
   printQueue(q);
}

Sortie

Initial Queue is: 1 2 3 4 5 
Reversed Queue is: 5 4 3 2 1 

Conclusion

Nous pouvons facilement inverser une pile en utilisant des files d'attente. Nous insérons l'élément de pile dans la file d'attente, puis insérons à nouveau l'élément de file d'attente dans la pile. J'espère que vous pourrez facilement comprendre et mettre en œuvre cette approche.

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!