PILHA
1207 palavras
5 páginas
Msc. Ruben Cruz Huacarpuma
O TAD pilha é uma abstração que permite representar uma coleção de objetos que tem as seguintes características:
◦ Os elementos são insertados unicamente por um extremo e são tirados por o mesmo extremo. Tem um comportamento LIFO (Last Input First Output) –
O ultimo em entrar é o primeiro em sair.
◦ Em um momento dado, somente esta disponível um objeto (o objeto mais recente em ser insertado) no extremo por onde são retirados os objetos (Cima)
Na vida do dia a dia:
◦ Pilha de pratos
◦ Pilha de livros ... Etc.
Na Informática
◦ Chamadas a subprogramas
◦ Compiladores
◦ Avaliações de expressões matemáticas.
Uma pilha pode-se representar como uma sequencia (lista) de elementos, onde os elementos são insertados e removidos somente por um extremo.
Ponteiro à
Informação
Ponteiro ao seguinte elemento
Uma pilha pode ser representada como uma sequencia de nós, com a particularidade que um dos extremos tem o nome de “top” ou
“Cima”, os nomes são agregados pela “Cima”.
Por exemplo uma pilha de nomes de estados:
DF
cima
SP
RJ null null
A definição recursiva de uma pilha:
Pilha
n elementos
= Cima + Pilha
n-1 elementos
Similar à definição recursiva de uma lista, sempre levando em consideração a definição de pilha.
Nome do TAD: Pilha
Descrição informal do TAD: Uma pilha é uma sequencia de elementos, onde os elementos são insertados unicamente por um extremo.
Unicamente tem-se acesso ao elemento de cima. Pilha
n elementos
= Cima + Pilha
n-1 elementos
As três operações naturais sobre sequencia ou coleções de elementos: Inserir, Remover e
Buscar são equivalentes a empilhar, desempilhar e cima.
Especificação do TAD Pilha
Elementos
Pilha = (Elemento, SubPilha)
Elemento є Objeto , SubPillha є Pilha
Onde:
Objeto é uma entidade que representa qualquer objeto do mundo real.
SubPilha é uma