logo

TechCodeview

Pyöreä jono

Miksi pyöreän jonon käsite otettiin käyttöön?

Matriisin toteutuksessa oli yksi rajoitus

Kuten yllä olevasta kuvasta näemme, takaosa on jonon viimeisessä kohdassa ja etuosa osoittaa jonnekin 0:n sijaanthasema. Yllä olevassa taulukossa on vain kaksi elementtiä ja kolme muuta paikkaa ovat tyhjiä. Takaosa on jonon viimeisessä kohdassa; jos yritämme lisätä elementin, se näyttää, että jonossa ei ole tyhjiä tiloja. On olemassa yksi ratkaisu, jolla vältetään tällainen muistitilan tuhlaus siirtämällä molempia elementtejä vasemmalle ja säätämällä etu- ja takapäätä vastaavasti. Se ei ole käytännössä hyvä lähestymistapa, koska kaikkien elementtien siirtäminen vie paljon aikaa. Tehokas tapa välttää muistin tuhlausta on käyttää ympyränmuotoista jonotietorakennetta.

Mikä on pyöreä jono?

Pyöreä jono on samanlainen kuin lineaarinen jono, koska se perustuu myös FIFO (First In First Out) -periaatteeseen, paitsi että viimeinen paikka on yhdistetty ympyränmuotoisen jonon ensimmäiseen paikkaan. Se tunnetaan myös nimellä a Soittopuskuri .

Toiminnot pyöreässä jonossa

Seuraavat ovat toiminnot, jotka voidaan suorittaa pyöreässä jonossa:

    Edessä:Sitä käytetään etuelementin hakemiseen jonosta.Takaosa:Sitä käytetään takaelementin hakemiseen jonosta.enQueue(arvo):Tätä toimintoa käytetään uuden arvon lisäämiseen jonoon. Uusi elementti asetetaan aina takapäästä.deQueue():Tämä toiminto poistaa elementin jonosta. Poisto jonossa tapahtuu aina etupäästä.

Circular Queue -sovellukset

Pyöreää jonoa voidaan käyttää seuraavissa tilanteissa:

    Muistin hallinta:Pyöreä jono tarjoaa muistinhallinnan. Kuten olemme jo nähneet, että lineaarisessa jonossa muistia ei hallita kovin tehokkaasti. Mutta pyöreän jonon tapauksessa muistia hallitaan tehokkaasti sijoittamalla elementit käyttämättömään paikkaan.CPU-aikataulu:Käyttöjärjestelmä käyttää myös pyöreää jonoa prosessien lisäämiseen ja niiden suorittamiseen.Liikennejärjestelmä:Tietokoneohjatussa liikennejärjestelmässä liikennevalo on yksi parhaista esimerkeistä pyöreästä jonosta. Jokainen liikennevalon valo syttyy yksitellen jokaisen aikajakson jälkeen. Kuten punainen valo syttyy minuutiksi, sitten keltainen valo minuutiksi ja sitten vihreä valo. Vihreän valon jälkeen punainen valo syttyy.

Jonotoiminto

Jonotoiminnan vaiheet on annettu alla:

  • Ensin tarkistamme, onko jono täynnä vai ei.
  • Aluksi etu- ja takaosa asetetaan arvoon -1. Kun lisäämme ensimmäisen elementin jonoon, sekä etu- että takaosa asetetaan arvoon 0.
  • Kun lisäämme uuden elementin, takaosa kasvaa, ts. taka=taka+1 .

Skenaariot elementin lisäämiseksi

On olemassa kaksi skenaariota, joissa jono ei ole täynnä:

    Jos takana != max - 1, sitten takaosa kasvaa arvoon mod (maksimikoko) ja uusi arvo lisätään jonon takapäähän.Jos edessä ! = 0 ja takana = max - 1, se tarkoittaa, että jono ei ole täynnä, aseta sitten takaosan arvoksi 0 ja lisää uusi elementti sinne.

On kaksi tapausta, joissa elementtiä ei voi lisätä:

  • Kun edessä ==0 && takana = max-1 , mikä tarkoittaa, että etu on jonon ensimmäisessä kohdassa ja takaosa jonon viimeisessä kohdassa.
  • edessä== takana + 1;

Algoritmi elementin lisäämiseksi pyöreään jonoon

Vaihe 1: JOS (TAKA+1)%MAX = ETUSSA
Kirjoita 'OVERFLOW'
Siirry vaiheeseen 4
[JOS LOPPU]

Vaihe 2: JOS ETEEN = -1 ja TAKA = -1
SET ETEEN = TAKA = 0
MUUTA JOS TAKA = MAX - 1 ja ETEEN ! = 0
SET REAR = 0
MUU
SET REAR = (REAR + 1) % MAX
[JOS LOPPU]

Vaihe 3: SET QUEUE[REAR] = VAL

Vaihe 4: POISTU

Poista jonosta -toiminto

Jonosta poistamisen vaiheet on esitetty alla:

  • Tarkistamme ensin, onko jono tyhjä vai ei. Jos jono on tyhjä, emme voi suorittaa poistotoimintoa.
  • Kun elementti poistetaan, frontin arvoa pienennetään yhdellä.
  • Jos jäljellä on vain yksi poistettava elementti, etu- ja takaosa palautetaan arvoon -1.

Algoritmi elementin poistamiseksi pyöreästä jonosta

Vaihe 1: JOS ETEEN = -1
Kirjoita 'ALIVUOTO'
Siirry vaiheeseen 4
[JOS LOPPU]

Vaihe 2: SET VAL = JONO[ETTU]

Vaihe 3: JOS ETEEN = TAKA
SET ETEEN = TAKA = -1
MUU
JOS ETEEN = MAX -1
SET FRONT = 0
MUU
SET FRONT = ETU + 1
[JOS LOPPU]
[JOS LOPPU]

Vaihe 4: POISTU

Ymmärretään jono- ja dequeue-toiminto kaaviomaisen esityksen kautta.

Pyöreä jono
Pyöreä jono
Pyöreä jono
Pyöreä jono
Pyöreä jono
Pyöreä jono
Pyöreä jono
Pyöreä jono

Pyöreän jonon toteutus Arraylla

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

Lähtö:

preg_match
Pyöreä jono