struct dqueue { int start; int size; int buffer_size; void *buffer[]; };The buffer will be considered circular, i.e. element zero of the buffer is considered located after the last element.
Considering circularity, at any point in time, the buffer will contain a contiguous block of elements, and another contiguous block of unused space. The start field will contain the index in the buffer containing the first element of the queue. The size field contains the number of elements in the queue. The buffer_size field contains the size of the buffer, i.e. the number of elements it can hold before it needs to be resized. Finally, the buffer field contains a pointer to the beginning of the buffer itself.
Here is the create function:
dqueue dq_create(void) { dqueue q = malloc(sizeof(struct dqueue)); q -> start = 0; q -> size = 0; q -> buffer_size = 4; q -> buffer = calloc(4, sizeof(void *)); return q; }Notice the use of calloc which will initialize the contents of the buffer to zero, usually equivalent to NULL.
Another easy part is the test for whether the queue is empty:
int dq_empty(dqueue q) { return q -> size == 0; }We shall use a local procedure to change the size of the buffer whenever necessary:
static void change_size(dqueue q, int new_size) { void *new_buffer[] = calloc(new_size, sizeof(void *)); if(q -> start + q -> size >= q -> buffer_size) { /* then the buffer wraps around */ int size1 = q -> start + q -> size - q -> buffer_size; int size2 = q -> buffer_size - q -> start; memcpy(new_buffer, q -> buffer + q -> start, size2 * sizeof(void *)); memcpy(new_buffer + size2, q -> buffer, size1 * sizeof(void *)); } else { /* no wraparound */ memcpy(new_buffer, q -> buffer + q -> start, q -> size * sizeof(void *)); } q -> start = 0; q -> buffer_size = new_size; free(q -> buffer); q -> buffer = new_buffer; }Notice that we always copy the block to the beginning of the new buffer.
Now, all that remains is to write the enqueue and dequeue functions. They are now relatively easy:
void dq_enq_front(dqueue q, void *element) { if(q -> size == q -> buffer_size) change_size(q, 2 * q -> buffer_size); q -> start = q -> start == 0 ? q -> buffer_size - 1 : q -> start - 1; q -> buffer[q -> start] = element; } void dq_enq_back(dqueue q, void *element) { if(q -> size == q -> buffer_size) change_size(q, 2 * q -> buffer_size); if(q -> start + q -> size >= q -> buffer_size) q -> buffer[q -> start + q -> size - q -> buffer_size] = element; else q -> buffer[q -> start + q -> size] = element; q -> size++; } void * dq_deq_front(dqueue q) { assert(!dq_empty(q)); { void *element = q -> buffer[q -> start]; q -> start++; q -> size--; if(q -> start == q -> buffer_size) q -> start = 0; if(q -> size < q -> buffer_size / 2 && q -> buffer_size > 4) change_size(q, q -> buffer_size / 2); return element; } } void * dq_deq_end(dqueue q) { assert(!dq_empty(q)); { int lastpos = q -> start + q -> size - 1; if(lastpos >= q -> buffer_size) lastpos -= q -> buffer_size; { void *element = q -> buffer[lastpos]; q -> size--; if(q -> size < q -> buffer_size / 2 && q -> buffer_size > 4) change_size(q, q -> buffer_size / 2); return element; } } }As you can see, these routines are still much more complicated than the corresponding ones using lists.