TechCodeview

Dlaczego wprowadzono koncepcję kolejki okrężnej?

Istniało jedno ograniczenie w implementacji tablicy

Jak widać na powyższym obrazku, tył znajduje się na ostatniej pozycji kolejki, a przód jest skierowany gdzieś, a nie na 0^tpozycja. W powyższej tablicy znajdują się tylko dwa elementy, a pozostałe trzy pozycje są puste. Tył znajduje się na ostatnim miejscu w kolejce; jeśli spróbujemy wstawić element, wyświetli się informacja, że ​​w kolejce nie ma pustych miejsc. Jest jedno rozwiązanie, które pozwala uniknąć takiego marnowania miejsca w pamięci, przesuwając oba elementy po lewej stronie i odpowiednio dopasowując przód i tył. Nie jest to praktycznie dobre podejście, ponieważ przesunięcie wszystkich elementów zajmie dużo czasu. Skutecznym sposobem uniknięcia marnowania pamięci jest użycie struktury danych kolejki cyklicznej.

Co to jest kolejka okrężna?

Kolejka okrężna jest podobna do kolejki liniowej, ponieważ również opiera się na zasadzie FIFO (pierwsze weszło, pierwsze wyszło), z tą różnicą, że ostatnia pozycja jest połączona z pierwszą pozycją w kolejce kołowej, która tworzy okrąg. Znany jest również jako Bufor pierścieniowy .

Operacje na kolejce cyklicznej

Poniżej przedstawiono operacje, które można wykonać na kolejce cyklicznej:

Przód:Służy do pobrania elementu frontowego z kolejki.Tył:Służy do pobrania tylnego elementu z kolejki.w kolejce(wartość):Ta funkcja służy do wstawienia nowej wartości do kolejki. Nowy element jest zawsze wstawiany od tyłu.usuńkolejkę():Ta funkcja usuwa element z kolejki. Usuwanie w kolejce zawsze odbywa się od frontu.

Zastosowania kolejki okrężnej

Kolejki cyklicznej można używać w następujących scenariuszach:

nfa do dfa

c wartość logiczna

Krok 3: USTAW KOLEJKĘ[TYŁ] = WARTOŚĆ

jądro mikrolityczne

Krok 4: WYJŚCIE

Operacja usuwania z kolejki

Poniżej przedstawiono kroki operacji usuwania z kolejki:

• Najpierw sprawdzamy, czy kolejka jest pusta, czy nie. Jeśli kolejka jest pusta, nie możemy wykonać operacji usunięcia z kolejki.
• Po usunięciu elementu wartość frontu zmniejsza się o 1.
• Jeżeli do usunięcia pozostał tylko jeden element, wówczas przód i tył są resetowane do -1.

Algorytm usuwania elementu z kolejki cyklicznej

Krok 1: JEŚLI PRZÓD = -1
Napisz „NIEDOM”
Przejdź do kroku 4
[KONIEC JEŻELI]

Krok 2: USTAW WARTOŚĆ = KOLEJKA[PRZÓD]

Krok 3: JEŚLI PRZÓD = TYŁ
USTAW PRZÓD = TYŁ = -1
W PRZECIWNYM RAZIE
JEŚLI PRZÓD = MAKS. -1
USTAW PRZÓD = 0
W PRZECIWNYM RAZIE
USTAW PRZÓD = PRZÓD + 1
[KONIEC JEŻELI]
[KONIEC JEŚLI]

jeśli inaczej, jeśli Java

Krok 4: WYJŚCIE

Przyjrzyjmy się operacji umieszczania i usuwania z kolejki poprzez przedstawienie schematyczne.

Implementacja kolejki cyklicznej przy użyciu 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)>

Wyjście: