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 procedureImplé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 procedureImplé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 procedureSi 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 procedureImplé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 procedureOpé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 procedureImplé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 .