View source for 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 (<code>STACKinit</code>), teste de pilha vazia (<code>STempty</code>), e inserção/remoção de elementos (<code>STACKpush</code>/<code>STACKpop</code>). 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());
  }