Perché è stato introdotto il concetto di coda circolare?

C'era una limitazione nell'implementazione dell'array di

Come possiamo vedere nell'immagine sopra, la parte posteriore è nell'ultima posizione della coda e la parte anteriore punta da qualche parte anziché dallo 0^thposizione. Nell'array sopra ci sono solo due elementi e le altre tre posizioni sono vuote. Il retro è l'ultima posizione della coda; se proviamo a inserire l'elemento allora mostrerà che non ci sono spazi vuoti nella Coda. Esiste una soluzione per evitare tale spreco di spazio di memoria spostando entrambi gli elementi a sinistra e regolando di conseguenza la parte anteriore e quella posteriore. Non è un approccio praticamente valido perché lo spostamento di tutti gli elementi richiederà molto tempo. L'approccio efficiente per evitare lo spreco di memoria è utilizzare la struttura dati della coda circolare.

Cos'è una coda circolare?

Una coda circolare è simile a una coda lineare poiché anch'essa si basa sul principio FIFO (First In First Out), tranne per il fatto che l'ultima posizione è collegata alla prima posizione in una coda circolare che forma un cerchio. È noto anche come a Buffer ad anello .

lungo da infilare

seleziona multitabella sql

Passaggio 4: USCITA

Operazione di rimozione della coda

Di seguito sono riportati i passaggi dell'operazione di rimozione dalla coda:

• Innanzitutto controlliamo se la coda è vuota o meno. Se la coda è vuota, non possiamo eseguire l'operazione di rimozione dalla coda.
• Quando l'elemento viene eliminato, il valore di front viene diminuito di 1.
• Se è rimasto solo un elemento da eliminare, la parte anteriore e quella posteriore vengono ripristinate a -1.

Algoritmo per eliminare un elemento dalla coda circolare

Passo 1: SE FRONTE = -1
Scrivi 'UNDERFLOW'
Vai al passaggio 4
[FINE di SE]

Passo 2: IMPOSTA VAL = CODA[FRONTE]

Passaggio 3: SE ANTERIORE = POSTERIORE
IMPOSTA ANTERIORE = POSTERIORE = -1
ALTRO
SE FRONTE = MAX -1
IMPOSTA FRONTE = 0
ALTRO
IMPOSTA DAVANTI = DAVANTI + 1
[FINE di SE]
[FINE SE]

Passaggio 4: USCITA

Comprendiamo l'operazione di accodamento e deaccodamento attraverso la rappresentazione schematica.

Implementazione della coda circolare utilizzando 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 && 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('Queue is overflow..'); } 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) && (rear==-1)) // condition to check queue is empty { printf('
Queue is underflow..'); } else if(front==rear) { printf('
The dequeued element is %d', queue[front]); front=-1; rear=-1; } else { printf('
The dequeued element is %d', queue[front]); front=(front+1)%max; } } // function to display the elements of a queue void display() { int i=front; if(front==-1 && rear==-1) { printf('
 Queue is empty..'); } else { printf('
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)>

Produzione: