Neste tutorial, você aprenderá o que é uma fila. Além disso, você encontrará a implementação de fila em C, C ++, Java e Python.
Uma fila é uma estrutura de dados útil na programação. É semelhante à fila de ingressos fora de uma sala de cinema, onde a primeira pessoa a entrar na fila é a primeira pessoa a receber o ingresso.
A fila segue a regra Primeiro a Entrar, Primeiro a Sair (FIFO) - o item que entra primeiro é o item que sai primeiro.
Representação FIFO de fila
Na imagem acima, como 1 foi mantido na fila antes de 2, é o primeiro a ser removido da fila também. Ele segue a regra FIFO .
Em termos de programação, colocando itens na fila é chamado de enfileiramento , e remover itens da fila é chamado dequeue .
Podemos implementar a fila em qualquer linguagem de programação como C, C ++, Java, Python ou C #, mas a especificação é praticamente a mesma.
Operações básicas de fila
Uma fila é um objeto (uma estrutura de dados abstrata - ADT) que permite as seguintes operações:
- Enfileirar : adicione um elemento ao final da fila
- Desenfileirar : remove um elemento da frente da fila
- IsEmpty : Verifique se a fila está vazia
- IsFull : Verifique se a fila está cheia
- Peek : obtenha o valor da frente da fila sem removê-lo
Trabalho de fila
As operações de fila funcionam da seguinte maneira:
- dois ponteiros FRONT e REAR
- FRONT rastreia o primeiro elemento da fila
- REAR rastreia o último elemento da fila
- inicialmente, defina o valor de FRONT e REAR para -1
Operação de enfileiramento
- verifique se a fila está cheia
- para o primeiro elemento, defina o valor de FRONT para 0
- aumentar o índice REAR em 1
- adicione o novo elemento na posição apontada por REAR
Operação de desenfileiramento
- verifique se a fila está vazia
- retorna o valor apontado por FRONT
- aumentar o índice FRONT em 1
- para o último elemento, redefina os valores de FRONT e REAR para -1
Operações de enfileiramento e desenfileiramento
Implementações de fila em Python, Java, C e C ++
Normalmente usamos arrays para implementar filas em Java e C / ++. No caso do Python, usamos listas.
Python Java C C ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear++; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )
Limitações da fila
Como você pode ver na imagem abaixo, após um pouco de enfileiramento e desenfileiramento, o tamanho da fila foi reduzido.
Limitação de uma fila
E só podemos adicionar os índices 0 e 1 apenas quando a fila é redefinida (quando todos os elementos foram retirados da fila).
Depois de REAR atingir o último índice, se pudermos armazenar elementos extras nos espaços vazios (0 e 1), podemos fazer uso dos espaços vazios. Isso é implementado por uma fila modificada chamada fila circular.
Análise de Complexidade
A complexidade das operações de enfileiramento e desenfileiramento em uma fila usando uma matriz é O(1).
Aplicações de Fila
- Agendamento de CPU, Agendamento de disco
- Quando os dados são transferidos de forma assíncrona entre dois processos. A fila é usada para sincronização. Por exemplo: Buffers de IO, canais, arquivo IO, etc.
- Tratamento de interrupções em sistemas de tempo real.
- Os sistemas telefônicos do Call Center usam Filas para manter as pessoas que ligam para elas em ordem.
Leituras Recomendadas
- Tipos de fila
- Circular Queue
- Estrutura de Dados Deque
- Fila de prioridade
