FILE D'ATTENTE CIRCULAIRE DS

Pourquoi le concept de file d’attente circulaire a-t-il été introduit ?

Il y avait une limitation dans l'implémentation du tableau de

Comme nous pouvons le voir sur l'image ci-dessus, l'arrière est à la dernière position de la file d'attente et l'avant pointe quelque part plutôt que le 0.^èmeposition. Dans le tableau ci-dessus, il n’y a que deux éléments et les trois autres positions sont vides. L'arrière est à la dernière position de la file d'attente ; si nous essayons d'insérer l'élément, cela montrera qu'il n'y a pas d'espace vide dans la file d'attente. Il existe une solution pour éviter un tel gaspillage d'espace mémoire en déplaçant les deux éléments vers la gauche et en ajustant l'avant et l'arrière en conséquence. Ce n’est pas une bonne approche en pratique car déplacer tous les éléments prendra beaucoup de temps. L’approche efficace pour éviter le gaspillage de mémoire consiste à utiliser la structure de données de file d’attente circulaire.

Qu'est-ce qu'une file d'attente circulaire ?

Une file d'attente circulaire est similaire à une file d'attente linéaire car elle est également basée sur le principe FIFO (First In First Out) sauf que la dernière position est connectée à la première position dans une file d'attente circulaire qui forme un cercle. Il est également connu sous le nom de Tampon annulaire .

Opérations sur la file d'attente circulaire

Voici les opérations qui peuvent être effectuées sur une file d'attente circulaire :

Devant:Il est utilisé pour obtenir l'élément avant de la file d'attente.Arrière:Il est utilisé pour récupérer l'élément arrière de la file d'attente.enQueue (valeur):Cette fonction permet d'insérer la nouvelle valeur dans la file d'attente. Le nouvel élément est toujours inséré par l'arrière.deQueue():Cette fonction supprime un élément de la file d'attente. La suppression dans une file d'attente s'effectue toujours depuis le front-end.

Applications de la file d'attente circulaire

La file d'attente circulaire peut être utilisée dans les scénarios suivants :

Rakhi Sawant

Gestion de la mémoire:La file d'attente circulaire assure la gestion de la mémoire. Comme nous l'avons déjà vu, dans une file d'attente linéaire, la mémoire n'est pas gérée de manière très efficace. Mais dans le cas d'une file d'attente circulaire, la mémoire est gérée efficacement en plaçant les éléments dans un emplacement qui n'est pas utilisé.Planification du processeur :Le système d'exploitation utilise également la file d'attente circulaire pour insérer les processus puis les exécuter.Système de circulation :Dans un système de circulation contrôlé par ordinateur, le feu de circulation est l'un des meilleurs exemples de file d'attente circulaire. Chaque feu de circulation s'allume un par un après chaque intervalle de temps. Par exemple, la lumière rouge s'allume pendant une minute, puis la lumière jaune pendant une minute, puis la lumière verte. Après le feu vert, le voyant rouge s'allume.

Opération de mise en file d'attente

Les étapes de l’opération de mise en file d’attente sont indiquées ci-dessous :

Tout d’abord, nous vérifierons si la file d’attente est pleine ou non.
Initialement, l'avant et l'arrière sont réglés sur -1. Lorsque nous insérons le premier élément dans une file d'attente, l'avant et l'arrière sont tous deux définis sur 0.
Lorsque nous insérons un nouvel élément, l'arrière est incrémenté, c'est-à-dire arrière=arrière+1 .

Scénarios d'insertion d'un élément

Il existe deux scénarios dans lesquels la file d'attente n'est pas pleine :

mod (taille maximale)

Il existe deux cas dans lesquels l'élément ne peut pas être inséré :

Quand devant ==0 && arrière = max-1 , ce qui signifie que l'avant est à la première position de la file d'attente et l'arrière est à la dernière position de la file d'attente.
avant== arrière + 1 ;

Algorithme pour insérer un élément dans une file d'attente circulaire

Étape 1: SI (ARRIÈRE+1)%MAX = AVANT
Écrivez « DÉBORDEMENT »
Passer à l'étape 4
[Fin DE SI]

Étape 2: SI AVANT = -1 et ARRIÈRE = -1
RÉGLER AVANT = ARRIÈRE = 0
AUTRE SI ARRIÈRE = MAX - 1 et AVANT ! = 0
RÉGLER ARRIÈRE = 0
AUTRE
RÉGLAGE ARRIÈRE = (ARRIÈRE + 1) % MAX
[FIN DE SI]

chaîne java.format

Étape 3: FIXER LA FILE[ARRIÈRE] = VAL

nom des produits de maquillage

Étape 4: SORTIE

Opération de retrait de la file d'attente

Les étapes de l’opération de retrait de la file d’attente sont indiquées ci-dessous :

