Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2249 palavras )
  • Download(s) : 0
  • Publicado : 11 de julho de 2012
Ler documento completo
Amostra do texto
11. Pilhas
W. Celes e J. L. Rangel Uma das estruturas de dados mais simples é a pilha. Possivelmente por essa razão, é a estrutura de dados mais utilizada em programação, sendo inclusive implementada diretamente pelo hardware da maioria das máquinas modernas. A idéia fundamental da pilha é que todo o acesso a seus elementos é feito através do seu topo. Assim, quando um elemento novo éintroduzido na pilha, passa a ser o elemento do topo, e o único elemento que pode ser removido da pilha é o do topo. Isto faz com que os elementos da pilha sejam retirados na ordem inversa à ordem em que foram introduzidos: o primeiro que sai é o último que entrou (a sigla LIFO – last in, first out – é usada para descrever esta estratégia). Para entendermos o funcionamento de uma estrutura de pilha, podemosfazer uma analogia com uma pilha de pratos. Se quisermos adicionar um prato na pilha, o colocamos no topo. Para pegar um prato da pilha, retiramos o do topo. Assim, temos que retirar o prato do topo para ter acesso ao próximo prato. A estrutura de pilha funciona de maneira análoga. Cada novo elemento é inserido no topo e só temos acesso ao elemento do topo da pilha. Existem duas operações básicasque devem ser implementadas numa estrutura de pilha: a operação para empilhar um novo elemento, inserindo-o no topo, e a operação para desempilhar um elemento, removendo-o do topo. É comum nos referirmos a essas duas operações pelos termos em inglês push (empilhar) e pop (desempilhar). A Figura 10.1 ilustra o funcionamento conceitual de uma pilha.
push (a) push (b) push (c) pop () retorna-se cpush (d) pop () retorna-se d

a

topo

b a

topo

c b a

topo b a topo

d b a

topo

b a

topo

Figura 10.1: Funcionamento da pilha.

O exemplo de utilização de pilha mais próximo é a própria pilha de execução da linguagem C. As variáveis locais das funções são dispostas numa pilha e uma função só tem acesso às variáveis que estão no topo (não é possível acessar as variáveisda função locais às outras funções). Há várias implementações possíveis de uma pilha, que se distinguem pela natureza dos seus elementos, pela maneira como os elementos são armazenados e pelas operações disponíveis para o tratamento da pilha.

Estruturas de Dados –PUC-Rio

10-1

11.1. Interface do tipo pilha
Neste capítulo, consideraremos duas implementações de pilha: usando vetor eusando lista encadeada. Para simplificar a exposição, consideraremos uma pilha que armazena valores reais. Independente da estratégia de implementação, podemos definir a interface do tipo abstrato que representa uma estrutura de pilha. A interface é composta pelas operações que estarão disponibilizadas para manipular e acessar as informações da pilha. Neste exemplo, vamos considerar a implementação decinco operações: • criar uma estrutura de pilha; • inserir um elemento no topo (push); • remover o elemento do topo (pop); • verificar se a pilha está vazia; • liberar a estrutura de pilha. O arquivo pilha.h, que representa a interface do tipo, pode conter o seguinte código:
typedef struct pilha Pilha; Pilha* cria (void); void push (Pilha* p, float v); float pop (Pilha* p); int vazia (Pilha* p);void libera (Pilha* p);

A função cria aloca dinamicamente a estrutura da pilha, inicializa seus campos e retorna seu ponteiro; as funções push e pop inserem e retiram, respectivamente, um valor real na pilha; a função vazia informa se a pilha está ou não vazia; e a função libera destrói a pilha, liberando toda a memória usada pela estrutura.

11.2. Implementação de pilha com vetor
Emaplicações computacionais que precisam de uma estrutura de pilha, é comum sabermos de antemão o número máximo de elementos que podem estar armazenados simultaneamente na pilha, isto é, a estrutura da pilha tem um limite conhecido. Nestes casos, a implementação da pilha pode ser feita usando um vetor. A implementação com vetor é bastante simples. Devemos ter um vetor (vet) para armazenar os elementos da...
tracking img