• Todo acesso a seus elementos é feito a partir do topo
• Inserção de um elemento, este passa a ser o elemento do topo da pilha
• Remoção de um elemento deve ser o do topo da pilha
• Estratégia LIFO – último que entra, primeiro que sai
• Duas operações básicas: empilhar um novo elemento e desempilhar um elemento
Push (a) Push (b)Push (c) Pop ()
Conjunto de operações
• Criação - criar uma pilha vazia
• Inserção - inserir um elemento no topo (push)
• Remoção - retirar um elemento do topo (pop)
• Vazia – verifica se a pilha está vazia.
• Libera – libera a pilha.
Implementação com vetor
Estrutura
• Estrutura contendo:n = numero de elementos na pilha
Vet [N] = vetor com o número máximo de elementos que podem estar armazenados na pilha..
• Os elementos ao serem inseridos ocupam as primeiras posições do vetor.
Exemplo:
#define N 10 /* numero Maximo de elementos */
/* estrutura da pilha */
struct pilha {
int n;
float vet[N];
};
typedef struct pilha Pilha;Criação
• Aloca dinamicamente a estutura da pilha
• Inicializa a pilha como vazia. Ou seja, n = 0.
/* funçao de criação - retorna uma pilha vazia */
Pilha* pilha_cria (void)
{
Pilha* p = (Pilha*) malloc (sizeof (Pilha));
p->n = 0; /* inicializa com 0 elementos */
return p;
};
Insere
• Insere um elementoem uma pilha.
• A próxima posição livre do vetor é utilizada
• Assegurar que existe espaço livre
Insere a, depois insere b e depois insere c.
Push (a) Push (b) Push (c)
/* funçao de inserção - insere elementos no topo da pilha.
Float v = informação.
Pilha* p = pilha, ouseja, o ponteiro para a pilha (topo)*/
void pilha_push (Pilha* p, float v)
{
if (p->n == N) {
printf ("Capacidade esgotada \n");
exit (1);
}
/* insere elemento na proxima posição livre */
p->vet[p->n] = v;
p->n++;
};
Exercício
1) Pa ra uma pilha, simulara situação:
A ) inserir 1,2,3. Retira 1. insere 4, 5. Desenhar a pilha e seu ponteiro.
2) Em C: Crie a pilha, inserir 2 elementos: 23 e 45.
}
Vazia
• Verifica se a pilha está vazia.
• Recebe ponteiro para a pilha
• Retorna 1 se estiver vazia. Retorna 0 se não estiver vazia.
/* funçao verifica se a fila esta vazia. Retorna 1 se vazia, caso contrario,retorna 0.
Pilha* p = pilha, ou seja, o ponteiro para a pilha (topo)*/
int pilha_vazia (Pilha* p)
{
return (p->n == 0);
};
Retira
• Retira um elemento do topo da pilha
Push (c) Pop ()
/* funçao retira elemento da pilha
Pilha *p = pilha, ou seja, o ponteiro para a pilha (topo)Retorna v = o elemento retirado da pilha. */
float pilha_pop (Pilha* p)
{
float v;
if (pilha_vazia (p) ) {
printf ("Não existe elemento \n");
exit (1);
};
/* retira elemento do topo*/
p->n--;
v = p->vet[p->n];
return v;
};
Imprime
• Exibe oselementos da pilha.
/* funçao para exibir a pilha
Pilha *p= pilha, ou seja, o ponteiro para a pilha*/
void pilha_imprime (Pilha* p)
{
int i;
for (i = p->n –1 ; i > = 0; i --)
printf (“%f\n”, p->vet[i]);
};
Exercício
1) Em C: Retira o elemento 23. Verifique se a lista está vazia . Retira o elemento 45. Verifique se a lista...