A deque or double-ended queue is a data structure that allows efficient addition and removal at either end. It may also support accessing elements by index, as this implementation does.
This deque is implemented as a dynamic array of fixed-size arrays. The first array is filled from right to left, and the last one from left to right, as shown in the following diagram:
When an array at either end becomes full, a new one is added, and when one is emptied, it is removed.
Here is the header file:
#ifndef DEQUE_H #define DEQUE_H #include <dynarray.h> typedef struct { dynarray *arrays; unsigned int arraysize; unsigned int front; unsigned int back; unsigned int firstempty; unsigned int lastempty; unsigned int count; } deque; typedef void (*deque_forfn)(void*); deque * deque_create(void); void deque_delete(deque * queue); void deque_push_front(deque * queue, void * data); void deque_push_back(deque * queue, void * data); void * deque_pop_front(deque * queue); void * deque_pop_back(deque * queue); void * deque_get_at(const deque *queue, unsigned int index); void * deque_set_at(deque *queue, unsigned int index, void * data); void * deque_peek_front(const deque * queue); void * deque_peek_back(const deque * queue); void deque_for_each(const deque * queue, deque_forfn fun); #endif /* DEQUE_H */
The implementation:
#include <stdlib.h> #include <deque.h> deque * deque_create(void) { deque *queue = malloc(sizeof(deque)); if (queue) { queue->arrays = dynarray_create(0); queue->arraysize = 4; queue->firstempty = 1; queue->lastempty = 1; queue->count = 0; dynarray_add_head(queue->arrays, malloc(queue->arraysize * sizeof(void*))); } return queue; } void deque_delete(deque * queue) { if (queue) { dynarray_for_each(queue->arrays, free); dynarray_delete(queue->arrays); free(queue); } } void deque_push_front(deque * queue, void * data) { unsigned int index; if (queue->count == 0) { /* Adding the first element */ index = queue->arraysize / 2; } else if (queue->firstempty) { /* There is an empty array at the beginning */ index = queue->arraysize - 1; } else if (queue->front == 0) { /* Beginning array is full - add another */ dynarray_add_head(queue->arrays, malloc(queue->arraysize * sizeof(void*))); index = queue->arraysize - 1; } else { index = queue->front - 1; } ((void**)dynarray_get(queue->arrays, 0))[index] = data; queue->front = index; queue->firstempty = 0; if (queue->arrays->count == 1) { queue->lastempty = 0; } queue->count++; if (queue->count == 1) { queue->back = queue->front; } } void deque_push_back(deque * queue, void * data) { unsigned int index; if (queue->count == 0) { /* Adding the first element */ index = queue->arraysize / 2; } else if (queue->lastempty) { /* There is an empty array at the end */ index = 0; } else if (queue->back == queue->arraysize - 1) { /* End array is full - add another */ dynarray_add_tail(queue->arrays, malloc(queue->arraysize * sizeof(void*))); index = 0; } else { index = queue->back + 1; } ((void**)dynarray_get(queue->arrays, queue->arrays->count - 1))[index] = data; queue->back = index; queue->lastempty = 0; if (queue->arrays->count == 1) { queue->firstempty = 0; } queue->count++; if (queue->count == 1) { queue->front = queue->back; } } void * deque_pop_front(deque * queue) { void *data = NULL; if (queue->count) { if (queue->firstempty) { /* There is an empty array at the beginning */ free(dynarray_remove_head(queue->arrays)); queue->firstempty = 0; } data = ((void**)dynarray_get(queue->arrays, 0))[queue->front]; queue->front++; if (queue->front == queue->arraysize) { /* First array is now empty */ queue->firstempty = 1; queue->front = 0; } queue->count--; if (queue->count == 1) { queue->back = queue->front; } else if (queue->count == 0 && queue->arrays->count == 2) { /* Both arrays are empty - remove either one */ free(dynarray_remove_head(queue->arrays)); } } return data; } void * deque_pop_back(deque * queue) { void *data = NULL; if (queue->count) { if (queue->lastempty) { /* There is an empty array at the end */ free(dynarray_remove_tail(queue->arrays)); queue->lastempty = 0; } data = ((void**)dynarray_get(queue->arrays, queue->arrays->count - 1))[queue->back]; if (queue->back == 0) { /* Last array is now empty */ queue->lastempty = 1; queue->back = queue->arraysize - 1; } else { queue->back--; } queue->count--; if (queue->count == 1) { queue->front = queue->back; } else if (queue->count == 0 && queue->arrays->count == 2) { /* Both arrays are empty - remove either one */ free(dynarray_remove_tail(queue->arrays)); } } return data; } void * deque_get_at(const deque *queue, unsigned int index) { void * data = NULL; if (index < queue->count) { const unsigned int pos = index + queue->front; data = ((void**)dynarray_get(queue->arrays, pos / queue->arraysize + queue->firstempty))[pos % queue->arraysize]; } return data; } void * deque_set_at(deque *queue, unsigned int index, void * data) { void * result = NULL; if (index == queue->count) { deque_push_back(queue, data); } else if (index < queue->count) { const unsigned int pos = index + queue->front; result = deque_get_at(queue, index); ((void**)dynarray_get(queue->arrays, pos / queue->arraysize + queue->firstempty))[pos % queue->arraysize] = data; } return result; } void * deque_peek_front(const deque * queue) { void *data = NULL; if (queue->count > 0) { data = ((void**)dynarray_get(queue->arrays, queue->firstempty))[queue->front]; } return data; } void * deque_peek_back(const deque * queue) { void *data = NULL; if (queue->count > 0) { data = ((void**)dynarray_get(queue->arrays, dynarray_get_count(queue->arrays) - 1 - queue->lastempty))[queue->back]; } return data; } void deque_for_each(const deque * queue, deque_forfn fun) { unsigned int i; for (i = 0; i < queue->count; i++) { fun(deque_get_at(queue, i)); } }
How would this work for a linked list based deque?
Hi, Todd. This is a different design from a linked list based deque. This design is preferable to a linked list because it allows indexed access in O(1) time, and has better cache performance because the storage is more contiguous.
That’s interesting, I wasn’t aware array’s were preferred for those reasons, granted I’m quite new to learning data structures.
I take it that it’s the same for stack based array/linked list relationship then?
It wouldn’t make so much difference for a stack as you don’t usually have indexed access to a stack, and pushing or popping a linked list or array-based stack are both O(1).
Array based stack would again be more cache-friendly though.