A Deep-Dive into Queues in C

Introduction

Much like any line you might encounter at the amusement park or your local grocery store, queues operate in the same way: first in, first out (FIFO).

In C, queues can be used to organize data (just like any other data structure) and usually come in the form of arrays or linked lists.

Today, we'll take a closer look at array-based queues and the operations surrounding it!

Operations on Queues

There are just two main operations that are distinct to queues:

• enqueue: add an element to the end of the queue (like a new person in line)

• dequeue: remove the element at the front of the queue (like the first person in line being attended)
  

Array-Based Queues

If we were to implement queues via arrays, our struct would look something like this:

#define CAPACITY 10;

typedef struct Queue
{
	// array containing a set number of queue elements
	// TYPE array[CAPACITY];
	int array[CAPACITY];
	// index representing the current front of the queue
	int front;
	// number of elements currently in the queue
	int size;
} queue;

At first, of course, we'll declare a queue and set the front and size fields to 0.

queue q1;
// the front of the queue is at index 0 by default
q1.front = 0;
// the size is currently at 0 because there are no elements
q1.size = 0;

Now, let's create functions for our operations.

Enqueueing

void enqueue(queue* q, int val)
{
	// finds the next available index in the array
	// CAPACITY was globally defined as 10
	
	// assume queue is not full

	int rear = (q->front + q->size) % CAPACITY;
	q->array[rear] = val;
	q->size++;
}

Notice how a pointer to the queue was passed rather than the queue variable, in order to pass it by reference instead of by value.

Also, we use the % operator to wrap around the queue in case rear is out of bounds and there is space at the beginning of the array.

Now let's talk about dequeuing...

Dequeuing

int dequeue(queue* q)
{
	// retrieves front element to return
	// changes front field by 1
	// changes size field by -1
	// CAPACITY was globally defined as 10

	// assume queue is non-empty

	int head = q->array[q->front];
	q->front = (q->front + 1) % CAPACITY;
	q->size--;
	
	return head;
}

Oddly enough, we don't actually "delete" the front element. We simply just ignore it and change other fields such that it doesn't seem to exist.

This is why we can use the % operator--when those front indices are "empty," there is space for new elements to wrap around the front.

Final Thoughts

Next, we'll tackle linked-list-based queues, so keep an eye out for that post. Thanks for reading!