2013/2-AED-2013.09.12: TAD Pilha

Arquivo .H

---

#include <stdio.h>
#include <stdlib.h>

// TAD Pilha
#define MAX 900000

// definição do tipochave
typedef int TipoChave;

// definição do registro tipo item
typedef struct {
  TipoChave Chave;
} TipoItem;

// definição do apontador para célula
typedef struct TipoCelula *TipoApontador;

// definição para o tipo célula
typedef struct TipoCelula {
  TipoItem Item;
  TipoApontador Prox;
} TipoCelula;

// definição do tipo pilha
typedef struct{
  TipoApontador Fundo, Topo;
  int Tamanho;
} TipoPilha;

// função que inicializa a pilha
void FPVazia(TipoPilha *Pilha);
// função que verifica se a pilha está vazia
int VaziaPilha(TipoPilha Pilha);
// função que empilha um item na pilha
void Empilha(TipoItem x, TipoPilha *Pilha);
// função que desempilha um item da pilha
void Desempilha(TipoPilha *Pilha,  TipoItem *Item);
// função que retorna o tamanho da pilha
int TamanhoPilha(TipoPilha Pilha);
// função que informa o elemento no topo da pilha
TipoItem TopoPilha(TipoPilha *Pilha);
// função que imprime o estado atual da pilha
void ImprimirPilha(TipoPilha Pilha);

// função que cria uma nova pilha
void FPVazia(TipoPilha *Pilha)
{ // cria a célula cabeça
  Pilha->Topo = (TipoApontador)
    malloc(sizeof(TipoCelula));
  // inicializa o topo e fundo
  Pilha->Fundo = Pilha->Topo;
  // inicializa o próximo do topo
  Pilha->Topo->Prox = NULL;
  // inicializa o tamanho
  Pilha->Tamanho = 0;
}

// função que verifica se a
//pilha está vazia
int VaziaPilha(TipoPilha Pilha)
{ // se a célula no topo for igual
  // a célula no fundo, ela está
  // vazia
  return (
    Pilha.Topo == Pilha.Fundo);
}


// função que empilha um item na pilha
void Empilha(TipoItem x, TipoPilha *Pilha)
{
  TipoApontador Aux;  // apontador auxiliar
  // aloca o apontador auxiliar
  Aux = (TipoApontador)
    malloc(sizeof(TipoCelula));
  // coloca o item no topo da pilha
  Pilha->Topo->Item = x;
  // célula auxiliar aponta para topo
  Aux->Prox = Pilha->Topo;
  // topo recebe auxiliar
  Pilha->Topo = Aux;
  // incrementar o tamanho da pilha
  Pilha->Tamanho++;
}

// função que desempilha o item no
// topo da pilha
void Desempilha(TipoPilha *Pilha,
  TipoItem *Item)
{ TipoApontador q;
  // se a pilha estiver vazia,
  // mostrar uma mensagem de erro
  if (VaziaPilha(*Pilha)) {
    printf("Erro: pilha vazia\n"); return;
  }
  q = Pilha->Topo; // obtem a célula no topo
  // altera o apontador para
  // apontar para o próximo
  Pilha->Topo = q->Prox;
  // obtem o item a ser removido do topo
  *Item = q->Prox->Item;
  // libera o espaço de memória alocado
  free(q);
  // diminuir o tamanho da pilha
  Pilha->Tamanho--;
}

// função para obter Tamanho da pilha
int TamanhoPilha(TipoPilha Pilha)
{ return (Pilha.Tamanho); }


// função para obter o elemento no topo da pilha
TipoItem TopoPilha(TipoPilha *Pilha)
{  TipoItem item; item.Chave = -1;
if (VaziaPilha(*Pilha) == 0){
item = Pilha->Topo->Prox->Item;
}
return (item);
}

void ImprimirPilha(TipoPilha Pilha)
{
  TipoApontador aux; TipoItem item;
  printf("Pilha Tamanho: %d -> ", Pilha.Tamanho);
  aux = Pilha.Topo;
  printf("Topo: ");
  while (aux->Prox != NULL){
 item = aux->Prox->Item;
 printf(" %3d | ", item.Chave);
 aux = aux->Prox;
  }
  printf(": Fundo\n");
}

---

Arquivo .C

---

#include "tad-pilha.h"

int main(void) {

  TipoPilha pilha; TipoItem item; int i;
  int chaves[] = {10, 11, 12, 45, 1};

  FPVazia(&pilha); // Inicializa a pilha
  printf("Pilha vazia?: %d\n", VaziaPilha(pilha)); // pilha vazia?
  item = TopoPilha(&pilha); // elemento no topo da pilha
  printf("Elemento no topo da pilha: %d\n", item.Chave);
  ImprimirPilha(pilha);

  /*Empilha cada chave */
  for (i = 0; i < 5; i++){
    item.Chave = chaves[i];
    Empilha(item, &pilha);
    printf("Empilhou: %3d => ", item.Chave);
    ImprimirPilha(pilha);
  }
  int tamPilha = TamanhoPilha(pilha); // tamanho da pilha
  printf("Tamanho da pilha: %d \n", tamPilha);
  printf("Pilha vazia?: %d\n", VaziaPilha(pilha)); // pilha vazia?
  item = TopoPilha(&pilha); // elemento no topo da pilha
  printf("Elemento no topo da pilha: %d\n", item.Chave);

  for (i = 0; i < tamPilha; i++) { /*Desempilha cada chave */
    Desempilha(&pilha, &item);
    printf("Desempilhou: %3d => ", item.Chave);
    ImprimirPilha(pilha);
  }
  printf("Tamanho da pilha: %d\n", TamanhoPilha(pilha)); // tamanho da pilha
  printf("Pilha vazia?: %d\n", VaziaPilha(pilha)); // pilha vazia?
  system("PAUSE");
  return EXIT_SUCCESS;
}