Índice > Pilha

Instituto de Ciências Matemáticas de São Carlos 
Departamento de Computação e Estatística 
SCE182 - Algoritmos e Estruturas de Dados 1 
Profs. Resp.: Graça Pimentel e Maria Cristina

Pilha

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 

Insere(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:

1. criar (P) - criar uma pilha P vazia
2. inserir (x, P) - insere x no topo de P (empilha): push(x,P)
3. vazia (P) - testa se P está vazia
4. topo (P) - acessa o elemento do topo da pilha (sem eliminar)
5. elimina (P) - elimina o elemento do topo de P (desempilha): pop(P)
6. destruir(P) - destrói a estrutura e libera o espaço ocupado por ela.

-> Fazer a Definição do TAD pilha.

Implementação de Pilhas

Como lista Sequencial ou Encadeada ?

No caso geral de listas ordenadas, a maior vantagem da alocação encadeada sobre a sequencial - 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 sequencial é mais vantajosa na maioria das vezes.

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

Aplicação

Índice