TechCodeview

순환 대기열 개념이 도입된 이유는 무엇입니까?

배열 구현에는 한 가지 제한 사항이 있었습니다.

위 이미지에서 볼 수 있듯이 후면은 대기열의 마지막 위치에 있고 전면은 0이 아닌 어딘가를 가리키고 있습니다.^일위치. 위 배열에는 두 개의 요소만 있고 나머지 세 개의 위치는 비어 있습니다. 후면은 대기열의 마지막 위치에 있습니다. 요소를 삽입하려고 하면 대기열에 빈 공간이 없다는 메시지가 표시됩니다. 이러한 메모리 공간 낭비를 방지하는 한 가지 솔루션은 왼쪽의 두 요소를 모두 이동하고 그에 따라 앞뒤 끝을 조정하는 것입니다. 모든 요소를 ​​이동하는 데 많은 시간이 소요되기 때문에 이는 실질적으로 좋은 접근 방식이 아닙니다. 메모리 낭비를 피하기 위한 효율적인 접근 방식은 순환 대기열 데이터 구조를 사용하는 것입니다.

순환 대기열이란 무엇입니까?

원형 큐는 원을 형성하는 원형 큐의 마지막 위치가 첫 번째 위치에 연결된다는 점을 제외하면 FIFO(선입선출) 원칙을 기반으로 한다는 점에서 선형 큐와 유사합니다. 그것은 또한 링 버퍼 .

순환 대기열에 대한 작업

순환 큐에서 수행할 수 있는 작업은 다음과 같습니다.

앞쪽:대기열에서 맨 앞의 요소를 가져오는 데 사용됩니다.뒤쪽:대기열에서 뒤쪽 요소를 가져오는 데 사용됩니다.엔큐(값):이 함수는 대기열에 새 값을 삽입하는 데 사용됩니다. 새 요소는 항상 뒤쪽 끝에서 삽입됩니다.대기열 해제():이 함수는 대기열에서 요소를 삭제합니다. 대기열 삭제는 항상 프런트 엔드에서 발생합니다.

순환 대기열의 응용

순환 대기열은 다음 시나리오에서 사용할 수 있습니다.

메모리 관리:순환 큐는 메모리 관리를 제공합니다. 선형 큐에서는 이미 살펴보았듯이 메모리가 매우 효율적으로 관리되지 않습니다. 그러나 순환 큐의 경우에는 사용되지 않는 위치에 요소를 배치하여 메모리를 효율적으로 관리합니다.CPU 스케줄링:운영 체제는 또한 순환 대기열을 사용하여 프로세스를 삽입한 다음 실행합니다.교통 시스템:컴퓨터 제어 교통 시스템에서 신호등은 원형 대기열의 가장 좋은 예 중 하나입니다. 신호등의 각 신호등은 매 진 간격마다 하나씩 켜집니다. 빨간색 표시등이 1분 동안 켜진 다음 노란색 표시등이 1분 동안 켜진 다음 녹색 표시등이 켜집니다. 녹색등이 켜진 후 빨간색 표시등이 켜집니다.

대기열에 넣기 작업

Enqueue 작업 단계는 다음과 같습니다.

• 먼저 Queue가 꽉 찼는지 확인합니다.
• 처음에는 전면과 후면이 -1로 설정되어 있습니다. Queue에 첫 번째 요소를 삽입하면 앞과 뒤가 모두 0으로 설정됩니다.
• 새 요소를 삽입하면 뒤쪽이 증가합니다. 즉, 후면=후면+1 .

요소 삽입 시나리오

대기열이 가득 차지 않은 경우에는 두 가지 시나리오가 있습니다.

문자열을 길게

스캐너 다음

4단계: 출구

대기열에서 빼기 작업

대기열 제거 작업 단계는 다음과 같습니다.

• 먼저 Queue가 비어 있는지 확인합니다. 대기열이 비어 있으면 대기열 제거 작업을 수행할 수 없습니다.
• 요소가 삭제되면 front의 값이 1씩 감소합니다.
• 삭제할 요소가 하나만 남아 있으면 전면과 후면이 -1로 재설정됩니다.

순환 큐에서 요소를 삭제하는 알고리즘

1 단계: IF FRONT = -1
'UNDERFLOW'라고 쓰세요.
4단계로 이동
[IF 종료]

2 단계: 값 설정 = 대기열[앞]

3단계: 전면 = 후면인 경우
전면 설정 = 후면 = -1
또 다른
IF FRONT = 최대 -1
전면 설정 = 0
또 다른
전면 설정 = 전면 + 1
[IF 종료]
[IF 끝]

4단계: 출구

도식적 표현을 통해 대기열에 넣기와 대기열에서 빼기 작업을 이해해 보겠습니다.

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

산출:

크루스칼 알고리즘'