Fila Circular em C: Como Implementar?
Publicados: 2020-10-23Os dados são organizados em uma fila circular em um padrão circular onde o último elemento é conectado ao primeiro elemento. Ao contrário da fila linear onde as tarefas são executadas em FIFO (First In First Out), a ordem da fila circular de execução das tarefas pode mudar. As operações de inserção e exclusão podem ser feitas em qualquer posição.
A fila circular é mais eficiente que a fila linear. Na representação gráfica de uma fila circular, pode-se observar que as posições frontal e traseira estão conectadas, formando um círculo onde as operações são sempre executadas em base FIFO. Cada novo elemento é adicionado na extremidade traseira e excluído da extremidade dianteira. Uma fila circular tem melhor utilização e complexidade de tempo O(1).
Fonte
Índice
Aplicações de uma fila circular
- Escalonamento da CPU: As filas circulares fazem uso dos espaços vazios de memória encontrados nas filas lineares.
- Sistema de Trânsito: No sistema de trânsito, com auxílio das filas circulares, os semáforos são acionados no intervalo de tempo definido.
- Gerenciamento de Memória: Os sistemas operacionais frequentemente mantêm uma linha de processos que estão preparados para serem executados ou que estão aguardando a ocorrência de um evento específico.
Aprenda: Programa C para classificação de bolhas: classificação de bolhas em C
Código de exemplo com explicação
Linha 1: // (1) Pré-processadores
Linha 2: // Definir limite de fila para 5 elementos
Linha 3: #include<stdio.h>
Linha 4: #define LIM 5
Linha 5: // (2) Declarações de tipo de dados de fila
Linha 6: // dados contém dados; delPos, posição para deletar; comprimento, não. do
Linha 7: // elementos atualmente presentes na fila
Linha 8: fila de estrutura typedef {
Linha 9: int data[LIM], delPos, comprimento;
Linha 10: } Q;
Linha 11: // (3) Declarações Globais
Linha 12: // Funções e variável global q do tipo de fila struct
Linha 13: Q q;
Linha 14: void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();
Linha 15: // (4) Chama a função de interface do usuário após a inicialização
Linha 16: int main()
Linha 17: {
Linha 18: initQ();
Linha 19: ui_Q_Ops();
Linha 20: retorno 0;
Linha 21: }
Linha 22: // (5) Inicializa a fila
Linha 23: void initQ()
Linha 24: {
Linha 25: q.comprimento = 0;
Linha 26: q.delPos = 0;
Linha 27: }
Linha 28: // (6) Menu Driven Loop chama as funções corretas
Linha 29: void ui_Q_Ops()
Linha 30: {
Linha 31: int escolha=0;
Linha 32: char input[16];
Linha 33: while(escolha!=4){
Linha 34: printf(" \n ———————-\n ");
Linha 35: printf(” 1. Insira na fila \n “);
Linha 36: printf(” 2. Excluir da fila \n “);
Linha 37: printf(” 3. Exibe os itens da fila \n “);
Linha 38: printf(” 4. Saia do programa \n “);
Linha 39: printf(" Digite a opção: ");
Linha 40: if (fgets(input, 15, stdin) != NULL){
Linha 41: if (sscanf(input, “%d”, &choice) == 1){
Linha 42: switch(escolha){
Linha 43: caso 1: insertQel();
Linha 44: quebra;
Linha 45: caso 2: deleteQel();
Linha 46: quebra;
Linha 47: caso 3: displayQels();
Linha 48: quebra;
Linha 49: caso 4: retorno;
Linha 50: default: printf(“Escolha inválida\n “);
Linha 51: continue;
Linha 52: }
Linha 53: } else
Linha 54: printf(” Escolha inválida \n “);
Linha 55: }
Linha 56: }
Linha 57: }
Linha 58: // (7) Inserir na fila
Linha 59: // Se o comprimento for igual ao MAX Limit, a fila está cheia, caso contrário insira
Linha 60: // obtido circularmente com soma de comprimento e módulo delPos por MAX Limit
Linha 61: // e comprimento do incremento
Linha 62: void insertQel()
Linha 63: {
Linha 64: int el, inspos;
Linha 65: char input[16];
Linha 66: if (q.length == LIM){
Linha 67: printf(" A fila está cheia \n ");
Linha 68: retorno;
Linha 69: }
Linha 70: inspos = (q.delPos + q.length) % LIM;
Linha 71: printf(" Digite o elemento para inserir: ");
Linha 72: if (fgets(input, 15, stdin) != NULL){
Linha 73: if (sscanf(input, “%d”, &el)){
Linha 74: q.data[inspos] = el;
Linha 75: q.length++;
Linha 76: } else
Linha 77: printf(” Entrada inválida \n “);
Linha 78: }
Linha 79: }
Linha 80: // (8) Excluir da fila
Linha 81: // Se Length for 0, queue está vazia, caso contrário delete em delPos
Linha 82: // e diminui o comprimento
Linha 83: void deleteQel()
Linha 84: {
Linha 85: if (q.length == 0){
Linha 86: printf(" A fila está vazia \n ");
Linha 87: } else {
Linha 88: printf(” Elemento deletado %d \n “, q.data[q.delPos]);
Linha 89: q.delPos = (q.delPos + 1) % LIM;
Linha 90: q.length–;
Linha 91: }
Linha 92: }
Linha 93: // (9) Exibir elementos da fila
Linha 94: // Exibe de forma circular executando um loop iniciando em delPos
Linha 95: // e adicionando iterador e módulo por Max Limit
Linha 96: void displayQels()
Linha 97: {
Linha 98: int i;
Linha 99: if (q.length == 0){
Linha 100: printf(" A fila está vazia \n ");
Linha 101: } else {
Linha 102: printf(" Os elementos da fila são: ");
Linha 103: for(i = 0; i < q.length; i++){
Linha 104: printf(“%d”, q.data[(q.delPos+i)%LIM]);
Linha 105: }
Linha 106: printf(” \n “);
Linha 107: }
Linha 108: }
Linha 109:
Saídas:
Operações em uma fila circular
1. insertQel() – Inserindo um elemento na fila circular
Em uma fila circular, a função enQueue() é usada para inserir um elemento na fila circular. Em uma fila circular, o novo recurso é sempre inserido na posição traseira. A função enQueue() recebe um valor inteiro como parâmetro e o insere na fila circular. As etapas a seguir são implementadas para inserir um elemento na fila circular:
Passo 1 – Verifique se o comprimento é igual ao MAX Limit. Se true, significa que a fila está FULL. Se estiver FULL, exiba “Queue is full” e encerre a função.
Passo 2 – Se NÃO estiver FULL, insira o valor que é obtido circularmente com o comprimento da soma e o módulo delPos pelo limite MAX e o comprimento do incremento
2. deleteQel() – Excluindo um elemento da fila circular
Em uma fila circular, deQueue() é uma função usada para excluir um elemento da fila circular. Em uma fila circular, o elemento é sempre excluído da posição frontal. A função deQueue() não recebe nenhum valor como parâmetro. As etapas a seguir são implementadas para excluir um elemento da fila circular…
Etapa 1 – Verifique se a fila está VAZIA. (frente == -1 && traseira == -1)
Passo 2 – Se estiver VAZIO, exiba “A fila está vazia” e encerre a função.
Passo 3 – Se NÃO estiver VAZIO, então exiba os elementos deletados de acordo com as posições. Depois que cada elemento for adicionado, vá para o próximo limite de fila de modificação de posição.
3. displayQels() – Exibe os elementos Queue que estão presentes na Fila Circular. As etapas a seguir são implementadas para exibir os elementos de uma fila circular:
Passo 1 – Verifique se a fila está VAZIA.
Passo 2 – Se length for 0, está VAZIO, então exiba “Queue is empty” e encerre a função.
Passo 3 – Se NÃO estiver VAZIO, então defina uma variável inteira 'i.'
Passo 4 – Defina i para 0.
Passo 5 – Novamente, exiba os elementos de acordo com a posição e incremente o valor em um (i++). Repita o mesmo até que 'i <q.length' se torne FALSE.
A fila circular também pode ser implementada usando a lista vinculada. Seguem os algoritmos:
- Algoritmo para enfileirar:
if (FRONT == NULL) // Inserindo em uma fila vazia
FRENTE = TRASEIRO = novoNó
fim se
outro
REAR -> next = newNode // Inserindo após o último elemento
REAR = novoNó
fim mais
TRASEIRA -> próximo = FRENTE
Enfileirar Enfileirar
- Algoritmo para Dequeue:
if(FRONT == NULL) // Condição para underflow
Imprima “Subfluxo de fila”
fim da fila
fim se
else if(FRONT == REAR) // A fila contém apenas um nó
temp = FRENTE -> dados
livre (temporário)
FRENTE = FRENTE -> próximo
TRASEIRA -> próximo = FRENTE
fim se
else if (FRONT == N – 1) // Se FRONT é o último nó
front = 0 // Torna FRONT o primeiro nó
fim se
fim da fila
Leia também: Python vs C: comparação completa lado a lado
Conclusão
Estruturas de dados e algoritmos são de grande importância e não apenas na programação C, mas também em outras linguagens. Seu valor é inédito e, para temas de tamanha importância, é melhor investir em cursos elaborados e orientados por especialistas, que agregarão excelente valor ao seu portfólio. O upGrad oferece uma ampla variedade de cursos poderosos que não apenas aprimoram suas habilidades, mas também criam fortes pilares de fundamentos.
Ele foi projetado pelo renomado IIIT-B, onde eles não apenas fornecem conteúdo de qualidade premium, mas também fazem parte de uma rede forte, onde você se conectará com pessoas que estão evoluindo na mesma carreira, bem como com especialistas do setor que resolver suas dúvidas e apoiá-lo sempre.
Conhecer a sua mentalidade e processo de pensamento iria ajudá-lo. E uma das coisas únicas que você obtém no upGrad é que você pode optar por opções de EMI e economizar no seu bolso.
Esperamos que você tenha uma excelente oportunidade de aprendizado na execução desses projetos C. Se você estiver interessado em aprender mais e precisar de orientação de especialistas do setor, confira o PG Diploma in Full-Stack Software Development da upGrad & IIIT Banglore.