Estrutura de dados pilhas

PILHAS

• 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 elemento em 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, ou