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