Pilhas C++

Pilhas

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 ideia 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.
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).

Pilhas
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).

Pilhas
Funções primitivas
Dentre as funções que podem operar sobre uma pilha podemos destacar: • Criar uma estrutura de pilha.
• Inserir um elemento no topo (push).
• Remover o elemento do topo (pop).
• Verificar se a pilha está vazia (empty)
• Liberar a estrutura de pilha.

Pilhas
Funções primitivas
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);

Pilhas
Implementação de pilha com vetor
Em muitas aplicações computacionais que precisam de uma estrutura de pilha é comum sabermos de antemão o número de elementos que precisam ser armazenados na pilha. Nestes casos a implementação pode ser feita usando-se vetor.
Os elementos inseridos ocupam as primeiras posições do vetor e o topo é representado por vetor[n-1]
#define STACKSIZE 50 struct pilha { int topo;
float