Codigo de uma pilha (ed)

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 do topo 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 um procedimento 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 de retorno 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