Tipos de Dados Abstractos: Pilha

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;
 }

Cliente

Conversor de notação infix para notação postfix

 #include <stdio.h>
 #include <string.h>
 
 #include "Item.h"   /* também é incluído via STACK.h; define Item como char */
 #include "STACK.h"
 
 main(int argc, char *argv[]) {
   char  *a = argv[1];
   int i, N = strlen(a);
 
   STACKinit(N);
 
   for (i = 0; i < N; i++) {
     if (a[i] == ')')                printf("%c ", STACKpop()); 
     if (a[i] == '+' || a[i] == '*') STACKpush(a[i]);
     if (a[i] >= '0' && a[i] <= '9') printf("%c ", a[i]); 
   }
 
   printf("\n");
 }

Calculadora RPN

 #include <stdio.h>
 #include <string.h>
 
 #include "Item.h" /* também é incluído via STACK.h; define Item como int */
 #include "STACK.h"
 
 #define DIGIT(d) (a[i] >= '0' && a[i] <= '9')
 
 main(int argc, char *argv[])  {
   char  *a = argv[1];
   int i, N = strlen(a);
 
   STACKinit(N);
 
   for (i = 0; i < N; i++) {
     if (a[i] == '+') STACKpush(STACKpop() + STACKpop());
     if (a[i] == '*') STACKpush(STACKpop() * STACKpop());
 
     if    (DIGIT(a[i])) STACKpush(0);
     while (DIGIT(a[i])) STACKpush(10 * STACKpop() + (a[i++] - '0')); 
   }
 
   printf("%d \n", STACKpop());
 }