Tipos de Dados Abstractos

Interface

O exemplo seguinte (adaptado de Sedgewick) apresenta a interface de uma pilha. A interface define as operações de inicialização (STACKinit), teste de pilha vazia (STempty), e inserção/remoção de elementos (STACKpush/STACKpop). Note-se que este tipo de dados abstracto não é de 1ª ordem.

   #ifndef __STACK_H__
   #define __STACK_H__

   #include "Item.h"

   void STACKinit(int);
   int  STACKempty();
   void STACKpush(Item);
   Item STACKpop();

   #endif

Implementação

Implementação com vector

 #include <stdlib.h>
 #include "Item.h"
 #include "STACK.h"

 static Item *s;
 static int   N;

 void STACKinit (int maxN) { s = malloc(maxN * sizeof(Item)); N = 0; }
 int  STACKempty()         { return N == 0; }
 void STACKpush (Item it)  { s[N++] = it;   }
 Item STACKpop  ()         { return s[--N]; } /* e se N≤0? */

Implementação com lista

 #include <stdlib.h>
 #include "Item.h"
 
 typedef struct STACKnode *link;
 struct STACKnode {
   Item item;
   link next;
 };
 static link head;
 
 link NEW(Item item, link next) {
   link x = malloc(sizeof *x);
   x->item = item; x->next = next; return x; 
 }
 
 void STACKinit(int maxN)      { head = NULL; }
 int  STACKempty()             { return head == NULL; }
 void STACKpush(Item item)     { head = NEW(item, head); }
 Item STACKpop() {
   Item item = head->item;   /* problema: e se a pilha está vazia? */
   link t    = head->next;
   free(head);
   head = t;
   return item;
 }