DS APĻVEIDA RINDA - DS APMĀCĪBA

Kāpēc tika ieviesta apļveida rindas koncepcija?

Masīva ieviešanā bija viens ierobežojums

Kā redzams iepriekš redzamajā attēlā, aizmugure atrodas rindas pēdējā pozīcijā un priekšpuse ir vērsta kaut kur, nevis 0.^thpozīciju. Iepriekš minētajā masīvā ir tikai divi elementi, un pārējās trīs pozīcijas ir tukšas. Aizmugure atrodas rindas pēdējā pozīcijā; ja mēģināsim ievietot elementu, tas parādīs, ka rindā nav tukšu vietu. Ir viens risinājums, kā izvairīties no šādas atmiņas vietas izšķērdēšanas, pārvietojot abus elementus pa kreisi un attiecīgi pielāgojot priekšējo un aizmugurējo daļu. Tā nav praktiski laba pieeja, jo visu elementu pārvietošana patērēs daudz laika. Efektīva pieeja, lai izvairītos no atmiņas izšķērdēšanas, ir izmantot apļveida rindu datu struktūru.

Kas ir apļveida rinda?

Apļveida rinda ir līdzīga lineārajai rindai, jo arī tās pamatā ir FIFO (First In First Out) princips, izņemot to, ka pēdējā pozīcija ir savienota ar pirmo pozīciju apļveida rindā, kas veido apli. Tas ir pazīstams arī kā a Zvana buferis .

Darbības apļveida rindā

Tālāk ir norādītas darbības, kuras var veikt apļveida rindā.

Priekšpuse:To izmanto, lai iegūtu priekšējo elementu no rindas.Aizmugure:To izmanto, lai no rindas iegūtu aizmugurējo elementu.enQueue(vērtība):Šī funkcija tiek izmantota, lai rindā ievietotu jauno vērtību. Jaunais elements vienmēr tiek ievietots no aizmugures.derinda():Šī funkcija izdzēš elementu no rindas. Dzēšana rindā vienmēr notiek no priekšpuses.

Apļveida rindas lietojumprogrammas

Apļveida rindu var izmantot šādos gadījumos:

Atmiņas pārvaldība:Apļveida rinda nodrošina atmiņas pārvaldību. Kā mēs jau redzējām, lineārajā rindā atmiņa netiek pārvaldīta ļoti efektīvi. Bet apļveida rindas gadījumā atmiņa tiek pārvaldīta efektīvi, ievietojot elementus vietā, kas netiek izmantota.CPU plānošana:Operētājsistēma izmanto arī apļveida rindu, lai ievietotu procesus un pēc tam tos izpildītu.Satiksmes sistēma:Datorvadītā satiksmes sistēmā luksofors ir viens no labākajiem apļveida rindas piemēriem. Katrs luksofora signāls iedegas pa vienam ik pēc laika intervāla. Tāpat kā sarkanā gaisma iedegas vienu minūti, tad dzeltena gaisma uz vienu minūti un tad zaļa gaisma. Pēc zaļās gaismas iedegas sarkanā gaisma.

Darbība rindā

Tālāk ir norādītas rindas darbības darbības.

Pirmkārt, mēs pārbaudīsim, vai rinda ir pilna.
Sākotnēji priekšpuse un aizmugure ir iestatīta uz -1. Kad rindā ievietojam pirmo elementu, gan priekšējais, gan aizmugurējais tiek iestatīts uz 0.
Ievietojot jaunu elementu, aizmugure tiek palielināta, t.i., aizmugure=aizmugure+1 .

Scenāriji elementa ievietošanai

Ir divi scenāriji, kad rinda nav pilna:

mod (maksimālais izmērs)

Ir divi gadījumi, kad elementu nevar ievietot:

Kad priekšā ==0 && aizmugurē = max-1 , kas nozīmē, ka priekšpuse atrodas rindas pirmajā pozīcijā un aizmugure atrodas rindas pēdējā pozīcijā.
priekšpuse== aizmugure + 1;

Algoritms elementa ievietošanai apļveida rindā

1. darbība: JA (REAR+1)%MAX = PRIEKŠĒJĀ
Uzrakstiet 'PĀRPLŪDE'
Pārejiet uz 4. darbību
[IF BEIGAS]

2. darbība: JA PRIEKŠĒJĀ = -1 un AIZMUGURĒ = -1
IESTATĪT PRIEKŠU = AIZMUGURES = 0
CITĀRT, JA AIZMUGURĒJĀ = MAX-1 un PRIEKŠĒJĀ! = 0
IESTATĪT AIZMUGURU = 0
CITS
IESTATĪT AIZMUGURĒJU = (REAR + 1) % MAX
[JA BEIGAS]

3. darbība: SET QUEUE[REAR] = VAL

4. darbība: IZEJA

Atcelšanas darbība

Tālāk ir norādīti izslēgšanas darbības soļi:

Pirmkārt, mēs pārbaudām, vai rinda ir tukša. Ja rinda ir tukša, mēs nevaram veikt izņemšanas darbību.
Kad elements tiek dzēsts, frontes vērtība tiek samazināta par 1.
Ja ir palicis tikai viens dzēšams elements, priekšpuse un aizmugure tiek atiestatīta uz -1.

Algoritms elementa dzēšanai no apļveida rindas

1. darbība: JA PRIEKŠĒJĀ = -1
Uzrakstiet 'UNDERFLOW'
Pārejiet uz 4. darbību
[IF END]

2. darbība: SET VAL = RINDA[PRIEKŠĒJĀ]

3. darbība: JA PRIEKŠĒJĀ = AIZMUGURĒJĀ
IESTATĪT PRIEKŠĒJĀ = AIZMUGURES = -1
CITS
JA PRIEKŠĒJĀ = MAX -1
SET FRONT = 0
CITS
SET FRONT = FRONT + 1
[IF END]
[JA BEIGAS]

4. darbība: IZEJA

Sapratīsim rindu un rindas darbību, izmantojot diagrammu.

Apļveida rindas ieviešana, izmantojot masīvu

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

Izvade:

virkne tērzēšanai