Queue!

While the last post’s Stack is used for implementing undo functions, Queue is used for BFS, or in game design, following NPC.

Queue

LILO, or FIFO.

The class started by linear queue, which meant its Get function would be O(n).

That was not worth it, so I just went ahead and wrote circular one.

Which was a good idea as the instructor demanded us to write that and now I got free time to write this post.

Here’s the code in C:

#include <stdio.h>

#define ARR_LEN 5
int queue[ARR_LEN] = { 0 };
int idxTail = 0;
int idxHead = 0;
int count = 0;

// Enqueue
int Put(int _data);
// Dequeue
int Get(void);
int Print(void);

This time, we use global variables for our data.

Which means I don’t need that much parameters for Put and Get.

Put, a.k.a. Enqueue

int Put(int _data) {
    if (count >= ARR_LEN) {
        printf("Overflow!\n");
        return -1;
    }
    queue[idxTail] = _data;
    idxTail = (idxTail + 1) % ARR_LEN;
    ++count;

    return 0;
}

I had extra count variable to keep track of how many items are queued… in the queue. count is used a lot handling actual Queue, so I think this extra 4B is worth to spend rather than calculating that.

Print

Does C# has this? string.Join(' ', myQueue)?

int Print(void) {
    int i = idxHead;
    for (int c = count; c > 0; --c) {
        printf("%d - ", queue[i]);
        i = (i + 1) % ARR_LEN;
    }
    printf("(%d)\n", count);

    return 0;
}

I decided to not throw an error when the count is 0.

If the count is zero, just display that it is zero.

The original method I used for this was much complicated one with 2 ifs, 3 fors and one subfunction, but after adding count, this method got much simplified as well.

Get, a.k.a. Dequeue

int Get(void) {
    if (count <= 0) {
        printf("Empty!\n");
        return -1;
    }
    int r = queue[idxHead++];
    idxHead = (idxHead + 1) % ARR_LEN;
    --count;

    return r;
}

And the getter now mirrors the setter, unlike linear queue. Thus, O(1) as how Queue should be.