[Curso de AeED - Aula 14] - Pilhas

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, podemos fazer 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ásicas que 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 1 ilustra o funcionamento conceitual de uma pilha.

Figura 1 - Ilustração do funcionamento de uma 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áveis da 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.

Neste capítulo, consideraremos duas implementações de pilha: usando vetor e usando 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 de cinco 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.



Implementação de uma pilha dinâmica

Quando o número máximo de elementos que serão armazenados na pilha não é conhecido, devemos implementar a pilha usando uma estrutura de dados dinâmica, no caso, empregando uma lista encadeada. Os elementos são armazenados na lista e a pilha  pode ser representada simplesmente por um ponteiro para o primeiro nó da lista.

O nó da lista para armazenar valores reais pode ser dado por:

struct no {
       float info;
       struct no* prox;
}; typedef struct no No;

A estrutura da pilha é então simplesmente:

struct pilha {
       No* prim;
};

A função cria aloca a estrutura da pilha e inicializa a lista como sendo vazia.

Pilha* cria (void){
       Pilha* p = (Pilha*) malloc(sizeof(Pilha));
       p->prim = NULL;
       return p;
}

O primeiro elemento da lista representa o topo da pilha. Cada novo elemento é inserido
no início da lista e, conseqüentemente, sempre que solicitado, retiramos o elemento
também do início da lista. Desta forma, precisamos de duas funções auxiliares da lista:
para inserir no início e para remover do início. Ambas as funções retornam o novo
primeiro nó da lista.

/* função auxiliar: insere no início */
No* ins_ini (No* l, float v){
       No* p = (No*) malloc(sizeof(No));
       p->info = v;
       p->prox = l;
       return p;
}

/* função auxiliar: retira do início */
No* ret_ini (No* l){
       No* p = l->prox;
       free(l);
       return p;
}

As funções que manipulam a pilha fazem uso dessas funções de lista:

void push (Pilha* p, float v){
       p->prim = ins_ini(p->prim,v);
}

float pop (Pilha* p){
       float v;
       if (vazia(p)) {
              printf("Pilha vazia.\n");
              exit(1); /* aborta programa */
       }
       v = p->prim->info;
       p->prim = ret_ini(p->prim);
       return v;
}

A pilha estará vazia se a lista estiver vazia:

int vazia (Pilha* p){
       return (p->prim==NULL);
}

Por fim, a função que libera a pilha deve antes liberar todos os elementos da lista.

void libera (Pilha* p){
       No* q = p->prim;
       while (q!=NULL) {
              No* t = q->prox;
              free(q);
              q = t;
       }
       free(p);
}

A rigor, pela definição da estrutura de pilha, só temos acesso ao elemento do topo. No
entanto, para testar o código, pode ser útil implementarmos uma função que imprima os
valores armazenados na pilha. Os códigos abaixo ilustram a implementação dessa
função nas duas versões de pilha (vetor e lista). A ordem de impressão adotada é do
topo para a base.


[Curso de AeED - Aula 14] - Pilhas [Curso de AeED - Aula 14] - Pilhas Reviewed by Vinicius dos Santos on 14:38:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!