Tipos de Dados Abstractos: Pilha: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
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'''()); | ||
} | } |
Latest revision as of 06:50, 19 May 2005
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()); }