Fila é uma estrutura de dados em que o primeiro elemento que entra é o primeiro que sai. Esse comportamento tem nome: FIFO, do inglês First In, First Out (primeiro a entrar, primeiro a sair).
No artigo sobre lista encadeada, deixei um desafio: criar um método que conta quantos nós a lista tem. Conseguiu? Veja como ficou o meu, em Python:
class No:
def __init__(self, valor, proximo=None):
self.valor = valor
self.proximo = proximo
class ListaEncadeada:
def __init__(self):
self.inicio = None
def adicionar_no_inicio(self, valor):
self.inicio = No(valor, self.inicio)
def contar(self):
total = 0
atual = self.inicio
while atual is not None:
total += 1 # em vez de mostrar o valor, soma um
atual = atual.proximo
return total
tarefas = ListaEncadeada()
tarefas.adicionar_no_inicio("Estudar")
tarefas.adicionar_no_inicio("Almoçar")
tarefas.adicionar_no_inicio("Acordar")
print(tarefas.contar()) # 3
A única diferença para o percorrer é que, em vez de mostrar o valor de cada nó, o método soma um. Se o seu ficou diferente e funciona, parabéns: em programação quase sempre existe mais de um caminho certo!
Como funciona uma fila?
Pense na fila da padaria. Quem chega entra no fim. Quem é atendido sai do início. Ninguém entra no meio e ninguém é atendido antes de quem chegou primeiro (pelo menos não deveria kkkk).
A fila da padaria: entra pelo fim, sai pelo início, e ninguém fura.
A fila tem duas operações principais:
Enfileirar (enqueue, em inglês): coloca um elemento no fim da fila.
Desenfileirar (dequeue, em inglês): tira o elemento que está no início da fila.
Veja o passo a passo:
Passo
Operação
Fila (do início para o fim)
Quem saiu
1
Enfileirar Ana
Ana
Ninguém
2
Enfileirar Bruno
Ana, Bruno
Ninguém
3
Enfileirar Carla
Ana, Bruno, Carla
Ninguém
4
Desenfileirar
Bruno, Carla
Ana
5
Desenfileirar
Carla
Bruno
Passo a passo de uma fila: quem chegou primeiro sai primeiro.
Ver a animação da fila, passo a passo
O mesmo passo a passo em movimento: três entradas pelo fim e duas saídas pelo início.
Qual a diferença entre fila e pilha?
Você já conhece a pilha? As duas guardam elementos em sequência, mas a regra de saída de uma é o contrário da outra:
Fila
Pilha
Regra
FIFO: o primeiro que entra é o primeiro que sai
LIFO: o último que entra é o primeiro que sai
Onde entra
No fim
No topo
De onde sai
Do início
Do topo
Analogia
Fila da padaria
Pilha de pratos
Diferença entre fila e pilha.
Mesma ordem de chegada, saídas diferentes: na fila sai quem chegou primeiro, na pilha sai quem chegou por último.
Fila em PHP, Python, C e Java
Vamos usar o que você aprendeu no artigo anterior: a nossa fila vai ser uma lista encadeada que guarda duas referências, uma para o início e outra para o fim. Assim, entrar no fim e sair do início dão o mesmo trabalho, não importa o tamanho da fila. Veja em PHP:
<?php
class No
{
public function __construct(
public string $valor,
public ?No $proximo = null,
) {
}
}
class Fila
{
private ?No $inicio = null;
private ?No $fim = null;
public function enfileirar(string $valor): void
{
$novo = new No($valor);
if ($this->fim === null) {
$this->inicio = $novo; // fila vazia: o novo é o primeiro
} else {
$this->fim->proximo = $novo; // o último passa a apontar para o novo
}
$this->fim = $novo;
}
public function desenfileirar(): ?string
{
if ($this->inicio === null) {
return null; // fila vazia: não há quem atender
}
$valor = $this->inicio->valor;
$this->inicio = $this->inicio->proximo; // o segundo vira o primeiro
if ($this->inicio === null) {
$this->fim = null; // saiu o último: a fila ficou vazia
}
return $valor;
}
}
$fila = new Fila();
$fila->enfileirar('Ana');
$fila->enfileirar('Bruno');
$fila->enfileirar('Carla');
echo $fila->desenfileirar(), PHP_EOL; // Ana
echo $fila->desenfileirar(), PHP_EOL; // Bruno
Em Python:
class No:
def __init__(self, valor):
self.valor = valor
self.proximo = None
class Fila:
def __init__(self):
self.inicio = None
self.fim = None
def enfileirar(self, valor):
novo = No(valor)
if self.fim is None:
self.inicio = novo # fila vazia: o novo é o primeiro
else:
self.fim.proximo = novo # o último passa a apontar para o novo
self.fim = novo
def desenfileirar(self):
if self.inicio is None:
return None # fila vazia: não há quem atender
valor = self.inicio.valor
self.inicio = self.inicio.proximo # o segundo vira o primeiro
if self.inicio is None:
self.fim = None # saiu o último: a fila ficou vazia
return valor
fila = Fila()
fila.enfileirar("Ana")
fila.enfileirar("Bruno")
fila.enfileirar("Carla")
print(fila.desenfileirar()) # Ana
print(fila.desenfileirar()) # Bruno
E em C:
#include <stdio.h>
#include <stdlib.h>
struct No {
int valor;
struct No *proximo;
};
struct Fila {
struct No *inicio;
struct No *fim;
};
void enfileirar(struct Fila *fila, int valor) {
struct No *novo = malloc(sizeof(struct No));
if (novo == NULL) {
return; // sem memória: a fila fica como estava
}
novo->valor = valor;
novo->proximo = NULL;
if (fila->fim == NULL) {
fila->inicio = novo; // fila vazia: o novo é o primeiro
} else {
fila->fim->proximo = novo; // o último passa a apontar para o novo
}
fila->fim = novo;
}
int desenfileirar(struct Fila *fila) {
if (fila->inicio == NULL) {
return -1; // fila vazia: não há quem atender
}
struct No *primeiro = fila->inicio;
int valor = primeiro->valor;
fila->inicio = primeiro->proximo; // o segundo vira o primeiro
if (fila->inicio == NULL) {
fila->fim = NULL; // saiu o último: a fila ficou vazia
}
free(primeiro);
return valor;
}
int main(void) {
struct Fila fila = {NULL, NULL};
enfileirar(&fila, 101);
enfileirar(&fila, 102);
enfileirar(&fila, 103);
printf("%d\n", desenfileirar(&fila)); // 101
printf("%d\n", desenfileirar(&fila)); // 102
printf("%d\n", desenfileirar(&fila)); // 103
return 0;
}
E em Java:
public class Main {
static class No {
String valor;
No proximo;
No(String valor) {
this.valor = valor;
}
}
static class Fila {
private No inicio = null;
private No fim = null;
void enfileirar(String valor) {
No novo = new No(valor);
if (fim == null) {
inicio = novo; // fila vazia: o novo é o primeiro
} else {
fim.proximo = novo; // o último passa a apontar para o novo
}
fim = novo;
}
String desenfileirar() {
if (inicio == null) {
return null; // fila vazia: não há quem atender
}
String valor = inicio.valor;
inicio = inicio.proximo; // o segundo vira o primeiro
if (inicio == null) {
fim = null; // saiu o último: a fila ficou vazia
}
return valor;
}
}
public static void main(String[] args) {
Fila fila = new Fila();
fila.enfileirar("Ana");
fila.enfileirar("Bruno");
fila.enfileirar("Carla");
System.out.println(fila.desenfileirar()); // Ana
System.out.println(fila.desenfileirar()); // Bruno
}
}
Observe dois cuidados que aparecem nas quatro linguagens. Quando a fila está vazia, o primeiro que entra é ao mesmo tempo o início e o fim. E quando sai o último, o fim também precisa voltar a apontar para “nada”. Esquecer esses dois detalhes é um erro bem comum, então vou repetir: fila vazia pede atenção na entrada e na saída!
No exemplo em C, usei números de senha no lugar dos nomes, e o -1 avisa que a fila está vazia.
Aí você pergunta: não dá para usar um vetor como fila?
Dá, mas tem um custo: tirar o primeiro valor de um vetor obriga a puxar todos os outros uma posição para frente. O próprio tutorial do Python recomenda, para filas, a classecollections.deque, que foi projetada para inserir e remover com eficiência nas duas pontas:
from collections import deque
fila = deque()
fila.append("Ana")
fila.append("Bruno")
print(fila.popleft()) # Ana
O PHP também traz uma fila pronta, a classe SplQueue, que por dentro usa uma lista duplamente encadeada:
<?php
$fila = new SplQueue();
$fila->enqueue('Ana');
$fila->enqueue('Bruno');
echo $fila->dequeue(), PHP_EOL; // Ana
No Java, a fila pronta é a interface Queue. Uma das classes que servem de fila é a ArrayDeque: o add coloca no fim, e o poll tira do início.
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> fila = new ArrayDeque<>();
fila.add("Ana");
fila.add("Bruno");
System.out.println(fila.poll()); // Ana
}
}
No dia a dia você vai usar essas estruturas prontas. Mas agora você sabe o que acontece dentro delas, e é isso que separa quem entende de quem só decora!
Onde as filas aparecem no dia a dia?
Fila de impressão: os documentos saem na ordem em que foram enviados.
Atendimento: senhas de banco, chamados de suporte, pedidos de uma lanchonete.
Tarefas em segundo plano: um site que precisa enviar milhares de e-mails coloca cada envio em uma fila e vai processando um por um.
Agora é com você!
Crie na sua fila o método espiar (peek, em inglês): ele mostra quem é o primeiro da fila sem tirar ninguém de lá. Antes de digitar, pense: o que ele deve devolver quando a fila estiver vazia?
Tente sozinho primeiro! Você já viu coisa mais difícil que isso neste artigo. A resposta eu conto no próximo.
Até aqui, todas as estruturas que vimos eram “em linha”: um elemento depois do outro. No próximo artigo isso muda: você vai conhecer a árvore binária, em que cada nó pode apontar para dois caminhos. Até lá!
Oracle, documentação do Java 21. Classe ArrayDeque (em inglês), com a fila da biblioteca padrão, o add, que insere no fim, e o poll, que retira do início.
Os exemplos foram executados em PHP 8.3, Python 3.13, GCC 13 e Java 21.
Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".
Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.
Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.
Usamos cookies necessários para o site funcionar. Com a sua permissão, também usamos cookies de estatística e de publicidade, com ou sem personalização. Você pode mudar a escolha quando quiser em Preferências de cookies. Política de privacidade
Continue a conversa