Conceptually, a queue contains elements that are inserted by the enqueue operation and deleted by the dequeue operation in the same order that they were inserted. In other words, the first element to be deleted is the first one inserted. The first operation returns the first element that was inserted without affecting the contents of the queue. Finally, the empty operation is a predicate to test whether the queue has zero elements.
Here, we shall actually use only three operations, enqueue, dequeue, and empty. We will have the dequeue also do the work of first by returning the object about to be deleted.
By now, the reader should be used to using header objects in order to obtain uniform reference semantics. We will therefore go directly to a version of the queue with a separate header file and implementation file.
#ifndef QUEUE_H #define QUEUE_H struct queue; typedef struct queue *queue; /* create an empty queue */ extern queue queue_create(void); /* insert an element at the end of the queue */ extern void queue_enq(queue q, void *element); /* delete the front element on the queue and return it */ extern void *queue_deq(queue q); /* return a true value if and only if the queue is empty */ extern int queue_empty(queue q); #endif
#include "queue.h" #include "list.h" #include < stdlib.h> struct queue { list head; list tail; }; queue queue_create(void) { queue q = malloc(sizeof(struct queue)); q -> head = q -> tail = NULL; return q; } int queue_empty(queue q) { return q -> head == NULL; } void queue_enq(queue q, void *element) { if(queue_empty(q)) q -> head = q -> tail = cons(element, NULL); else { q -> tail -> next = cons(element, NULL); q -> tail = q -> tail -> next; } } void * queue_deq(queue q) { assert(!empty(q)); { void *temp = q -> head -> element; q -> head = cdr_and_free(q -> head); return temp; } }In the createoperation, we use the fact that in C, the assignment operation is an expression (and thus has a value) in order to shorted the code by one line. The value of q -> tail = NULL is itself NULL, which can be used as a value to assign to q -> head. A similar trick is used in the enq operation.
The head field in the queue structure points to the first cell of the list, which corresponds to the head of the queue (from where elements are dequeued), and the tail field points to the last cell of the list, which corresponds to the tail of the queue (where elements are enqueued). Notice the special case necessary when the queue is empty before an enqueue operation. After a dequeue operation resulting in an empty queue, the tail field will point to a list cell that is no longer allocated. This might be a problem if a garbage collector is used, as it might keep that cell (and worse, its contents) alive even though it will never be used again. In that case, another special case must be introduced in the dequeue operation, like this:
void * queue_deq(queue q) { assert(!empty(q)); { void *temp = q -> head -> element; q -> head = cdr_and_free(q -> head); if(empty(q)) q -> tail = NULL; return temp; } }
#include "queue.h" #include "list.h" #include < stdlib.h> struct queue { list head; list tail; }; queue queue_create(void) { queue q = malloc(sizeof(struct queue)); q -> head = q -> tail = cons(NULL, NULL); return q; } int queue_empty(queue q) { return q -> head == q -> tail; } void queue_enq(queue q, void *element) { q -> tail -> next = cons(NULL, NULL); q -> tail -> element = element; q -> tail = q -> tail -> next; } void * queue_deq(queue q) { assert(!empty(q)); { void *temp = q -> head -> element; q -> head = cdr_and_free(q -> head); return temp; } }With this version no special case is needed, neither in the enqueue operation nor in the dequeue operation. And the dequeue operation works fine with a garbage collector as well. The code for the enqueue operation is now 7 lines instead of 11.