Concevoir une structure de données de file d'attente pour obtenir la valeur minimale ou maximale en un temps O(1)

C++ a un fichier d'en-tête deque pour gérer les propriétés des piles et des files d'attente. Dans les structures de données, résoudre le problème de complexité temporelle O(1) nécessite un temps constant. En utilisant un deque dans ce programme, nous bénéficions des avantages de l'utilisation à la fois d'une pile et d'une file d'attente.

Dans cet article, nous allons résoudre la structure des données de file d'attente pour obtenir la valeur minimale ou maximale d'un nombre en un temps O(1).

Grammaire

deque<data_type> name_of_queue;

Paramètres

• deque - C'est ce qu'on appelle un deque, qui commande un ensemble d'éléments ou de numéros équivalents à une file d'attente.

• data_type - le type de données utilisé, tel que int, float, etc.

• name_of_queue - n'importe quel nom donné à la file d'attente, comme ab, cd, etc.

front()

front() est une fonction prédéfinie en C++ STL, qui fait directement référence à la première position d'index de la file d'attente.

back()

back() est une fonction prédéfinie en C++ STL, qui fait directement référence à la dernière position d'index de la file d'attente.

push_back()

push_back() est également une fonction prédéfinie pour insérer des éléments par derrière.

Algorithme

• Nous utiliserons les fichiers d'en-tête 'iostream' et 'deque' pour démarrer le programme.

• Nous insérons dans deque pour gérer la valeur maximale ou minimale du nombre.

  • "dequedq" - En l'utilisant, nous pouvons activer les propriétés des piles et des files d'attente

• À partir de la boucle for, nous insérons des éléments dans la plage 10 à 15. Puis poussez les éléments du tableau à l'aide d'une boucle for appelée 'push_back[i ]' qui accepte 'i' comme argument.

• Ensuite, nous créons deux variables en utilisant les fonctions prédéfinies front() et back() pour trouver la valeur minimale et maximale d'un nombre. front() recherche le premier index pour représenter le plus petit nombre, tandis que back() recherche le dernier index pour représenter le plus grand nombre.

• Maintenant, nous initialisons la boucle for pour parcourir la longueur du numéro d'index et utiliser cette longueur pour classer la comparaison des éléments les plus petits et les plus grands comme 'dq[i]'. Ainsi, cela trouvera le nombre minimum et maximum.

• Enfin, nous imprimons la sortie de longueur minimale et maximale à l'aide des variables 'min_element' et 'max_element'.

Exemple

Dans ce programme, nous allons résoudre la structure des données de file d'attente pour obtenir les valeurs minimale et maximale en un temps O(1).

#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq; 
   // double ended queue
   // insert elements into the deque using a loop
   for(int i = 10; i <= 15; i++) {
      dq.push_back(i);
   }
   // find the minimum and maximum elements
   int min_element = dq.front();
   int max_element = dq.back();

   for(int i = 1; i < dq.size(); i++) {
      if(dq[i] < min_element) {
         min_element = dq[i];
      }
      if(dq[i] > max_element) {
         max_element = dq[i];
      }
   }
   //Print the minimum and maximum elements
   cout << "Minimum element: " << min_element << endl;
   cout << "Maximum element: " << max_element << endl;
   return 0;
}

Sortie

Minimum element: 10
Maximum element: 15

Conclusion

Nous avons exploré le concept de structure de données de file d'attente pour trouver l'élément le plus petit ou le plus grand. Nous avons vu comment front() et back() peuvent être utilisés pour trouver la valeur minimale et maximale d'un élément, et également comment ajouter un refoulement à la fin d'un élément indexé. En utilisant un deque, nous pouvons gérer le problème en complexité temporelle O(1).

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!