ADTs de 1ª ordem: Fila

From Wiki**3

Interface

 #ifndef __QUEUE_H__
 #define __QUEUE_H__
 
 #include "Item.h"
 
 typedef struct queue *Q;
 
 Q    QUEUEinit(int);
 int  QUEUEempty(Q);
 void QUEUEput(Q, Item);
 Item QUEUEget(Q);
 
 #endif

Implementação

Implementação baseada em lista

 #include <stdlib.h>
 #include "Item.h"
 #include "QUEUE.h"
 
 typedef struct QUEUEnode* link;
 struct QUEUEnode { Item item; link next; };
 struct queue     { link head; link tail; };
 
 link NEW(Item item, link next) {
   link x = malloc(sizeof *x);
   x->item = item; x->next = next;     
   return x;                         
 }                                   
 
 Q QUEUEinit(int maxN) {
   Q q = malloc(sizeof *q); 
   q->head = NULL;
   q->tail = NULL; 
   return q;
 }
 
 int QUEUEempty(Q q) { return q->head == NULL; }
 
 void QUEUEput(Q q, Item item) { 
   if (q->head == NULL) {
     q->tail = NEW(item, q->head);
     q->head = q->tail;
     return;
   }
 
   q->tail->next = NEW(item, q->tail->next); 
   q->tail       = q->tail->next;
 }
 
 Item QUEUEget(Q q) {
   Item item = q->head->item;
   link t    = q->head->next;
   free(q->head);
   q->head = t;
   return item;
 }

Cliente

 #include <stdio.h>
 #include <stdlib.h>
 
 #include "Item.h"  /* também incluído por QUEUE.h */
 #include "QUEUE.h"
 #define M 10
 
 main(int argc, char *argv[]) {
   int i, j, N = atoi(argv[1]); 
   Q queues[M]; 
 
   for (i = 0; i < M; i++) queues[i] = QUEUEinit(N);
   for (i = 0; i < N; i++) QUEUEput(queues[rand() % M], i);
 
   for (i = 0; i < M; i++, printf("\n"))
     for (j = 0; !QUEUEempty(queues[i]); j++) 
       printf("%3d ", QUEUEget(queues[i]));
 }