Semblable à la file d'attente, il s'agit d'une structure de données linéaire qui suit un ordre particulier dans lequel les opérations sont effectuées pour stocker les données. L'ordre est premier entré, premier sorti (FIFO) . On peut imaginer une file d'attente comme une file de personnes attendant de recevoir quelque chose dans un ordre séquentiel qui commence au début de la file. Il s'agit d'une liste ordonnée dans laquelle les insertions sont effectuées à une extrémité appelée arrière et les suppressions sont effectuées à partir de l'autre extrémité appelée avant. Un bon exemple de file d'attente est n'importe quelle file d'attente de consommateurs pour une ressource dans laquelle le consommateur arrivé en premier est servi en premier.
La différence entre les piles et les files d'attente réside dans la suppression. Dans une pile, nous supprimons l'élément le plus récemment ajouté ; dans une file d'attente, nous supprimons l'élément le moins récemment ajouté.
Structure des données de file d'attente
Opérations de base sur la file d'attente :
- enqueue() : insère un élément à la fin de la file d'attente, c'est-à-dire à l'arrière. dequeue() : Cette opération supprime et renvoie un élément qui se trouve au début de la file d'attente. front() : Cette opération renvoie l’élément au début sans le supprimer. Rear() : Cette opération renvoie l'élément à l'arrière sans le supprimer. isEmpty() : Cette opération indique si la file d'attente est vide ou non. isFull() : Cette opération indique si la file d'attente est pleine ou non. size() : Cette opération renvoie la taille de la file d'attente, c'est-à-dire le nombre total d'éléments qu'elle contient.
Types de files d'attente :
- File d'attente simple : la file d'attente simple, également connue sous le nom de file d'attente linéaire, est la version la plus basique d'une file d'attente. Ici, l'insertion d'un élément, c'est-à-dire l'opération de mise en file d'attente, a lieu à l'extrémité arrière et la suppression d'un élément, c'est-à-dire l'opération de retrait de la file d'attente, a lieu à l'extrémité avant. Ici, le problème est que si nous faisons apparaître un élément de l'avant puis de l'arrière jusqu'à la capacité de la file d'attente et bien qu'il y ait des espaces vides avant l'avant, cela signifie que la file d'attente n'est pas pleine, mais selon la condition de la fonction isFull(), cela montrera que le la file d'attente est alors pleine. Pour résoudre ce problème, nous utilisons une file d'attente circulaire.
- File d'attente circulaire : Dans une file d'attente circulaire, l'élément de la file d'attente agit comme un anneau circulaire. Le fonctionnement d'une file d'attente circulaire est similaire à celui d'une file d'attente linéaire à l'exception du fait que le dernier élément est connecté au premier élément. Son avantage est que la mémoire est mieux utilisée. En effet, s'il y a un espace vide, c'est-à-dire si aucun élément n'est présent à une certaine position dans la file d'attente, alors un élément peut être facilement ajouté à cette position en utilisant la capacité modulo ( %n ).
- File d'attente de priorité : Cette file d'attente est un type spécial de file d'attente. Sa spécialité est qu'il organise les éléments dans une file d'attente en fonction d'une certaine priorité. La priorité peut être quelque chose où l'élément avec la valeur la plus élevée a la priorité, ce qui crée une file d'attente avec un ordre décroissant de valeurs. La priorité peut également être telle que l'élément avec la valeur la plus basse obtient la priorité la plus élevée, ce qui crée à son tour une file d'attente avec un ordre croissant de valeurs. Dans la file d'attente de priorité prédéfinie, C++ donne la priorité à la valeur la plus élevée tandis que Java donne la priorité à la valeur la plus basse.
- Par conséquent : La suppression de la file d'attente est également connue sous le nom de file d'attente à double extrémité. Comme son nom l'indique, à double extrémité, cela signifie qu'un élément peut être inséré ou supprimé des deux extrémités de la file d'attente, contrairement aux autres files d'attente dans lesquelles cela ne peut être fait qu'à partir d'une seule extrémité. En raison de cette propriété, il peut ne pas obéir à la propriété First In First Out.
Applications de la file d'attente :
La file d'attente est utilisée lorsque les éléments ne doivent pas être traités immédiatement, mais doivent être traités dans F premier je n F premier Ô tu commande comme Recherche en largeur d'abord . Cette propriété de Queue le rend également utile dans les types de scénarios suivants.
- Lorsqu'une ressource est partagée entre plusieurs consommateurs. Les exemples incluent la planification du processeur et la planification des disques. Lorsque les données sont transférées de manière asynchrone (les données ne sont pas nécessairement reçues au même rythme que celles envoyées) entre deux processus. Les exemples incluent les tampons d'E/S, les canaux, les E/S de fichiers, etc. La file d'attente peut être utilisée comme composant essentiel dans diverses autres structures de données.
Implémentation du tableau de file d'attente :
Pour implémenter la file d'attente, nous devons garder une trace de deux index, avant et arrière. Nous mettons un élément en file d’attente à l’arrière et retirons un élément de la file d’attente à l’avant. Si nous incrémentons simplement les indices avant et arrière, alors il peut y avoir des problèmes, l'avant peut atteindre la fin du tableau. La solution à ce problème est d'augmenter l'avant et l'arrière de manière circulaire.
Étapes de mise en file d'attente :
- Vérifiez que la file d'attente est pleine ou non
- S'il est plein, imprimez le débordement et quittez
- Si la file d'attente n'est pas pleine, incrémentez tail et ajoutez l'élément
Étapes pour retirer la file d'attente :
- La file d'attente de vérification est vide ou non
- s'il est vide, imprimez le sous-débit et quittez
- s'il n'est pas vide, imprimer l'élément en tête et incrémenter la tête
Vous trouverez ci-dessous un programme pour implémenter l'opération ci-dessus sur la file d'attente
C++
chiffres romains de 1 à 100
// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->capacité = capacité;> >queue->front = file d'attente->taille = 0;> >// This is important, see the enqueue> >queue->arrière = capacité - 1;> >queue->tableau =>new> int>[queue->capacité];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->taille == file d'attente->capacité);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->taille == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->arrière = (file d'attente->arrière + 1)> >% queue->capacité;> >queue->array[file->arrière] = item;> >queue->taille = file d'attente->taille + 1;> >cout << item <<>' enqueued to queue
'>;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->array[file->front];> >queue->front = (file d'attente->front + 1)> >% queue->capacité;> >queue->taille = file d'attente->taille - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[file->front];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[file->arrière];> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>' dequeued from queue
'>;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra> |
>
>
C
// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->capacité = capacité;> >queue->front = file d'attente->taille = 0;> >// This is important, see the enqueue> >queue->arrière = capacité - 1;> >queue->tableau = (>int>*)>malloc>(> >queue->capacité *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->taille == file d'attente->capacité);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->taille == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->arrière = (file d'attente->arrière + 1)> >% queue->capacité;> >queue->array[file->arrière] = item;> >queue->taille = file d'attente->taille + 1;> >printf>(>'%d enqueued to queue
'>, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->array[file->front];> >queue->front = (file d'attente->front + 1)> >% queue->capacité;> >queue->taille = file d'attente->taille - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[file->front];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[file->arrière];> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>'%d dequeued from queue
'>,> >dequeue(queue));> >printf>(>'Front item is %d
'>, front(queue));> >printf>(>'Rear item is %d
'>, rear(queue));> >return> 0;> }> |
>
jsp
>
Java
// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>' dequeued from queue
'>);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani> |
>
>
Python3
décodage javascript base64
# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()> |
>
preg_match
>
C#
// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }> |
>
>
Javascript
> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> > |
>
>
latex dérivé partielSortir
10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>
Analyse de complexité :
- Complexité temporelle
| Opérations | Complexité |
|---|---|
| Mettre en file d'attente (insertion) | O(1) |
| Deque(suppression) | O(1) |
| Devant(Obtenir devant) | O(1) |
| Arrière (Obtenir l'arrière) | O(1) |
| IsFull (Vérifier que la file d'attente est pleine ou non) | O(1) |
| IsEmpty (Vérifier que la file d'attente est vide ou non) | O(1) |
- Espace auxiliaire :
O(N) où N est la taille du tableau pour stocker les éléments.
Avantages de la mise en œuvre de tableaux :
- Facile à mettre en œuvre.
- Une grande quantité de données peut être gérée efficacement et facilement.
- Les opérations telles que l'insertion et la suppression peuvent être effectuées facilement car elles suivent la règle du premier entré, premier sorti.
Inconvénients de la mise en œuvre d'un tableau :
- Structure de données statique, taille fixe.
- Si la file d'attente comporte un grand nombre d'opérations de mise en file d'attente et de retrait de la file d'attente, à un moment donné (en cas d'incrémentation linéaire des index avant et arrière), nous ne pourrons peut-être pas insérer d'éléments dans la file d'attente même si la file d'attente est vide (ce problème est évité en utilisant une file d'attente circulaire).
- La taille maximale d'une file d'attente doit être définie au préalable.