Listas Restritas

Listas Restritas

Definição: São listas onde existe alguma restrição na forma com que são atualizadas ou acessadas. A limitação imposta à lista determina uma ordenação dos itens diferente da ordem natural dos valores dos dados.

Iremos ver dois tipos de listas restritas: Pilha e Fila.

Pilha

Definição: Uma pilha é uma lista em que as operações de inserção e remoção são feitas na mesma extremidade da lista, conhecido como topo da pilha.

Esta restrição de acesso (ou disciplina) que caracteriza a pilha é denominada LIFO, abreviação de "Last In First Out", isto é, o último a entrar será o primeiro a sair.

Graficamente temos:

A tabela abaixo descreve as principais operações:

Operação	Descrição
Inicializar	Executa as ações necessárias para aprontar a pilha.
Empilhar	Coloca um elemento no topo da pilha.
Desempilhar	Remove o elemento que está no topo da pilha.
Topo	Retorna o elemento que está no topo da pilha.
Vazia	Indica se a pilha está vazia.

Há basicamente 2 formas de implementar uma pilha:

Usando uma lista encadeada: o elemento inserido é colocado na cabeça da lista.
Usando um array: o elemento inserido é colocado na posição nº de elementos + 1.

Pilha baseada em lista encadeada

Para ver uma implementação de uma Pilha usando lista encadeada, abra a unit PilhaE e para um programa que demonstra como usá-la para testar o casamento de parênteses de uma expressão TestExp.

O procedimento Inicializar faz com que o topo receba nil e o tamanho seja igual a zero.

O procedimento Empilhar coloca a informação em um novo nó e faz com que este nó aponte para o topo antigo. Em seguida, o topo passa a ser este novo nó.

O procedimento Desempilhar obtém a informação contida no nó do topo, retira este nó da lista encadeada e faz com que o topo seja o nó abaixo do retirado.

O procedimento Topo obtém a informação contida no nó que está no topo da pilha.

Pilha baseada em array

A implementação de uma pilha usando array é muito semelhante a uma lista encadeada. A principal diferença é que não podemos tirar elementos do meio da pilha, podendo fazê-lo apenas no topo da pilha que corresponde ao último elemento preenchido do array.

Graficamente teríamos:

A pilha só precisa de uma variável que indica qual é o último elemento preenchido do array. As inserções (Empilhamento) e remoções (Desempilhamento) são feitas sempre, respectivamente, após o topo ou nele.

Após a Inicialização, teríamos:

Depois de empilhar A, B, C:

Depois de desempilhar 1 item (obrigatoriamente C):

Fila

Definição: É uma lista na qual as inserções são feitas em uma extremidade chamada "cauda" ou "fundo", e as remoções são feitas na outra extremidade, chamada "cabeça" ou "frente".

Numa fila, o primeiro a entrar é o primeiro a sair. Esta política de acesso é denominada FIFO ("First In, First Out"). Ilustrando teríamos:

A tabela abaixo descreve as principais operações:

Operação	Descrição
Inicializar	Cria uma fila vazia.
Inserir	Insere um elemento no fundo (cauda) da fila.
Retirar	Retira um elemento que está na frente (cabeça) da fila.
Frente	Retorna o elemento que está na frente (cabeça) da fila.
Vazia	Indica se a fila está vazia.

Há basicamente 2 formas de implementar uma fila:

Usando uma lista encadeada:
1. O elemento inserido é colocado no fim da lista (cauda).
2. A retirada é feita no início (cabeça).
Usando um array:
1. há duas variáveis (Início e Fim) que indicam as extremidades da fila (cabeça e cauda).
2. Ao retirar um elemento, isto é feito na posição Início.
3. Ao inserir, o novo elemento é colocado na posição Fim + 1.

Fila baseada em lista encadeada

Inserindo A e B:

Retirando o elemento da frente (A):

Inserindo C:

Para ver uma implementação de uma Fila usando lista encadeada, abra a unit FilaE. Para ver um programa de exemplo que usa uma Fila e uma Pilha para descobrir se uma string é um palíndromo. Abra o programa Palindromo.

Os procedimentos/funções Vazia, Cheia e Tamanho são semelhantes aos da lista encadeada, mudando apenas o tipo do parâmetro passado.

Fila baseada em array

A implementação de uma fila é semelhante à de uma lista seqüencial onde as inserções são feitas no final da lista e as remoções no início.

Fila Vazia:

Inserindo A e B:

Retirando o elemento da frente (A):

Inserindo C:

Graficamente teríamos:

Para evitar que a cada retirada de um item da fila seja necessário deslocar todos os elementos do array para a "esquerda", usamos três variáveis: Início, Fim e Tamanho.

Inicio = 0 Fim = 0 Tamanho = 0	Inicio = 1 Fim = 4 Tamanho = 4	Inicio = 2 Fim = 4 Tamanho = 3
Inicio = 3 Fim = 4 Tamanho = 2	Inicio = 3 Fim = 1 Tamanho = 3	Inicio = 3 Fim = 2 Tamanho = 4

Funcionamento geral da Inserção

if tamanho < Max then
   begin
      Fim := (Fim mod Max) + 1;
      itens[Fim] := item;
      inc(tamanho)
   end
else
   begin
      writeln('Fila Cheia');
      halt;
   end;

Funcionamento geral da Retirada

if tamanho > 0 then
   begin
      item := itens[Inicio];
      inicio := (Inicio mod Max) + 1;
      dec(tamanho)
   end
else
   begin
      writeln('Fila Vazia');
      halt;
   end;