|
|
| (One intermediate revision by the same user not shown) |
| 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>
| + | == Cliente == |
| − | #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 ===
| + | * [[Tipos de Dados Abstractos: Pilha#Cliente|Pilha]] |
| − | | + | * [[Tipos de Dados Abstractos: Fila#Cliente|Fila]] |
| − | #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 ==
| |