Na ciência da computação, uma fila é uma estrutura de dados linear onde os componentes são colocados em uma extremidade e removidos da outra extremidade de acordo com o princípio 'primeiro a entrar, primeiro a sair' (FIFO). Esta estrutura de dados pode ser utilizada para controlar uma sequência de ações ou armazenar dados. C é uma linguagem de computador com capacidade de fila incorporada na forma de arrays ou listas vinculadas.
Características:
- Uma fila é um tipo de estrutura de dados linear que pode ser construída com uma matriz ou uma lista vinculada.
- Os elementos são realocados para o final da fila enquanto são removidos da frente.
- Enfileirar (adicionar um elemento na parte de trás) e desenfileirar (remover um elemento da frente) são duas operações de fila.
- Quando elementos são adicionados e removidos com frequência, uma fila pode ser construída como uma fila circular para evitar desperdício de memória.
Usando matriz:
Para implementar uma fila em C usando um array, primeiro defina o tamanho máximo da fila e declare um array desse tamanho. Os inteiros front e back foram definidos respectivamente como 1. A variável front representa o elemento frontal da fila e a variável back representa o elemento back.
Antes de enviar o novo elemento para a posição final da fila, precisamos aumentar a variável back em 1. A fila agora está cheia e nenhum outro elemento adicional pode ser adicionado quando a posição back estiver atingindo a capacidade máxima da fila. Adicionamos um elemento ao início da fila e aumentamos a variável frontal em apenas um para remover um elemento da fila. Se as posições frontal e traseira forem iguais e nenhum outro componente puder ser excluído, podemos dizer que a fila está vazia.
Abaixo está uma instância de uma fila escrita em C que faz uso de um array:
como saber se alguém te bloqueou no android
Linguagem de programação C:
listas em java
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } A saída do código será:
Saída:
10 20 30 Queue is empty-1
Explicação:
- Primeiro, enfileiramos três elementos 10, 20 e 30 na fila.
- Em seguida, retiramos da fila e imprimimos o elemento frontal da fila, que é 10.
- Em seguida, retiramos da fila e imprimimos novamente o elemento frontal da fila, que é 20.
- Em seguida, retiramos da fila e imprimimos novamente o elemento frontal da fila, que é 30.
- Finalmente, fazemos um desenfileiramento de uma fila vazia que gera 'A fila está vazia' e retorna -1.
Usando lista vinculada:
Outra abordagem alternativa para construir uma fila na linguagem de programação C é usar uma lista vinculada. Cada um dos nós na fila é expresso usando este método por um nó que contém o valor do elemento e um ponteiro para o nó seguinte na fila. Para rastrear o primeiro e o último nó da fila, respectivamente, são usados ponteiros frontais e traseiros.
Estabelecemos um novo nó com o valor do elemento e definimos seu próximo ponteiro como NULL para adicionar um elemento à fila. Para o novo nó, definimos os ponteiros frontal e traseiro se a fila estiver vazia. Caso contrário, atualizamos o ponteiro traseiro e definimos o próximo ponteiro do nó traseiro antigo para apontar para o novo nó.
sistema.out.println
Ao excluir um nó de uma fila, o nó anterior é excluído primeiro, depois o ponteiro frontal é atualizado para o nó subsequente na fila e, finalmente, a memória que o nó removido estava ocupando é liberada. Se o ponteiro frontal for NULL após a remoção, a fila estará vazia.
Aqui está um exemplo de fila implementada em C usando uma lista vinculada:
Linguagem de programação C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } A saída do código será:
Saída:
pandas e numpy
10 20 30 Queue is empty-1
Explicação:
- Primeiro, enfileiramos três elementos 10, 20 e 30 na fila.
- Em seguida, retiramos da fila e imprimimos o elemento frontal da fila, que é 10.
- Em seguida, retiramos da fila e imprimimos novamente o elemento frontal da fila, que é 20.
- Em seguida, retiramos da fila e imprimimos novamente o elemento frontal da fila, que é 30.
- Por fim, tentamos retirar da fila vazia, o que imprime a mensagem 'A fila está vazia' e retorna -1.
Vantagens:
- As filas são particularmente úteis para implementar algoritmos que exigem que os elementos sejam processados em uma sequência precisa, como pesquisa em largura e agendamento de tarefas.
- Como as operações de fila têm uma complexidade de tempo O(1), elas podem ser executadas rapidamente mesmo em filas enormes.
- As filas são particularmente flexíveis, pois podem ser simplesmente implementadas usando um array ou uma lista vinculada.
Desvantagens:
- Uma fila, diferentemente de uma pilha, não pode ser construída com um único ponteiro, tornando a implementação da fila um pouco mais complicada.
- Se a fila for construída como uma matriz, ela poderá ficar cheia em breve se muitos elementos forem adicionados, resultando em problemas de desempenho ou possivelmente em uma falha.
- Ao utilizar uma lista vinculada para implementar a fila, a sobrecarga de memória de cada nó pode ser significativa, especialmente para elementos pequenos.
Conclusão:
Os aplicativos que usam filas, uma estrutura de dados crucial, incluem sistemas operacionais, redes e jogos, para citar apenas alguns. Eles são ideais para algoritmos que devem lidar com elementos em uma ordem específica, pois são simples de criar usando um array ou lista vinculada. Entretanto, as filas apresentam desvantagens que devem ser consideradas ao selecionar uma estrutura de dados para uma determinada aplicação, como consumo de memória e complexidade de implementação.