Estrutura de dados pilhas

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1983 palavras )
  • Download(s) : 0
  • Publicado : 24 de abril de 2012
Ler documento completo
Amostra do texto
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 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...
tracking img