// Queue.h Stan Eisenstat (02/26/19) // Interface to Queue ADT #include typedef struct queue *Queue; // Queue is pointer to struct queue bool createQ (Queue *q); // Create Queue *Q bool destroyQ (Queue q); // Reclaim storage for Q bool addQ (Queue q, int n); // Add N from tail of Q bool removeQ (Queue q, int *n); // Remove *N from head of Q ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // Queue.c Stan Eisenstat (02/26/19) // Implementation of Queue ADT #include "Queue.h" #include #include // This implementation of the Queue ADT uses a "circular" array of length MAX, // the number F of entries removed (initially 0), and the number R of entries // added (initially -1). #define MAX 10 struct queue {int v[MAX]; long f, r;}; // Internal struct for Queue bool createQ (Queue *q) { if ((*q = malloc (sizeof (**q))) == NULL) return false; (*q)->f = 0; (*q)->r = -1; return true; } bool destroyQ (Queue q) { free (q); return true; } bool addQ (Queue q, int n) { if (q->r == q->f + MAX-1) // Q full? return false; q->v[++q->r % MAX] = n; return true; } bool removeQ (Queue q, int *n) { if (q->r < q->f) // Q empty? return false; *n = q->v[q->f++ % MAX]; return true; } ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // testQueue.c Stan Eisenstat (02/26/19) // Program to illustrate use of Queue ADT #include #include "Queue.h" #include int main (int argc, char *argv[]) { int n, i; Queue q; if (! createQ (&q)) { printf ("Unable to create Queue\n"); return EXIT_FAILURE; } for (i = 0; addQ(q,i); i++) printf ("Added %d to Queue\n", i); printf ("Could not add %d to Queue\n", i); while (removeQ(q,&n)) printf ("Removed %d from Queue\n", n); printf ("Reached end of Queue\n"); if (! destroyQ (q)) { printf ("Unable to destroy Queue\n"); return EXIT_FAILURE; } return EXIT_SUCCESS; }