How do you implement a deque using an array in c language?

Answer 1

A deque (pronounced deck) is a double-ended queue where objects can be efficiently pushed to and popped from either end of the queue.

Arrays are not ideally suited to this task because arrays operate more efficiently when used like a stack, pushing and popping elements at the end of the array where the unused elements are. When we run out of unused elements we can reallocate the array creating more space at the end as required (typically doubling the allocation with each reallocation). For this we need to keep track of three pieces of information:

1. The start address of the array.
2. The overall length of the array in elements (size).
3. The number of unused elements at the end of the array (space).

A queue differs from a stack in that all insertions occur at the first unused element, while extractions occur at the first used element, which is initially at the start of the array. After an extraction we end up with an unused element at the start of the array. Although we could shunt all used elements by one element to eliminate the gap, it is more efficient to just keep track of the front of the queue. Thus we need 4 pieces of information:

1. The start address of the array.
2. The overall length of the array in elements (size).
3. The total number of unused elements in the array (space).
4. The index of the first element in the queue (start).

From this information it is trivial to calculate the length of the queue (size-space) and thus determine where the first unused element is using modulo arithmetic: ((start+(size-space))%size).

When we run out of space at the end of the array for an insertion, we simply use the unused elements at the beginning of the array. When we run out of space completely, we normalise the array so that the start of the queue is back at the beginning of the array before reallocating the array, thus placing all the new unused elements at the end of the array (after the last element in the queue). If we don't normalise the array, we will most likely end up with unused elements in the middle of the queue due to the circular nature of the array.

To implement a deque we use a similar technique except we can insert and extract from either end of the queue. The following program demonstrates how the major deque operations can be implemented upon an array of unsigned integers.

#include

#include

#include

#include

// a deque of unsigned integers

typedef struct arraydeque_t {

unsigned* arr; // pointer to a variable length array of type unsigned

unsigned sz; // overall length of array (in elements)

unsigned space; // unused elements

unsigned start; // index of the start of the queue

} arraydeque;

bool is_empty (arraydeque*);

unsigned size (arraydeque*);

unsigned back (arraydeque*);

unsigned front (arraydeque*);

int initialise (arraydeque*);

int push_back (arraydeque*, unsigned);

int push_front (arraydeque*, unsigned);

int expand (arraydeque*);

void pop_back (arraydeque*);

void pop_front (arraydeque*);

void clear (arraydeque*);

// calculates and returns the length of the queue

unsigned size (arraydeque* deq) {

return deq->sz-deq->space;

}

// returns true if the queue is empty

bool is_empty (arraydeque* deq) {

return deq->space==deq->sz;

}

// clear the deque

void clear (arraydeque* deq) {

if (deq->arr) free (deq->arr);

memset (deq, 0, sizeof (arraydeque));

}

// initialise the deque

int initialise (arraydeque* deq) {

const unsigned sz = 1; // start with 2 unused elements

memset (deq, 0, sizeof (arraydeque));

deq->arr = (unsigned*) malloc (sz * sizeof (unsigned));

if (!deq->arr) return -1; // out of memory

deq->sz = sz;

deq->space = sz;

return 0;

}

// increase the size of the deque (create space)

int expand (arraydeque* deq) {

unsigned space, t, i, *p;

if (deq->space) return 0; // no need to expand when we have space

// normalise the array (realign the start of the queue with the start of the array

while (deq->start) {

t = deq->arr[0]; // temporarily store first element value

for (i=1; isz; ++i) // shunt all other elements forward

deq->arr[i-1] = deq->arr[i];

deq->arr[deq->sz-1] = t; // put temporary value at end of array

--deq->start;

}

// reallocate the array to create space after the queue

space = (unsigned) (0.6 * deq->sz + 1); // optimum growth: 160%

p = (unsigned*) realloc (deq->arr, (deq->sz + space) * sizeof(unsigned));

if (!p) return -1; // out of memory

deq->arr = p;

deq->sz += space;

deq->space = space;

return 0;

}

// insert value at the back of the queue

int push_back (arraydeque* deq, unsigned val) {

if (expand (deq))

return -1; // out of memory

deq->arr[(deq->start+size (deq))%deq->sz] = val;

--deq->space;

return 0;

}

// insert value at the front of the queue

int push_front (arraydeque* deq, unsigned val) {

if (expand (deq))

return -1; // out of memory

if (!deq->start)

deq->start=deq->sz;

--deq->start;

deq->arr[deq->start] = val;

--deq->space;

return 0;

}

// extract the back value

void pop_back (arraydeque* deq) {

++deq->space;

}

// extract the front value

void pop_front (arraydeque* deq) {

++deq->start;

deq->start%=deq->sz;

++deq->space;

}

// return the back value

unsigned back (arraydeque* deq) {

return deq->arr[((deq->start + size(deq)-1)%deq->sz)];

}

// return the front value

unsigned front (arraydeque* deq) {

return deq->arr[deq->start];

}

// returns true or false at random (used by test program)

bool is_true (void) {

return rand() & 0x1;

}

// prints the content of the deque (used by test program)

void print_queue (arraydeque* deq) {

unsigned i, sz;

printf ("{");

sz = size (deq);

i = deq->start;

while (sz--) {

printf ("%u%s", deq->arr[i++], sz?", ":"");

if (i==deq->sz) i=0;

}

printf ("}\n");

}

// test program

int main (void) {

unsigned i, loop;

srand((unsigned) time(0)); // seed random generator

arraydeque deq;

initialise (&deq); // initialise the deque

for (loop=0; loop<100; ++loop) {

if (is_true ()) {

i = rand() % 10;

if (is_true ()) {

printf ("Pushing %d to the front:\t\t", i);

if (push_front (&deq, i))

break; // out of memory

}else{

printf ("Pushing %d to the back:\t\t", i);

if (push_back (&deq, i))

break; // out of memory

}

print_queue (&deq);

}

else if (is_true() && !is_empty (&deq)) {

if (is_true ()) {

printf ("Popping %u from the front:\t", front (&deq));

pop_front (&deq);

}else{

printf ("Popping %u from the back:\t", back (&deq));

pop_back (&deq);

}

print_queue (&deq);

}

}

while (!is_empty(&deq)) {

if (is_true ()) {

printf ("Popping %u from the front:\t", front (&deq));

pop_front (&deq);

}else{

printf ("Popping %u from the back:\t", back (&deq));

pop_back (&deq);

}

print_queue (&deq);

}

clear (&deq);

return 0;

}