Dans ce didacticiel, vous apprendrez ce qu'est une file d'attente. Vous trouverez également l'implémentation de la file d'attente en C, C ++, Java et Python.
Une file d'attente est une structure de données utile en programmation. C'est similaire à la file d'attente à l'extérieur d'une salle de cinéma, où la première personne entrant dans la file d'attente est la première personne à obtenir le billet.
La file d'attente suit la règle du premier entré, premier sorti (FIFO) - l'élément qui entre en premier est l'élément qui sort en premier.
Représentation FIFO de la file d'attente
Dans l'image ci-dessus, étant donné que 1 a été conservé dans la file d'attente avant 2, il est également le premier à être supprimé de la file d'attente. Il suit la règle FIFO .
En ce qui concerne la programmation, mettre des éléments dans la file d' attente est appelé enqueue et la suppression d' éléments de la file d' attente est appelé dequeue .
Nous pouvons implémenter la file d'attente dans n'importe quel langage de programmation comme C, C ++, Java, Python ou C #, mais la spécification est à peu près la même.
Opérations de base de la file d'attente
Une file d'attente est un objet (une structure de données abstraite - ADT) qui permet les opérations suivantes:
- Mettre en file d'attente: ajouter un élément à la fin de la file d'attente
- Dequeue : supprimer un élément de l'avant de la file d'attente
- IsEmpty : vérifier si la file d'attente est vide
- IsFull : vérifier si la file d'attente est pleine
- Coup d'oeil : obtenez la valeur de l'avant de la file d'attente sans le supprimer
Fonctionnement de la file d'attente
Les opérations de file d'attente fonctionnent comme suit:
- deux pointeurs AVANT et ARRIÈRE
- FRONT trace le premier élément de la file d'attente
- REAR suivre le dernier élément de la file d'attente
- initialement, définissez la valeur de FRONT et REAR sur -1
Opération de mise en file d'attente
- vérifier si la file d'attente est pleine
- pour le premier élément, définissez la valeur de FRONT sur 0
- augmenter l'indice REAR de 1
- ajouter le nouvel élément à la position pointée par REAR
Opération de retrait de la file d'attente
- vérifier si la file d'attente est vide
- renvoie la valeur pointée par FRONT
- augmenter l'indice FRONT de 1
- pour le dernier élément, remettez les valeurs de FRONT et REAR à -1
Opérations de mise en file d'attente et de retrait de la file d'attente
Implémentations de file d'attente en Python, Java, C et C ++
Nous utilisons généralement des tableaux pour implémenter des files d'attente en Java et C / ++. Dans le cas de Python, nous utilisons des listes.
Python Java C C ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear++; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )
Limitations de la file d'attente
Comme vous pouvez le voir dans l'image ci-dessous, après un peu de mise en file d'attente et de retrait de la file d'attente, la taille de la file d'attente a été réduite.
Limitation d'une file d'attente
Et nous ne pouvons ajouter les index 0 et 1 que lorsque la file d'attente est réinitialisée (lorsque tous les éléments ont été retirés de la file d'attente).
Une fois REAR atteint le dernier index, si nous pouvons stocker des éléments supplémentaires dans les espaces vides (0 et 1), nous pouvons utiliser les espaces vides. Ceci est mis en œuvre par une file d'attente modifiée appelée file d'attente circulaire.
Analyse de complexité
La complexité des opérations de mise en file d'attente et de retrait de la file d'attente dans une file d'attente à l'aide d'un tableau est de O(1).
Applications de la file d'attente
- Planification du processeur, planification du disque
- Lorsque les données sont transférées de manière asynchrone entre deux processus, la file d'attente est utilisée pour la synchronisation. Par exemple: tampons IO, tuyaux, fichier IO, etc.
- Gestion des interruptions dans les systèmes temps réel.
- Les systèmes téléphoniques du centre d'appels utilisent des files d'attente pour mettre en ordre les personnes qui les appellent.
Lectures recommandées
- Types de file d'attente
- File d'attente circulaire
- Structure des données Deque
- File d'attente de priorité
