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
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;