close
The Wayback Machine - https://web.archive.org/web/20140306145414/http://www.martinbroadhurst.com:80/articles/deque.html

Martin Broadhurst > Data Structures

Deque

Contents

Introduction

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:

Creation

Create a deque with MBdeque_create.

Adding elements

Add at the head with MBdeque_push_front, and add at the tail with MBdeque_push_back.

Removing elements

Remove from the head with MBdeque_pop_front, and remove from the tail with MBdeque_pop_back.

Accessing elements

Access elements by array index using MBdeque_get_at and MBdeque_set_at. Look at the first and last elements with MBdeque_peek_front and MBdeque_peek_back. Get an iterator over the elements with MBdeque_iterator.

Example program

#include <stdio.h>

#include <deque.h>

typedef void (*addfn)(MBdeque*, void*);
typedef void*(*removefn)(MBdeque*);

void test(MBdeque *deque, addfn addfn, removefn removefn)
{
    char * elements[] = {"A", "B", "C", "D", "E", "F"};
    unsigned int i;
    const unsigned int n = sizeof(elements) / sizeof(const char*);
    MBiterator *it;
    void *data;

    for (i = 0; i < n; i++) {
        addfn(deque, elements[i]);
    }
    printf("front is %s, back is %s\n", (const char *)MBdeque_peek_front(deque), (const char *)MBdeque_peek_back(deque));

    it = MBdeque_iterator(deque);
    while ((data = MBiterator_get(it))) {
        printf("%s\n", (const char*)data);
    }
    putchar('\n');
    MBiterator_delete(it);

    for (i = 0; i < n; i++) {
        data = removefn(deque);
        printf("%s\n", data ? (const char*)data : "NULL");
    }
    putchar('\n');
}

int main(void)
{
    addfn addfns[] = { MBdeque_push_back, MBdeque_push_front };
    removefn removefns[] = { MBdeque_pop_back, MBdeque_pop_front };
    const unsigned int nfns = sizeof(addfns) / sizeof(addfn);
    MBdeque * deque = MBdeque_create();
    unsigned int a, r;
    for (a = 0; a < nfns; a++) {
        for (r = 0; r < nfns; r++) {
            test(deque, addfns[a], removefns[r]);
        }
    }
    MBdeque_delete(deque);

    return 0;
}

Source code

Download

The following archives contain the full source code, example programs and build instructions for all of the data structures:

Copyright (C) 2010 Martin Broadhurst