|
|
| Line 1: |
Line 1: |
| | == Interface == | | == 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.
| + | * [[Tipos de Dados Abstractos: Pilha#Interface|Pilha]] |
| − | | + | * [[Tipos de Dados Abstractos: Fila#Interface|Fila]] |
| − | #ifndef __STACK_H__
| |
| − | #define __STACK_H__
| |
| − |
| |
| − | #include "Item.h"
| |
| − |
| |
| − | void STACKinit(int);
| |
| − | int STACKempty();
| |
| − | void STACKpush(Item);
| |
| − | Item STACKpop();
| |
| − |
| |
| − | #endif
| |
| | | | |
| | == Implementação == | | == Implementação == |
| | | | |
| − | === Implementação com vector ===
| + | * [[Tipos de Dados Abstractos: Pilha#Implementação|Pilha]] |
| − | | + | * [[Tipos de Dados Abstractos: Fila#Implementação|Fila]] |
| − | #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 == | | == Cliente == |
| | | | |
| − | === Conversor de notação ''infix'' para notação ''postfix'' ===
| + | * [[Tipos de Dados Abstractos: Pilha#Cliente|Pilha]] |
| − | | + | * [[Tipos de Dados Abstractos: Fila#Cliente|Fila]] |
| − | #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());
| |
| − | }
| |