Line 8: | Line 8: | ||
#include "Item.h" | #include "Item.h" | ||
− | void STACKinit(int); | + | void '''STACKinit'''(int); |
− | int STACKempty(); | + | int '''STACKempty'''(); |
− | void STACKpush(Item); | + | void '''STACKpush'''(Item); |
− | Item STACKpop(); | + | Item '''STACKpop'''(); |
#endif | #endif | ||
Line 26: | Line 26: | ||
static int N; | static int N; | ||
− | void STACKinit (int maxN) { s = malloc(maxN * sizeof(Item)); N = 0; } | + | void '''STACKinit''' (int maxN) { s = malloc(maxN * sizeof(Item)); N = 0; } |
− | int STACKempty() { return N == 0; } | + | int '''STACKempty'''() { return N == 0; } |
− | void STACKpush (Item it) { s[N++] = it; } | + | void '''STACKpush''' (Item it) { s[N++] = it; } |
− | Item STACKpop () { return s[--N]; } /* e se N≤0? */ | + | Item '''STACKpop''' () { return s[--N]; } /* e se N≤0? */ |
=== Implementação com lista === | === Implementação com lista === | ||
Line 48: | Line 48: | ||
} | } | ||
− | void STACKinit(int maxN) { head = NULL; } | + | void '''STACKinit'''(int maxN) { head = NULL; } |
− | int STACKempty() { return head == NULL; } | + | int '''STACKempty'''() { return head == NULL; } |
− | void STACKpush(Item item) { head = NEW(item, head); } | + | void '''STACKpush'''(Item item) { head = NEW(item, head); } |
− | Item STACKpop() { | + | Item '''STACKpop'''() { |
Item item = head->item; /* problema: e se a pilha está vazia? */ | Item item = head->item; /* problema: e se a pilha está vazia? */ | ||
link t = head->next; | link t = head->next; | ||
Line 73: | Line 73: | ||
int i, N = strlen(a); | int i, N = strlen(a); | ||
− | STACKinit(N); | + | '''STACKinit'''(N); |
for (i = 0; i < N; i++) { | for (i = 0; i < N; i++) { | ||
− | if (a[i] == ')') printf("%c ", STACKpop()); | + | if (a[i] == ')') printf("%c ", '''STACKpop'''()); |
− | if (a[i] == '+' || a[i] == '*') STACKpush(a[i]); | + | if (a[i] == '+' || a[i] == '*') '''STACKpush'''(a[i]); |
if (a[i] >= '0' && a[i] <= '9') printf("%c ", a[i]); | if (a[i] >= '0' && a[i] <= '9') printf("%c ", a[i]); | ||
} | } | ||
Line 98: | Line 98: | ||
int i, N = strlen(a); | int i, N = strlen(a); | ||
− | STACKinit(N); | + | '''STACKinit'''(N); |
for (i = 0; i < N; i++) { | for (i = 0; i < N; i++) { | ||
− | if (a[i] == '+') STACKpush(STACKpop() + STACKpop()); | + | if (a[i] == '+') '''STACKpush'''('''STACKpop'''() + '''STACKpop'''()); |
− | if (a[i] == '*') STACKpush(STACKpop() * STACKpop()); | + | if (a[i] == '*') '''STACKpush'''('''STACKpop'''() * '''STACKpop'''()); |
− | if (DIGIT(a[i])) STACKpush(0); | + | if (DIGIT(a[i])) '''STACKpush'''(0); |
− | while (DIGIT(a[i])) STACKpush(10 * STACKpop() + (a[i++] - '0')); | + | while (DIGIT(a[i])) '''STACKpush'''(10 * '''STACKpop'''() + (a[i++] - '0')); |
} | } | ||
− | printf("%d \n", STACKpop()); | + | printf("%d \n", '''STACKpop'''()); |
} | } |
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
#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? */
#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; }
#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"); }
#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()); }