Por que foi introduzido o conceito de fila circular?
Houve uma limitação na implementação do array de
Como podemos ver na imagem acima, a parte traseira está na última posição da fila e a frente está apontando para algum lugar ao invés de 0ºposição. Na matriz acima, existem apenas dois elementos e outras três posições estão vazias. A retaguarda está na última posição da Fila; se tentarmos inserir o elemento, isso mostrará que não há espaços vazios na fila. Existe uma solução para evitar esse desperdício de espaço de memória, deslocando ambos os elementos à esquerda e ajustando a extremidade dianteira e traseira de acordo. Não é uma abordagem praticamente boa porque mudar todos os elementos consumirá muito tempo. A abordagem eficiente para evitar o desperdício de memória é usar a estrutura de dados da fila circular.
O que é uma fila circular?
Uma fila circular é semelhante a uma fila linear, pois também se baseia no princípio FIFO (First In First Out), exceto que a última posição está conectada à primeira posição em uma fila circular que forma um círculo. Também é conhecido como Buffer de anel .
Operações na fila circular
A seguir estão as operações que podem ser executadas em uma fila circular:
Aplicações de Fila Circular
A fila circular pode ser usada nos seguintes cenários:
Operação de enfileiramento
As etapas da operação de enfileiramento são fornecidas abaixo:
- Primeiramente verificaremos se a Fila está cheia ou não.
- Inicialmente, a frente e a traseira são definidas como -1. Quando inserimos o primeiro elemento em uma Queue, front e rear são definidos como 0.
- Quando inserimos um novo elemento, a parte traseira é incrementada, ou seja, traseira=traseira+1 .
Cenários para inserir um elemento
Existem dois cenários em que a fila não está cheia:
Existem dois casos em que o elemento não pode ser inserido:
- Quando frente ==0 && traseira = máx-1 , o que significa que a frente está na primeira posição da Fila e a retaguarda está na última posição da Fila.
- frente== traseira + 1;
Algoritmo para inserir um elemento em uma fila circular
memória virtual
Passo 1: SE (TRASEIRO+1)%MAX = FRENTE
Escreva 'OVERFLOW'
Vá para a etapa 4
[Fim DE SE]
Passo 2: SE FRENTE = -1 e TRASEIRA = -1
DEFINIR FRENTE = TRASEIRA = 0
ELSE SE TRASEIRO = MAX - 1 e FRENTE! = 0
DEFINIR TRASEIRA = 0
OUTRO
DEFINIR TRASEIRA = (TRASEIRA + 1)% MÁX.
[FIM DO SE]
Etapa 3: DEFINIR QUEUE[REAR] = VAL
Passo 4: SAÍDA
Operação de desenfileiramento
As etapas da operação de desenfileiramento são fornecidas abaixo:
- Primeiro, verificamos se a Fila está vazia ou não. Se a fila estiver vazia, não poderemos realizar a operação de desenfileiramento.
- Quando o elemento é excluído, o valor de front é diminuído em 1.
- Se houver apenas um elemento restante que deve ser excluído, a parte frontal e traseira serão redefinidas para -1.
Algoritmo para excluir um elemento da fila circular
Passo 1: SE FRENTE = -1
Escreva 'UNDEFLOW'
Vá para a etapa 4
[FIM do SE]
Passo 2: DEFINIR VAL = FILA[FRENTE]
Etapa 3: SE FRENTE = TRASEIRA
DEFINIR FRENTE = TRASEIRA = -1
OUTRO
SE FRENTE = MÁX -1
DEFINIR FRENTE = 0
OUTRO
DEFINIR FRENTE = FRENTE + 1
[FIM do SE]
[FIM DO SE]
Passo 4: SAÍDA
Vamos entender a operação de enfileiramento e desenfileiramento por meio da representação diagramática.
Implementação de fila circular usando 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 :'); 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->data=x; newnode->next=0; if(rear==-1) // checking whether the Queue is empty or not. { front=rear=newnode; rear->next=front; } else { rear->next=newnode; rear=newnode; rear->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)&&(rear==-1)) // checking whether the queue is empty or not { printf('
Queue is empty'); } else if(front==rear) // checking whether the single element is left in the queue { front=rear=-1; free(temp); } else { front=front->next; rear->next=front; free(temp); } } // function to get the front of the queue int peek() { if((front==-1) &&(rear==-1)) { printf('
Queue is empty'); } else { printf('
The front element is %d', front->data); } } // function to display all the elements of the queue void display() { struct node *temp; temp=front; printf('
The elements in a Queue are : '); if((front==-1) && (rear==-1)) { printf('Queue is empty'); } else { while(temp->next!=front) { printf('%d,', temp->data); temp=temp->next; } printf('%d', temp->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)> Saída:
