Estruturas de Dados: Pilhas, Filas, Ponteiros e Árvores

Pilha (Stack)

• Stack
• Lista Linear
• Inserção e remoção no topo
• LIFO (Last In, First Out) - O último a entrar é o primeiro a sair
• Base e Topo

Operações de Pilha

• TOP: Retorna uma cópia do elemento no topo.
• PUSH: Insere um elemento no topo.
• POP: Remove o elemento do topo.
• Overflow: Ocorre ao tentar inserir em uma pilha cheia.
• Underflow: Ocorre ao tentar acessar uma pilha vazia.

Aplicações: Guardar dados em ordem inversa; utilizados em Sistemas Operacionais, Compiladores e nas instruções de subprogramas.

Fila (Queue)

• Lista Linear
• Insere no Final
• Remove no Início

Operações de Fila

• Enqueue (Enfileirar): Insere um elemento.
• Dequeue (Desenfileirar): Remove um elemento.
• F.começo persegue F.final.
• Fila Vazia: F.começo = F.final.
• Fila Cheia: F.final > MAX.
• Impasse: F.começo = F.final > MAX (Fila cheia e vazia simultaneamente).

Solução: Utilizar um contador para guardar a quantidade e colocar a posição 1 depois do MAX, tornando a Fila Circular.

Ponteiros

Ponteiros são variáveis destinadas a guardar e manipular endereços de memória.

O endereço é um número inteiro que serve para identificar um byte específico da memória. A diferença entre um inteiro qualquer e um inteiro que representa um endereço está nas operações efetuadas: inteiros comuns podem ser somados ou multiplicados, enquanto endereços servem apenas para referenciar posições específicas.

Um ponteiro deve ter um tipo determinado na sua declaração. A sintaxe para a definição de tipos ponteiros é: type <nome> = ^<tipo>.

• Se uma variável ponteiro P armazena um endereço, P^ nos dá o conteúdo armazenado naquele endereço.
• O sistema operacional gerencia a memória; um programa raramente usa toda a memória disponível, deixando grande parte livre.

Árvores

São estruturas de dados adequadas para a representação de hierarquias. Uma árvore é composta por um conjunto de nós.

• Existe um nó r (raiz) que contém zero ou mais subárvores ligadas diretamente a ele.
• A raiz se liga a elementos chamados de galhos ou filhos.

Fundamentos Básicos

• Grau: Número de subárvores de um nó.
• Folha: Um nó com grau zero (não possui subárvores).
• Filhos: Raízes das subárvores de um nó.
• Nó não terminal: Nó que não é folha e é diferente da raiz.
• Altura: Comprimento do caminho mais longo da raiz até uma das folhas. Uma árvore nula tem altura 0.
• Todos os nós são acessíveis a partir da raiz por um caminho único.

Árvore Binária

Uma árvore binária pode ser nula ou possuir as seguintes características:

1. Possui um nó especial denominado raiz.
2. Nenhum nó tem grau superior a 2 (no máximo dois filhos).
3. Existe um senso de posição: distingue-se entre subárvore esquerda e direita.

Atravessamento (Caminhamento)

É a passagem sistemática por cada um dos nós:

• Pré-ordem (Prefixa): Visita a raiz, caminha pela esquerda, depois pela direita.
• Em ordem (Infixa): Caminha pela esquerda, visita a raiz, depois pela direita.
• Pós-ordem (Posfixa): Caminha pela esquerda, caminha pela direita, depois visita a raiz.
• Em nível: Percorre de cima para baixo, da esquerda para a direita.

Tipos de Árvores Binárias

• Estritamente Binária: Todo nó tem 0 ou 2 subárvores (sem "filho único").
• Árvore Binária Cheia: Todos os nós (exceto o último nível) possuem duas subárvores. Uma árvore de altura h tem 2^h – 1 nós.
• Árvore Degenerada: Cada nó possui exatamente um filho; o número de níveis é igual ao número de nós.

Árvore Binária de Busca (BST)

Uma árvore é de busca se:

• Todo elemento da subárvore esquerda é menor que a raiz.
• Nenhum elemento da subárvore direita é menor que a raiz.
• As subárvores também são árvores de busca binária.

Busca: Compara com a raiz; se menor, vai para a esquerda; se maior, vai para a direita (recursivamente).

Inserção: Se vazia, cria o nó. Se não, compara a chave: se menor, insere na esquerda; se maior, insere na direita.

Remoção

Processo complexo com três casos:

1. Remoção em folha.
2. Remoção de nó com um filho.
3. Remoção de nó com dois filhos: substitui-se pelo sucessor (mais à esquerda da subárvore direita) ou pelo antecessor (mais à direita da subárvore esquerda).

Árvore AVL

Uma árvore é balanceada quando as subárvores de qualquer nó têm a mesma altura. A Árvore AVL (Adelson-Velsky e Landis) é uma árvore de busca onde a diferença de altura entre subárvores (Fator de Balanceamento - FB) é de, no máximo, 1.

Para manter o balanceamento após inserções, utilizam-se Rotações:

• Rotação simples à esquerda;
• Rotação simples à direita;
• Rotação dupla à esquerda;
• Rotação dupla à direita.

Implementações em Pascal

procedure push(var P:tpPilha; s:string);
   begin
       if full(P) then
          writeln('Stack Overflow!')
       else
       begin
           inc(P.topo); // P.topo := P.topo + 1
           P.dados[P.topo] := s;
           writeln(s, ' foi empilhado(a)');
       end;
   end;

function pop(var P:tpPilha):string;
   begin
        if empty(P) then
           pop := 'Stack Underflow'
        else
        begin
           pop := P.dados[P.topo];
           dec(P.topo); // P.topo := P.topo - 1
        end;
   end;

procedure enqueue(var F:tpFila; s:string);
begin
    if cheia(F) then
       writeln('Fila cheia. Cabe ninguém!')
    else
    begin
        F.dados[F.final] := s;
        inc(F.final);
        writeln(s, ' entrou na fila!!!');
    end;
end;

function dequeue(var F:tpFila):string;
begin
    if vazia(F) then
       dequeue := 'Ninguém'
    else
    begin
       dequeue := F.dados[F.comeco];
       inc(F.comeco);
    end;
end;

procedure listar(F:tpFila);
begin
    if vazia(F) then
       writeln('A fila está vazia!')
    else
    begin
        writeln('Mostrando a fila');
        while not vazia(F) do
        begin
            write(dequeue(F), ' | ');
        end;
        writeln;
    end;
end;

Fila Circular

procedure fila.Inserir (a:tipo);
begin
    if fim < MAX then
    // ... lógica de inserção
end;

procedure fila.Retirar (var a:tipo);
begin
    clrscr;
    if not vazia then
    begin
        a := vetfila[inicio];
        n_elem := n_elem - 1;
        if inicio < MAX then
            inicio := inicio + 1
        else
            inicio := 1;
        writeln('Elemento retirado: ', a);
    end
    else
        writeln('A Fila está vazia');
    readkey;
end;