c circular queue data structure
Este tutorial sobre a estrutura de dados da fila circular C ++ explica o que é a fila circular, quais são as operações básicas junto com a implementação e os aplicativos:
Uma fila circular é uma extensão da fila básica que discutimos anteriormente. Também é conhecido como “Ring buffer”.
O que é fila circular em C ++?
Uma fila circular é uma estrutura de dados linear usada para armazenar itens de dados. Ele executa as operações seguindo a abordagem FIFO (Primeiro a Entrar, Primeiro a Sair) e a última posição na fila é conectada de volta à primeira posição para formar um círculo.
=> Procure toda a série de treinamento C ++ aqui
O que você aprenderá:
Fila circular em C ++
O diagrama a seguir mostra uma fila circular.
A imagem acima mostra uma estrutura de dados circular de tamanho 10. Os primeiros seis elementos já estão na fila e vemos que a primeira posição e a última posição estão unidas. Devido a este arranjo, o espaço não é desperdiçado como acontece em uma fila linear.
o gateway padrão não está disponível constantemente
Em uma fila linear, depois que a fila está cheia, excluímos os elementos de outra extremidade, e o status da fila ainda é mostrado como cheio e não podemos inserir mais elementos.
Na fila circular, quando a fila está cheia, e quando removemos os elementos da frente uma vez que a última e a primeira posição estão conectadas, podemos inserir os elementos de trás que foram desocupados, excluindo o elemento.
Na próxima seção, aprenderemos sobre as operações básicas da fila circular.
Operações básicas
Algumas das operações básicas da fila circular são as seguintes:
Frente: Retorna a posição frontal na fila circular.
Traseira: Retorna a posição traseira na fila circular.
Enfileirar: Enqueue (valor) é usado para inserir um elemento na fila circular. O elemento é sempre inserido na extremidade posterior da fila.
Seguimos a seguinte seqüência de etapas para inserir um novo elemento na fila circular.
# 1) Verifique se a fila circular está cheia: teste ((traseiro == SIZE-1 && frontal == 0) || (traseiro == frontal-1)), onde ‘SIZE’ é o tamanho da fila circular.
#dois) Se a fila circular estiver cheia, será exibida uma mensagem como “Fila cheia”. Se a fila não estiver cheia, verifique se (traseira == SIZE - 1 && frontal! = 0). Se for verdade, defina rear = 0 e insira o elemento.
Retirar da fila: A função Desenfileirar é usada para excluir um elemento da fila. Na fila circular, o elemento é sempre excluído do front end. A seguir, é fornecida a sequência para a operação de desenfileiramento em uma fila circular.
Degraus:
# 1) Verifique se a fila circular está vazia: verifique se (frente == - 1).
#dois) Se estiver vazio, exiba a mensagem “A fila está vazia”. Se a fila não estiver vazia, execute a etapa 3.
# 3) Verifique se (dianteiro == traseiro). Se for verdade, defina frente = traseira = -1, então verifique se (frente == tamanho-1), se for verdade, defina frente = 0 e retorne o elemento.
Ilustração
Nesta seção, veremos uma ilustração detalhada de como adicionar / remover elementos na fila circular.
Considere a seguinte fila circular de 5 elementos, conforme mostrado abaixo:
onde posso assistir anime de graça
Em seguida, inserimos o item 1 na fila.
A seguir, inserimos um item com valor 3.
Ao inserirmos os elementos para encher a fila, a representação será a seguinte.
Agora, excluímos os dois elementos, ou seja, item 1 e item 3 da fila, conforme mostrado abaixo.
Em seguida, inserimos ou enfileiramos o elemento 11 na fila circular, conforme representado abaixo.
Novamente, vamos inserir o elemento 13 na fila circular. A fila será exibida conforme mostrado abaixo.
Vemos que na fila circular movemos ou inserimos elementos em um círculo. Portanto, podemos consumir todo o espaço da fila até que ela fique cheia.
Implementação
Vamos implementar a fila circular usando C ++.
#include using namespace std; class Queue { public: // Initialize front and rear int rear, front; // Circular Queue int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int(sz); } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<'
Queue is Full'; return; } else if (front == -1) { /* Insert First Element */ front = rear = 0; circular_queue(rear) = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue(rear) = elem; } else { rear++; circular_queue(rear) = elem; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { cout<<'
Queue is Empty'; return -1; } int data = circular_queue(front); circular_queue(front) = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //display elements of Circular Queue void Queue::displayQueue() { if (front == -1) { cout<<'
Queue is Empty'<= front) { for (int i = front; i <= rear; i++) cout< Acima é mostrado o resultado das operações de fila circular. Primeiro, adicionamos os elementos e, em seguida, retiramos da fila ou removemos dois elementos. Em seguida, inserimos ou enfileiramos mais três elementos na fila circular. Vemos que, ao contrário da fila linear, os elementos são adicionados no final da fila.
Implementação de lista vinculada
Vamos discutir a implementação de lista vinculada de uma fila circular agora. A seguir, é fornecida a implementação de lista vinculada da fila circular em C ++. Observe que usamos struct para representar cada nó. As operações são as mesmas discutidas antes, exceto que, neste caso, temos que executá-las em relação aos nós da lista vinculada.
A saída mostra a fila circular após a operação de enfileiramento, desenfileiramento e também após a segunda operação de enfileiramento.
#include using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* this functions performs enqueue operation for circular queue */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // This function performs dequeue operation for Circular Queue int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<'Queue is empty!!'; return -1; } int elem; // item to be dequeued // item is the last node to be deleted if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //more than one nodes { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //display elements of Circular Queue void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<data<<' '; temp = temp->link; } cout<data; } //main program int main() { // Create a circular queue and initialize front and rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Insert/enqueue elements in Circular Queue enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<'
Circular Queue elements after enqueue operation: '; // Display elements in Circular Queue displayQueue(pq); // Delete/dequeue elements from Circular Queue cout<<'
Dequeued Item: '< Resultado:
A próxima implementação é um programa Java para demonstrar a fila circular usando a lista vinculada.
import java.util.* ; class Main { // Node structure static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Enqueue operation for circular queue static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Dequeue operation for Circular Queue static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ('Queue is empty!!'); return Integer.MIN_VALUE; } int value; // Value to be dequeued // the last node to be deleted if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // There are more than one nodes Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // display the elements of Circular Queue static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf('%d ', temp.data); temp = temp.link; } System.out.printf('%d', temp.data); } /* main program */ public static void main(String args()) { // Create a queue and initialize front and rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Insert/enqueue elements in Circular Queue enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print('
Circular Queue elements after Enqueue Operation:'); // Display elements in Circular Queue displayQueue(cq); // Delete/dequeue elements from Circular Queue System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.print('
Circular Queue elements after Dequeue Operation:'); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print('
Circular Queue elements after second Enqueue Operation:'); displayQueue(cq); } } Resultado:
A saída do programa acima é semelhante ao programa anterior.
Formulários
Vamos discutir algumas das aplicações da fila circular.
- Agendamento de CPU: O processo do sistema operacional que requer que algum evento ocorra ou que alguns outros processos sejam concluídos para execução é freqüentemente mantido em uma fila circular para que seja executado um após o outro quando todas as condições forem atendidas ou quando todos os eventos ocorrerem.
- Gerenciamento de memória: O uso de filas comuns desperdiça espaço de memória, conforme já mencionado em nossa discussão acima. Usar uma fila circular para gerenciamento de memória é benéfico para o uso ideal da memória.
- Sistema de sinal de tráfego controlado por computador: Os sinais de tráfego computadorizados são frequentemente adicionados a uma fila circular para que se repitam após o intervalo de tempo especificado.
Conclusão
As filas circulares corrigem a principal desvantagem de uma fila normal, em que não podemos inserir elementos quando o ponteiro traseiro está no final da fila, mesmo quando excluímos os elementos e o espaço é vazio. Em uma fila circular, os elementos são dispostos de maneira circular, de modo que o espaço não seja desperdiçado.
Também vimos as principais operações da fila circular. As filas circulares são principalmente úteis para fins de programação e aplicações como sistemas de semáforos, onde os sinais brilham em curvas.
liste todos os sistemas operacionais com os quais você está familiarizado
Em nosso próximo tutorial, aprenderemos sobre as filas duplas que são simplesmente chamadas de “deque”.
=> Visite aqui para aprender C ++ do zero
Leitura recomendada
- Estrutura de dados da fila em C ++ com ilustração
- Estrutura de dados da fila de prioridade em C ++ com ilustração
- Estrutura de dados de lista ligada circular em C ++ com ilustração
- Tutorial do Data Mart - Tipos, exemplos e implementação do Data Mart
- Estrutura de pilha de dados em C ++ com ilustração
- Exemplos de mineração de dados: aplicações mais comuns de mineração de dados 2021
- Estrutura de dados de árvore binária em C ++
- Fila prioritária em STL
