|
|
| (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 ==
| |