DS KÖRKÖRÖS SOR - DS OKTATÓANYAG

Miért vezették be a körkörös sor fogalmát?

Volt egy korlátozás a tömb megvalósításában

Amint a fenti képen láthatjuk, a hátsó rész a sor utolsó pozíciójában van, és az elülső valahova mutat, nem pedig a 0-ra.^thpozíció. A fenti tömbben csak két elem van, a másik három pozíció pedig üres. A hátsó rész a sor utolsó helyén van; Ha megpróbáljuk beszúrni az elemet, akkor azt fogja mutatni, hogy nincsenek üres helyek a Queue-ban. Van egy megoldás a memória ilyen pazarlásának elkerülésére, ha mindkét elemet balra tolja, és ennek megfelelően állítja be az elülső és a hátsó részt. Gyakorlatilag nem jó megközelítés, mert az összes elem áthelyezése sok időt vesz igénybe. A memóriapazarlás elkerülésének hatékony módja a körkörös adatstruktúra használata.

Mi az a körkörös várólista?

A kör alakú sor hasonló a lineáris sorhoz, mivel szintén a FIFO (First In First Out) elven alapul, azzal a különbséggel, hogy az utolsó pozíció egy kör alakú sor első pozíciójához kapcsolódik, amely kört alkot. Más néven a Csengetési puffer .

Műveletek a körkörös sorban

A körkörös sorban végrehajtható műveletek a következők:

Elülső:Ez arra szolgál, hogy az elülső elemet lekérje a Queue-ból.Hátulsó:A hátsó elem lekérésére szolgál a Queue-ból.enQueue(érték):Ez a függvény az új érték beszúrására szolgál a sorba. Az új elemet mindig a hátulról kell beilleszteni.deQueue():Ez a függvény egy elemet töröl a sorból. A várólista törlése mindig az előoldalról történik.

A Circular Queue alkalmazásai

A kör alakú várólista a következő forgatókönyvekben használható:

Memóriakezelés:A kör alakú sor memóriakezelést biztosít. Amint azt már láttuk, a lineáris sorban a memória kezelése nem túl hatékony. De körkörös sor esetén a memória hatékony kezelése úgy történik, hogy az elemeket nem használt helyre helyezik.CPU ütemezés:Az operációs rendszer a körkörös sort is használja a folyamatok beszúrására, majd végrehajtására.Közlekedési rendszer:Egy számítógépes forgalomirányítási rendszerben a jelzőlámpa a kör alakú sor egyik legjobb példája. Minden közlekedési lámpa egyenként kigyullad minden időintervallum után. Mintha egy percre a piros lámpa világítana, majd egy percre a sárga, majd a zöld fény. Zöld lámpa után a piros lámpa kigyullad.

Sorba állítás művelet

Az enqueue művelet lépései az alábbiak:

Először is ellenőrizzük, hogy a várólista megtelt-e vagy sem.
Kezdetben az első és a hátsó rész -1-re van állítva. Amikor beszúrjuk az első elemet egy sorba, az elülső és a hátsó elem egyaránt 0 lesz.
Amikor új elemet helyezünk be, a hátsó rész növekszik, azaz hátsó=hátsó+1 .

Egy elem beszúrásának forgatókönyvei

Két forgatókönyv létezik, amikor a várólista nem tele:

mod (maximális)

Két olyan eset van, amikor az elem nem illeszthető be:

Amikor elöl ==0 && hátsó = max-1 , ami azt jelenti, hogy az elülső a sor első pozíciójában, a hátsó pedig a sor utolsó pozíciójában van.
elöl== hátsó + 1;

Algoritmus elem beszúrására egy kör alakú sorba

1. lépés: IF (HÁTSÓ+1)%MAX = ELSŐ
Írja be: 'OVERFLOW'
Ugrás a 4. lépésre
[HA VÉGE]

2. lépés: HA ELSŐ = -1 és HÁTSÓ = -1
ELSŐ BEÁLLÍTÁS = HÁTSÓ = 0
EGYÉB HA HÁTSÓ = MAX - 1 és ELSŐ ! = 0
HÁTSÓ BEÁLLÍTÁS = 0
MÁS
HÁTSÓ BEÁLLÍTÁS = (HÁTSÓ + 1) % MAX
[HA VÉGE]

3. lépés: SET QUEUE[REAR] = VAL

4. lépés: KIJÁRAT

Dequeue művelet

Az alábbiakban a sorból való kilépés lépései láthatók:

Először is ellenőrizzük, hogy a sor üres-e vagy sem. Ha a várólista üres, nem tudjuk végrehajtani a dequeue műveletet.
Az elem törlésekor a front értéke 1-gyel csökken.
Ha csak egy elem maradt, amelyet törölni kell, akkor az elülső és a hátsó rész visszaáll -1-re.

Algoritmus egy elem törlésére a kör alakú sorból

1. lépés: HA ELSŐ = -1
Írja be: 'ALACSÚJTÁS'
Lépjen a 4. lépésre
[HA VÉGE]

2. lépés: ÉRTÉK BEÁLLÍTÁSA = QUEUE[FRONT]

3. lépés: HA ELSŐ = HÁTSÓ
ELSŐ BEÁLLÍTÁS = HÁTSÓ = -1
MÁS
HA ELSŐ = MAX -1
ELSŐ BEÁLLÍTÁS = 0
MÁS
ELSŐ BEÁLLÍTÁS = FRONT + 1
[HA VÉGE]
[HA VÉGE]

4. lépés: KIJÁRAT

Értsük meg a sorbaállítás és a dequeue műveletet a diagrammatikus ábrázoláson keresztül.

Kör alakú sor megvalósítása tömb segítségével

 #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)>

Kimenet:

TechCodeview

Körkörös sor