Creating a Simple FIFO Queue for C

mgcadmin 12-02-2022

First In, First Out

Queues are on of the most fundamental data structures in use. Queues are an ordered collection. Items are added in such a way that the first item added to the queue is the first Item to be removed. They pop everywhere covering a myriad of scenarios. From job scheduling, to breadth first search, Branch and Bound, and countless other examples, the queue makes possible some of the most important algorithms in computer science.

Many modern programming languages include a Queue data structure in their standard library: C++ has std::queue, std::deque, and std::priority_queue, and Java.util has a myriad of queue structures, both parallelized and single threaded. Languages like python, javascript, and perl have built in functionality for easily converting arrays into a queue or stack via use of functions like shift(), unshift(), push(), and pop().

C however is famously known for having a rather "light" standard library, lacking any data structures except static arrays. Fear not though, because by using a doubly linked list we can implement a queue fast and efficiently that grows and shrinks as needed in less than 60 lines of code.

Basic Operations

Queue's are meant to strictly control access to its elements, limiting read operations to the front of the queue, and write operations to the end of the queue. The only operations necessary for implementing a queue are:

1. Push - add an item to the back of a queue
2. Pop - remove an item from the front of a queue
3. Front - read the first item on the queue
4. isEmpty - check if the queue contains any items
5. (optionally) size - the number of items in the queue

First things first we need to define our node structure for holding the queued items and the queue itself:

Next, some helper functions to deal with memory allocation of nodes and initializing the queue its self, remember to include stdlib.h for access to malloc():

With those in place, push uses the same algorithm for adding a node at the end of a doubly linked list, note that this implementation uses a dummy tail node 'z' for facilitating this, we also increment the size value to keep track of the items in the queue:

Popping is done by resetting the pointers to set head->next to head->next->next, and setting the new head->next->prev pointer to head. Before doing that we assign the original head->next to t so that we can free() the memory it was allocated. We decrement the size value to keep the number of items in the queue correct.

size(), empty(), and front() are all one liners, which don't require much explanation. Empty check is head's next is pointing to z. we could also check if size is 0, but i prefer this method in case *somehow* a node is removed without decrementing the size counter, an unlikely scenario, but one can never be too careful. I use the convention of calling the front of the queue front() instead of peek() as is sometimes done.

 

Conclusion

And there you have it, if you find yourself in need of a simple queue for use in a C program this implementation will serve you well, as it has done for me.

The code explained here is available in its entirety on my github at:

https://github.com/maxgoren/DataStructures/blob/main/clang/queue.h

---