Anhanguera engenharia do softwaerw

Disciplina: Algoritmos e Estrutura de Dados
Conteúdo da aula: Pilhas – Aplicações e Implementações.
Livro Tenembaum pág. 86

Pilha

Motivação
Pilha é uma estrutura simples e por essa razão é muito utilizada em programação, inclusive é implementada diretamente no hardware das máquinas. Podemos fazer uma analogia de pilhas com se fosse uma pilha de pratos. Ao colocarmos um prato na pilha, normalmente o colocamos no topo. Ao retirá-lo também o retiramos do topo.

Conceito
Seu conceito é descrito através da sigla LIFO (last in, first out), o primeiro que sai é o último que entrou. Isto é, os elementos da pilhas são retirados na ordem inversa a que entrou.
O último elemento da pilha é chamado de topo da pilha, sendo assim, quando um novo elemento é inserido na pilha, este passa a ser o novo topo da pilha, por conseqüência ele é o único elemento que podemos sair da pilha. Quando o elemento do topo é eliminado, o elemento anterior passa a ser o novo topo da pilha.

Operações
Existem duas operações básicas: • Empilhar um novo elemento, inserindo-o no topo. • Desempilhar um elemento, removendo-o do topo.

É comum chamar essas operações com seus termos em inglês push (empilhar) e pop (desempilhar).

A figura abaixo exemplifica o conceito de pilha:

push (a) | |push (b) | |push (c) | |pop ( ) | |push (d) | | | | | | | | |retorna c | | | | | | | | | | | | | | | | | | | |c |topo | | |d |topo | | | |b |topo |b | |b |topo |b | | |a |topo |a | |a | |a | |a | | |
Objeto de estudo
Veremos as seguintes operações para manipular e acessar as informações da pilha: • Criar uma estrutura de pilha. • Inserir um elemento no topo. • Remover o elemento do topo. • Verificar se a pilha está vazia.

Podemos representar a pilha através de um vetor. É comum sabermos a quantidade máxima de elementos que podem ser armazenados na pilha, ou seja, neste caso, a estrutura pilha tem seu limite conhecido.
Dado um vetor conhecido para armazenar