Tout d'abord, nous vérifions si la file d'attente est vide ou non. Si la file d'attente est vide, nous ne pouvons pas effectuer l'opération de retrait de la file d'attente.
Lorsque l'élément est supprimé, la valeur de front est décrémentée de 1.
S'il ne reste qu'un seul élément à supprimer, alors l'avant et l'arrière sont remis à -1.

Algorithme pour supprimer un élément de la file d'attente circulaire

Étape 1: SI DEVANT = -1
Écrivez « SOUS-COULEMENT »
Passer à l'étape 4
[FIN de SI]

Étape 2: SET VAL = QUEUE[AVANT]

Étape 3: SI AVANT = ARRIÈRE
RÉGLER AVANT = ARRIÈRE = -1
AUTRE
SI AVANT = MAX -1
DÉFINIR L'AVANT = 0
AUTRE
RÉGLER DEVANT = DEVANT + 1
[FIN de SI]
[FIN DE SI]

CSS alignant les images

Étape 4: SORTIE

Comprenons l'opération de mise en file d'attente et de retrait de la file d'attente à travers la représentation schématique.

Implémentation d'une file d'attente circulaire à l'aide de Array

 #include # define max 6 int queue[max]; // array declaration int front=-1; int rear=-1; // function to insert an element in a circular queue void enqueue(int element) { if(front==-1 &amp;&amp; rear==-1) // condition to check queue is empty { front=0; rear=0; queue[rear]=element; } else if((rear+1)%max==front) // condition to check queue is full { printf(&apos;Queue is overflow..&apos;); } else { rear=(rear+1)%max; // rear is incremented queue[rear]=element; // assigning a value to the queue at the rear position. } } // function to delete the element from the queue int dequeue() { if((front==-1) &amp;&amp; (rear==-1)) // condition to check queue is empty { printf(&apos;
Queue is underflow..&apos;); } else if(front==rear) { printf(&apos;
The dequeued element is %d&apos;, queue[front]); front=-1; rear=-1; } else { printf(&apos;
The dequeued element is %d&apos;, queue[front]); front=(front+1)%max; } } // function to display the elements of a queue void display() { int i=front; if(front==-1 &amp;&amp; rear==-1) { printf(&apos;
 Queue is empty..&apos;); } else { printf(&apos;
Elements in a Queue are :&apos;); while(i<=rear) { printf('%d,', queue[i]); i="(i+1)%max;" } int main() choice="1,x;" variables declaration while(choice<4 && choice!="0)" while loop printf('
 press 1: insert an element'); printf('
press 2: delete 3: display the printf('
enter your choice'); scanf('%d', &choice); switch(choice) case printf('enter element which is to be inserted'); &x); enqueue(x); break; dequeue(); display(); }} return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/14/circular-queue-10.webp" alt="Circular Queue"> <h3>Implementation of circular queue using linked list</h3> <p>As we know that linked list is a linear data structure that stores two parts, i.e., data part and the address part where address part contains the address of the next node. Here, linked list is used to implement the circular queue; therefore, the linked list follows the properties of the Queue. When we are implementing the circular queue using linked list then both the <strong> <em>enqueue and dequeue</em> </strong> operations take <strong> <em>O(1)</em> </strong> time.</p> <pre> #include // Declaration of struct type node struct node { int data; struct node *next; }; struct node *front=-1; struct node *rear=-1; // function to insert the element in the Queue void enqueue(int x) { struct node *newnode; // declaration of pointer of struct node type. newnode=(struct node *)malloc(sizeof(struct node)); // allocating the memory to the newnode newnode-&gt;data=x; newnode-&gt;next=0; if(rear==-1) // checking whether the Queue is empty or not. { front=rear=newnode; rear-&gt;next=front; } else { rear-&gt;next=newnode; rear=newnode; rear-&gt;next=front; } } // function to delete the element from the queue void dequeue() { struct node *temp; // declaration of pointer of node type temp=front; if((front==-1)&amp;&amp;(rear==-1)) // checking whether the queue is empty or not { printf(&apos;
Queue is empty&apos;); } else if(front==rear) // checking whether the single element is left in the queue { front=rear=-1; free(temp); } else { front=front-&gt;next; rear-&gt;next=front; free(temp); } } // function to get the front of the queue int peek() { if((front==-1) &amp;&amp;(rear==-1)) { printf(&apos;
Queue is empty&apos;); } else { printf(&apos;
The front element is %d&apos;, front-&gt;data); } } // function to display all the elements of the queue void display() { struct node *temp; temp=front; printf(&apos;
 The elements in a Queue are : &apos;); if((front==-1) &amp;&amp; (rear==-1)) { printf(&apos;Queue is empty&apos;); } else { while(temp-&gt;next!=front) { printf(&apos;%d,&apos;, temp-&gt;data); temp=temp-&gt;next; } printf(&apos;%d&apos;, temp-&gt;data); } } void main() { enqueue(34); enqueue(10); enqueue(23); display(); dequeue(); peek(); } </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/14/circular-queue-11.webp" alt="Circular Queue"> <hr></=rear)>

Sortir:

TechCodeview