Um exemplo de pilha encadeada

Um bom exemplo de estruturas dinâmicas de dados é uma biblioteca de pilha simples que utiliza uma lista dinâmica e inclui funções init, clear, push e pop. O arquivo de cabeçalho da biblioteca tem o seguinte aspecto: 
  /* Biblioteca Estática. Esta biblioteca oferece as
     operações básicas de pilha para uma 
     pilha de inteiros (facilmente alterável) */

  typedef int stack_data;

  extern void stack_init();
  /* Inicializa esta biblioteca.
     Chama primeiro antes de chamar qualquer outra coisa. */

  extern void stack_clear();
  /* Apaga todas as entradas da pilha. */

  extern int stack_empty();
  * Retorna 1 se a pilha estiver vazia, caso contrário, 0. */ 
  
  extern void stack_push(stack_data d);
  /* Força o valor d na pilha. */   

  extern stack_data stack_pop();
  /* Retorna o elemento de cima da pilha,
     e o remove. Retorna lixo se a pilha estiver vazia. */

O arquivo de código da biblioteca vem a seguir: 

  #include "stack.h" 
  #include <stdio.h>
   
 /* Biblioteca Estática. Esta biblioteca oferece as
    operações básicas de pilha para uma pilha de inteiros */

  struct stack_rec
  { 
     stack_data data;
     struct stack_rec *next;
  }; 

  struct stack_rec *top=NULL;

  void stack_init()
  /* Inicializa esta biblioteca.
  Chama antes de chamar qualquer outra coisa. */
  { 
     top=NULL; 
  }    
  void stack_clear()
  /* Apaga todas as entradas da pilha. */
  {
      stack_data x;

      while (!stack_empty())
      x=stack_pop();
  }

  int stack_empty()
  /* Retorna 1 se a pilha estiver vazia, caso contrário, 0. */
  {
      if (top==NULL)
          return(1);
      else
          return(0);
  }
  
  void stack_push(stack_data d)
  /* Força o valor d na pilha. */
  {
      struct stack_rec *temp;
      temp=
    (struct stack_rec *)malloc(sizeof(struct stack_rec));
      temp->data=d;
      temp->next=top;
      top=temp;
  } 
   stack_data stack_pop()
  /* Retorna o elemento de cima da pilha,
     e o remove. Retorna lixo se a pilha estiver vazia. */
  {
      struct stack_rec *temp;
      stack_data d=0;
      if (top!=NULL)
      {
          d=top->data;
          temp=top; 
          top=top->next;
          free(temp);
      }
      return(d);
  }

Observe como esta biblioteca realiza a ocultação de informações: quem vir apenas o arquivo de cabeçalho não poderá dizer se a pilha é implementada com matrizes, ponteiros, arquivos ou de outro modo. Observe também que a linguagem C usa NULL. NULL está definido em stdio.h, de forma que quase sempre você terá que incluir stdio.h quando usar ponteiros. NULL é o mesmo que zero.

Tente isto
  • Adicione uma função dup, count e add para a biblioteca de pilha duplicar o elemento do topo da pilha, retornar uma soma do número de elementos na pilha e adicionar os dois elementos de cima da pilha. Crie um programa de driver e um makefile e compile a biblioteca de pilha com o driver para verificar se funciona.

Erros que devem ser evitados na linguagem C
  • Esquecer de incluir os parênteses quando você fizer referência a um registro, como em (*p).i acima.
  • Falhar em descartar um bloco alocado. Por exemplo, você não deve dizer top=NULL na função stack, pois tal ação deixa órfãos os blocos que precisam ser descartados.
  • Esquecer de incluir stdio.h com qualquer operação de ponteiro, de forma que tenha acesso a NULL.