Algoritmos

Fila (estrutura de dados): quem chega primeiro sai primeiro

Capa do artigo Fila (estrutura de dados): quem chega primeiro sai primeiro
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. Como funciona uma fila?
  2. Qual a diferença entre fila e pilha?
  3. Fila em PHP, Python, C e Java
  4. Aí você pergunta: não dá para usar um vetor como fila?
  5. Onde as filas aparecem no dia a dia?
  6. Agora é com você!

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).

História em quadrinhos em três quadros na fila da padaria: Carla chega e entra no fim, Ana, a primeira, é atendida e sai, e Davi é mandado para o fim da fila
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:

PassoOperaçãoFila (do início para o fim)Quem saiu
1Enfileirar AnaAnaNinguém
2Enfileirar BrunoAna, BrunoNinguém
3Enfileirar CarlaAna, Bruno, CarlaNinguém
4DesenfileirarBruno, CarlaAna
5DesenfileirarCarlaBruno
Passo a passo de uma fila: quem chegou primeiro sai primeiro.
Ver a animação da fila, passo a passo
Animação de uma fila em que Ana, Bruno e Carla entram pelo fim e depois Ana e Bruno saem pelo início, na ordem em que chegaram
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:

FilaPilha
RegraFIFO: o primeiro que entra é o primeiro que saiLIFO: o último que entra é o primeiro que sai
Onde entraNo fimNo topo
De onde saiDo inícioDo topo
AnalogiaFila da padariaPilha de pratos
Diferença entre fila e pilha.
Diagrama comparando fila e pilha com Ana, Bruno e Carla: na fila sai a Ana, na pilha sai a Carla
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 classe collections.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á!

Confiança Sempre!!!

Fontes:

Compartilhe este artigo

Sobre quem escreve

Walmir Silva

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.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Guardamos o IP e o navegador de quem comenta por 6 meses, para barrar spam e porque o Marco Civil da Internet pede a guarda dos registros de acesso por esse prazo. Veja como tratamos seus dados.

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e o código do registro dela, e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager.

Exibem anúncios do Google AdSense sem personalização. Os cookies desta categoria limitam a repetição dos anúncios e medem o resultado deles.

Usa a sua navegação para escolher anúncios e formar públicos de anúncio: anúncios do Google escolhidos pelos seus interesses e os indicadores do Google no Analytics. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.