Structure des données et algorithmes - File d'attente

Queue est une structure de données abstraite, quelque peu similaire à Stacks. Contrairement aux piles, une file d'attente est ouverte à ses deux extrémités. Une extrémité est toujours utilisée pour insérer des données (mise en file d'attente) et l'autre est utilisée pour supprimer des données (dequeue). La file d'attente suit la méthodologie du premier entré, premier sorti, c'est-à-dire que l'élément de données stocké en premier sera consulté en premier.

Un exemple concret de file d'attente peut être une route à sens unique à voie unique, où le véhicule entre en premier, sort en premier. D'autres exemples concrets peuvent être considérés comme des files d'attente aux guichets et aux arrêts de bus.

Représentation de la file d'attente

Comme nous comprenons maintenant que dans la file d'attente, nous accédons aux deux extrémités pour des raisons différentes. Le diagramme suivant donné ci-dessous tente d'expliquer la représentation de la file d'attente sous forme de structure de données -

Comme dans les piles, une file d'attente peut également être implémentée à l'aide de tableaux, de listes liées, de pointeurs et de structures. Par souci de simplicité, nous allons implémenter des files d'attente en utilisant un tableau à une dimension.

Opérations de base

Les opérations de file d'attente peuvent impliquer l'initialisation ou la définition de la file d'attente, son utilisation, puis son effacement complet de la mémoire. Ici, nous allons essayer de comprendre les opérations de base associées aux files d'attente -

enqueue() - ajouter (stocker) un élément à la file d'attente.
dequeue() - supprimer (accéder) un élément de la file d'attente.

Peu de fonctions supplémentaires sont nécessaires pour rendre efficace l'opération de file d'attente mentionnée ci-dessus. Ce sont -

peek() - Obtient l'élément au début de la file d'attente sans le supprimer.
isfull() - Vérifie si la file d'attente est pleine.
isempty() - Vérifie si la file d'attente est vide.

Dans la file d'attente, nous retirons (ou accédons) toujours aux données, pointées par front pointeur et tout en enregistrant (ou en stockant) des données dans la file d'attente, nous prenons l'aide de rear aiguille.

Découvrons d'abord les fonctions de support d'une file d'attente -

coup d'oeil ()

Cette fonction permet de voir les données au frontde la file d'attente. L'algorithme de la fonction peek () est le suivant -

Algorithm

begin procedure peek
   return queue[front]
end procedure

Implémentation de la fonction peek () en langage de programmation C -

Example

int peek() {
   return queue[front];
}

est rempli()

Comme nous utilisons un tableau à dimension unique pour implémenter la file d'attente, nous vérifions simplement que le pointeur arrière atteint MAXSIZE pour déterminer que la file d'attente est pleine. Si nous maintenons la file d'attente dans une liste chaînée circulaire, l'algorithme sera différent. Algorithme de la fonction isfull () -

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Implémentation de la fonction isfull () en langage de programmation C -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

est vide()

Algorithme de la fonction isempty () -

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

Si la valeur de front est inférieur à MIN ou 0, il indique que la file d'attente n'est pas encore initialisée, donc vide.

Voici le code de programmation C -

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

Opération de mise en file d'attente

Les files d'attente maintiennent deux pointeurs de données, front et rear. Par conséquent, ses opérations sont comparativement difficiles à mettre en œuvre que celles des piles.

Les étapes suivantes doivent être prises pour mettre en file d'attente (insérer) des données dans une file d'attente -

Step 1 - Vérifiez si la file d'attente est pleine.
Step 2 - Si la file d'attente est pleine, générer une erreur de dépassement de capacité et quitter.
Step 3 - Si la file d'attente n'est pas pleine, incrémentez rear pointeur pour pointer le prochain espace vide.
Step 4 - Ajoutez un élément de données à l'emplacement de la file d'attente, où pointe l'arrière.
Step 5 - retour de succès.

Parfois, nous vérifions également si une file d'attente est initialisée ou non, pour gérer d'éventuelles situations imprévues.

Algorithme pour l'opération de mise en file d'attente

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

Implémentation de enqueue () en langage de programmation C -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

Opération de retrait de la file d'attente

L'accès aux données de la file d'attente est un processus de deux tâches: accéder aux données où frontpointe et supprime les données après l'accès. Les étapes suivantes sont prises pour effectuerdequeue opération -

Step 1 - Vérifiez si la file d'attente est vide.
Step 2 - Si la file d'attente est vide, générer une erreur de sous-dépassement et quitter.
Step 3 - Si la file d'attente n'est pas vide, accédez aux données où front pointe.
Step 4 - Incrément front pointeur pour pointer vers le prochain élément de données disponible.
Step 5 - Retournez le succès.

Algorithme pour l'opération de retrait de la file d'attente

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Implémentation de dequeue () en langage de programmation C -

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Pour un programme Queue complet en langage de programmation C, veuillez cliquer ici .