DEV Community

Alex Reis
Alex Reis

Posted on

2 1 1 1 1

Estruturas de Dados: Fila

É um tipo especial de lista linear com as mesmas priprieadades, mas com a restrição de que a inserção ocorre no final e remoção no começo da fila.

Alocação Sequencial

São necessários dois ponteiros: início de fila (f) e retaguarda (r). Para a adição de um elemento, move-se o ponteiro r; para a retirada, move-se o ponteiro f. A situação de fila vazia é representada por f = r = 0.

À medida que os ponteiros são incrementados na memória disponível, a fila “se move”, o que pode dar origem à falsa impressão de memória esgotada. Para eliminar esse problema, consideram-se os M nós alocados como se estivessem em círculo, onde F[1] segue F[M].

A inicialização de *f e r é f = r = 0.

Inserção na fila

    prov := r mod M + 1
    se prov != f então
        r := prov
        F[r] := novo-valor
        se f == 0 então
            f := 1
    senão *overflow*
Enter fullscreen mode Exit fullscreen mode

Remoção

    se f != 0 então
        valor-recuperado := F[f]
        se f == r então
            f := r := 0
        senão
            f := f mod M + 1
    senão *underflow*
Enter fullscreen mode Exit fullscreen mode

Operações de tempo constante.

Alocação Encadeada

Filas exigem duas variáveis do tipo ponteiro: inicio, que aponta para o primeiro nó da lista, e fim, que aponta para o último. Na fila vazia, ambos apontam para nulo.

Inserção

    // alocar pt
    pt->.info := novo-valor
    pt->.prox := nulo
    se fim != nulo então
        fim->.prox := pt
    senão
        inicio := pt
    fim := pt
Enter fullscreen mode Exit fullscreen mode

Remoção

    se inicio != nulo então
        pt := inicio
        inicio := inicio->.prox
        se inicio == nulo então
            fim := nulo
        valor-recuperado := pt->.info
        // desalocar pt
    senão *underflow*
Enter fullscreen mode Exit fullscreen mode

A complexidade para essas operações é constante, ou seja, O(1).

Referência

Livro Estruturas de Dados e seus Algoritmos

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay