Introdução a Listas Lineares de Fila por Alocação Sequencial, Introdução à Pilha Duplamente Encadeada, uma base para melhor compreensão.

          Introdução a Listas Lineares de Fila por Alocação Sequencial, utilizando teste de mesa para melhor compreensão.

FIFO

• Inserção: da variável Y para V .............. Y → V

Respeitando a regra de fila “sempre no final”.

Um exemplo de Inserção da variável Y para V .............. Y → V

se FIM = n

então OVERFLOW;

senão FIM := FIM +1;

V[FIM] := Y; (onde Y = Dados)

se FIM = 1 então COMEÇO := 1;
fim se;

Segue abaixo a tela inicial do nosso algoritmo, onde encontraremos valores para Fim = 3, Y= Dados e Começo = 1.

• Exclusão: de V para variável Y ............ Y ← V

Respeitando a regra de fila “sempre no início”

Um exemplo de Exclusão: de V para variável Y Y ← V

se FIM = 0

então UNDERFLOW;

senão Y:= V[COMEÇO];

     COMEÇO := COMEÇO + 1;

     se COMECO>FIM então COMEÇO := 0;

                                           FIM := 0;

     fim se

fim se;

Se o Fim for igual a zero, então teremos um underflow, ou seja, não há nada na fila. Neste exemplo inicial, não temos situação de underflow.

• Pesquisa: localiza variável Y em V ....... Y ? V

Respeitando a regra de fila “a partir do início”

• Modificação: localiza variável Y em V; 

troca valor de V pela variável X X ↔ Y ? V

Grande inconveniente da estrutura de fila

Situações de OVERFLOW podem ocorrer com a fila praticamente vazia;

Motivo: não aproveitamento, deixando posições vazias (sem conteúdo).

Introdução à Pilha Duplamente Encadeada, usando teste de mesa para melhor compreensão.

LIFO

Na estrutura virtual de pilha:

• As inclusões são feitas no topo;
• As exclusões são feitas no topo;
• A consulta é feita à partir do topo;

Inserção: da variável Y para PILHA .............. Y → PILHA

Vamos avaliar o algoritmo abaixo, com teste de mesa:

• aloc P;
• P­.INFO := Y;
• P­.PROX := TOPO;
• TOPO := P;

Observe a tela inicial, antes da execução do algoritmo acima. Para acompanhar o passo a passo, siga as fechas.

Exclusão: de PILHA para variável Y ............. Y ← PILHA

se TOPO=L

• então UNDERFLOW;
• senão Y:= TOPO­.INFO;
• P:= TOPO;
• TOPO:= TOPO­.PROX;
• lib P;

fim se;

Observe novamente o passo-a-passo.

Observe a tela ao lado.Indica a tela inicial antes que o algoritmo se inicie.

Pesquisa: localiza variável Y na PILHA ........ Y ? PILHA

P:= TOPO;
enquanto TOPO # L e TOPO­.INFO # Y faça

• TOPO:= TOPO­.PROX;

fim enquanto;
se TOPO # L

• então SUCESSO;
• senão FRACASSO;

fim se;
TOPO:=P;

Observe a tela abaixo. Indica a tela inicial antes que o algoritmo se inicie.

Modificação: localiza variável Y em PILHA; troca valor de PILHA pela variável X ............ X ↔ Y ? PILHA

Segue algoritmo abaixo como modelo de pesquisa e alteração.

P:= COMEÇO;
enquanto COMEÇO # L e COMEÇO­.INFO # Y faça
    COMEÇO:= COMEÇO­.PROX;
    fim enquanto;
        se COMEÇO # L
            então COMEÇO­.INFO := X;
                 SUCESSO;
             senão FRACASSO;
        fim se;
COMEÇO:=P;