Estruturas de Dados: Pilha

#dsa #computerscience #beginners #braziliandevs

É um tipo especial de lista linear, com a restrição que inserções e remoções ocorrem na mesma extremidade.

Alocação Sequencial

Temos um ponteiro chamado topo para indicar o topo da pilha,ou seja, o elemento da extremidade. Os algoritmos abaixo implementam inserção e remoção na pilha, considerando uma mmória de M posições.

Inserção na pilha

    se topo != M então
        topo := topo+1
        P[topo] := novo-valor
    senão *overflow*

Remoção na pilha

    se topo != 0 então
        valor-recuperado := P[topo]
        topo := topo - 1
    senão *underflow*

A complexidade das operações é O(1).

Alocação Encadeada

Considerando-se listas simplesmente encadeadas (sem nó-cabeça), o topo da pilha é o primeiro nó da lista, apontado por uma variável ponteiro topo. Se a pilha estiver vazia então topo = nulo.

Inserção

    // alocar pt
    pt->.info := novo-valor
    pt->.prox := topo
    topo := pt

Remoção

    se topo != nulo então
        pt := topo
        topo := topo->.prox
        valor-recuperado := pt->.info
        // desalocar pt
    senão *underflow*

As complexidades dessas operações são constantes, ou seja, O(1).

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More