Pilhas

Pilhas

Onde surgiu:

O conceito de pilha foi proposto pela primeira vez em 1946, no projeto do computador de Alan M. Turing (que usou os termos "enterrar" e "desenterrar") como meio de abertura e voltando de sub-rotinas. Os alemães Klaus Samelson e Friedrich L. Bauer, da Universidade Técnica de Munique, propuseram a idéia em 1955 e solicitaram uma patente em 1957. Foi desenvolvido o mesmo conceito, de forma independente, pelo australiano Charles Leonard Hamblin no primeiro semestre de 1957.

Como pode ser implementada:

A implementação de pilhas pode ser realizada através de vetor (alocação do espaço de memória para os elementos é contígua) ou através de listas encadeadas.

Implementação de pilha com vetor
Em aplicaçõ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 ilha, 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 pilha. Os elementos inseridos ocupam as primeiras posições do vetor. Desta forma, se temos n elementos armazenados na pilha, o elemento vet[n-1]representa o elemento do topo. A estrutura que representa o tipo pilha deve, portanto, ser composta pelo vetor e pelo número de elementos armazenados.

#define MAX 50 struct pilha { int n; float vet[MAX];
};

A função para criar a pilha aloca dinamicamente essa estrutura e inicializa a pilha como sendo vazia, isto é, com o número de elementos igual a zero.

Pilha* cria (void)
{
Pilha* p = (Pilha*) malloc(sizeof(Pilha)); p->n = 0; /* inicializa com zero elementos */ return p;
}

Para inserir um elemento na pilha, usamos a próxima posição livre do vetor. Devemos ainda assegurar que exista espaço para a inserção do novo elemento, tendo em vista que trata-se de um vetor com dimensão fixa.