Codigo de uma pilha (ed)

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1364 palavras )
  • Download(s) : 0
  • Publicado : 24 de março de 2013
Ler documento completo
Amostra do texto
Pilhas



Pilhas são listas onde a inserção de um novo item ou a remoção de um item já existente se dá em uma única extremidade, no topo.





Pilha vazia





Insere(A)





Insere(B)





Retira(B)



Insre(C)



Retira(C)



Retira(A)





Definição

Dada uma pilha P=( a(1), a(2), ..., a(n) ), dizemos que a(1) é o elemento da base da pilha;a(n) é o elemento topo da pilha; e a(i+1) está acima de a(i).

Pilhas são também conhecidas como listas LIFO (Last In First Out).

Operações Associadas:

criar (P) - criar uma pilha P vazia

inserir (x, P) - insere x no topo de P (empilha): push(x,P)

vazia (P) - testa se P está vazia

topo (P) - acessa o elemento do topo da pilha (sem eliminar)

elimina (P) - elimina o elemento dotopo de P (desempilha): pop(P)



Exemplo do Uso de Pilhas

Chamadas de procedimentos

Suponha a seguinte situação:

[pic]

Quando o procedimento A1 é executado, ele efetua uma chamada a A2, que deve carregar consigo o endereço de retorno e1. Ao término de A2, o processamento deve retornar ao A1, no devido endereço.

Situação idêntica ocorre em A2 e A3.

Assim, quando umprocedimento termina, é o seu endereço de retorno que deve ser consultado. Portanto, há uma lista implícita de endereços (e0, e1, e2, e3) que deve ser manipulada como uma pilha pelo sistema, onde e0 é o endereço de retorno de A1.

No caso de processamento recursivo - por exemplo uma chamada a A2 dentro de A4 - o gerenciamento da lista como uma pilha resolve automaticamente a obtenção dos endereços deretorno na ordem apropriada (e0, e1, e2, e3, e4).



Implementação de Pilhas

Como lista Seqüencial ou Encadeada ?

No caso geral de listas ordenadas, a maior vantagem da alocação encadeada sobre a seqüencial - se a memória não for problema - é a eliminação de deslocamentos na inserção ou eliminação dos elementos. No caso das pilhas, essas operações de deslocamento não ocorrem.Portanto, podemos dizer que a alocação seqüencial é mais vantajosa na maioria das vezes.

Um outro modo de se implementar pode ser feito utilizando pilhas múltiplas.

Alocação Sequencial de Pilhas



Definição da Estrutura de Dados

Type

pilha = array [1..maxp] of TipoElem;

indice = 0 .. maxp;

Var

P: pilha;

topo: indice;



[pic]



Operações:1. criar (P) - criar uma pilha P vazia

procedure criar (Var topo:indice);

begin

topo := 0;

end;



2. inserir (x, P) - insere x no topo de P(empilha): push (x, P).

procedure push (x:TipoElem; var P: pilha; Var topo:indice);

begin

if topo = maxp then

"PILHA CHEIA"

else

begin

topo := topo + 1;

P[topo]:= x;

end

end;



3. vazia (P) - testa se P está vazia

function vazia (topo: indice): boolean;

begin

vazia := (topo = 0);

end;



4. topo (P) - acessa o elemento do topo da pilha (sem eliminar)

procedure top (Var topo_p: TipoElem; P:pilha; topo:indice);

begin

if topo = 0 then

"PILHA VAZIA"

else topo_p := P[topo];end;



5. elimina (P) - elimina o elemento do topo de P (desempilha): pop (P)

procedure pop (var P:pilha; Var topo:indice);

begin

if topo = 0 then

"PILHA VAZIA"

else topo := topo-1;

end;



Devolve elemento eliminado

procedure pop_up (var topo_p:TipoElem; var P:pilha;

var topo:indice);

begin

if topo = 0 then"PILHA VAZIA"

else

begin

topo_p := P[topo]; {no caso de acesso ao elemento}

topo := topo-1;

end;

end;



Alocação Encadeada de Pilhas

Definição da Estrutura de Dados

Type

tpont = ^reg_pilha;

pilha = tpont;

reg_pilha = record

info: TipoElem;

lig: tpont;...
tracking img