Queue Implementations for Pathfinding

Improving my Queue implementation throughout pathfinding project.

Whilst adding to my in-terminal pathfinding visualisation project (link here), I knew I would need a Queue data structure for my implementation of the Depth-First Search (DFS), a very popular algorithm in such visualisations.

For those whom are unaware, a Queue is a first in first out data structure where elements are removed from the front (dequeued) and added to the rear (enqueued). This makes sense to me given DFS’s priority for the first route chosen and then following this route until it reaches a dead end or the goal.

My first ‘make it exist’ implementation of this queue data structure looked something like this:

A cell represents a square on a 2D grid in this instance. So by dequeueing a cell pointer we get a pointer to the appropriate cell in a grid of the terminals size.

Queue* queueInit() {
    Queue *Q = malloc(sizeof(Queue));
    if (!Q) die("queueInit() -> malloc");

    Q->qu = NULL;
    Q->qu_size = 0;
    return Q;
}

Queue* enqueue(Queue *Q, struct Cell  *cell) {
    
    cell->type = OPEN;
    cell->inOpenSet = true;

    if (Q->qu_size == 0) {
        Q->qu = malloc(sizeof(*Q->qu));
    } else {
        Q->qu = realloc(Q->qu, (Q->qu_size + 1) * sizeof(Q->qu));
    }
    Q->qu[Q->qu_size++] = cell;
    return Q;
}

struct Cell* dequeue(Queue *Q) {
    struct Cell *cell = Q->qu[0];

    cell->type = CLOSED;
    cell->inOpenSet = false;
    Q->qu_size--;
    Q->qu = &Q->qu[1];
    return cell;
}

void freeQueue(Queue *Q) {
    return;
}

I’m not proud of this implementation it believe it has several problems, so lets take a look at some of them and try and improve this implementation bit-by-bit. These are some of the problems I found:

• No error checking for malloc and realloc in enqueue().
• Needlessly returning the Queue structure in enqueue().
• Appending cell states in our Queue functionality isn’t ideal, perhaps theres a better way.
• Using realloc() to request more memory upon a single addition to the queue is expensive and not required.

The first of which is quite an easy fix. We don’t error check for malloc() and realloc(), so we can simply create our own wrapper for the malloc() and realloc() functions to appropriately error-check whenever we use it. This will save ample time.

void *Malloc(size_t n)
{
    void *p = malloc(n);
    if (p == NULL) die("malloc()");
    return p;
}

void *Realloc(void **orig_ptr, size_t newsize) {
    /* realloc() with error-checks. */
    if (orig_ptr == NULL) return NULL;

    void *tmp = realloc(*orig_ptr, newsize);
    
    if (tmp == NULL) return *orig_ptr;

    *orig_ptr = tmp;
    return *orig_ptr;
}