If you have to schedule tasks by incoming order, print some jobs or buffer some messages you might want to use a queue. A queue is part of the STL in C++ as std::queue<T>, where T stands for the type you want the collection to be of.
There isn’t such luxury in C (standard), so we will create our own Queue Class in this article. We will rely on some concepts from my article on how to implement Classes in C, so read it first if you are interested.
If you need an overview of different containers and their advantages and disadvantages you can find them in my article here.
In this Article...
How a Queue works
A queue is a container that works according to the “first in first out” (FIFO) principle. You push the new data in the back of the queue and pop inserted data from the front. In contrast to other containers (e.g. Linked List or Vector) you cannot access any elements with a queue, but only the next or the last element.
For our elements we will have a sort of dynamic array that we resize everytime that an element is added or removed.
One could also reserve some memory in advance and only increase if the queue gets bigger. This is up to the developer implementing the queue class and as always weighs in the space vs. speed discussion.
Queue with 0 Elements
When there are no elements in the queue we only have the size element in the struct that really occupies memory and tells us that the queue is empty.
Queue with 1 Element
With one element we have the special case that back() and front() point to the same element within the queue. Our size is now 1 as you would expect it.
Queue with 3 Elements
In a queue with three Elements we really see the behaviour of this data type. In order to get to the “2” we have to first remove “1” and in order to get to “3” we then have to remove the “2” from the queue first. There is no way around and this is intentionally so as it makes sure that the elements are processed in order.
A Note on Double Ended Queues
A dequeue (double ended queue) is a combination of a queue and a stack (read more about stacks here). It can be accessed from both sides and therefore does not guarantee FIFO or LIFO element access.
We will not cover this special type of queue in this article but together with the information from the stack article you may want to implement a dequeue for yourself.
Goals of the Queue Implementation in C
We will implement a Queue Class in C that is capable of the following features:
- Initializing a Queue (and clean up!)
- Adding Elements to the Queue
- Accessing Elements
- Removing Elements from the Queue
- Swapping complete Queues
We will only implement a Queue for the Integer (int) type. The C language is missing the <template> stuff that C++ provides so you have to make an implementation for every type that you need. (You maybe could use void-Pointers but that is a rabbit whole of it’s own…)
Queue Initialization in C
We will need three files for our implementation:
- queue.h – here we define the Interface for our Queue
- queue.c – the actual Queue implementation
- main.c – here we write a little program to test our Queue
The queue_t struct contains the elements we want to store and a size which tells us how many elements are currently stored within the queue.
The header file serves as Interface for our Queue “Class”. The struct is declared anonymusly because the members will be private.
#pragma once
typedef struct queue_t queue_t;
queue_t* queue_new();
void queue_ctr(queue_t* obj);
void queue_dtr(queue_t* obj);The struct is exactly as described above. The new(), ctr() and dtr() functions imitate the behaviour of a class which I described more deeply in the article about classes in C. In the destructor we make sure to separatly free the elements if they are allocated to any heap memory.
#include "queue.h"
#include <stdlib.h>
typedef struct queue_t {
int* elements;
int size;
} queue_t;
queue_t* queue_new()
{
return (queue_t*) malloc(sizeof(queue_t));
}
void queue_ctr(queue_t* obj)
{
obj->elements = calloc(0, sizeof(int));
obj->size = 0;
}
void queue_dtr(queue_t* obj)
{
if(obj==NULL) {
return;
}
free(obj->elements);
free(obj);
obj = NULL;
}This initial test program doesn’t do that much besides making sure that we can allocate, initialize and destroy our queue:
#include "queue.h"
int main(int argc, char** argv)
{
queue_t* my_queue = queue_new();
queue_ctr(my_queue);
queue_dtr(my_queue);
return 0;
}Adding an Element to a Queue in C
There is only one way to add an element to the queue via its push(…) function. However, in C++ there also is a function called emplace(…) which also adds an element to the end of the list but also creates the object for it in place. Since we don’t have Objects in the C++ sense we don’t really need another function.
We will implement it nevertheless but in its implementation just call the push(…) function. Our Header file now has two more functions. Remember that we want to store Integers in our queue:
...
void queue_push(queue_t* obj, int element);
void queue_emplace(queue_t* obj, int element);
...Exactly as I promised, emplace(…) just forwards the parameters to the push(…) function.
The push(…) function itself increments the size of the queue, reallocates memory for the new element and puts the element at the back of the queue.
...
void queue_push(queue_t* obj, int element)
{
obj->size++;
obj->elements = (int*) realloc(obj->elements, obj->size);
obj->elements[(obj->size-1)] = element;
}
void queue_emplace(queue_t* obj, int element)
{
push(obj, element);
}
...We create a small test program to use our functions:
...
int main(int argc, char** argv)
{
queue_t* my_queue = queue_new();
queue_ctr(my_queue);
queue_push(my_queue, 1);
queue_emplace(my_queue, 2);
queue_dtr(my_queue);
return 0;
}
...There is no output for this test program, for now we have to trust that everything works fine. In the next paragraph we will get some information about our queue.
Getting Information about the Queue
The C++ Standard defines two capacity functions for a queue to get some information about its content. The first checks if a queue is empty, the second returns the size of the queue. In order to use bool in C we include the stdbool library.
#pragma once
#include <stdbool.h>
...
bool queue_empty(queue_t* obj);
int queue_size(queue_t* obj);
...The implementation of these functions is as simple as it gets. The queue is empty if its size is zero, and the size function itself returns the current value of our size element.
...
int queue_empty(queue_t* obj)
{
return (obj->size==0);
}
int queue_size(queue_t* obj)
{
return obj->size;
}
...We now can test these functions by modifing our “add” test program a little bit by adding outputs here and there.
...
int main(int argc, char** argv)
{
queue_t* my_queue = queue_new();
queue_ctr(my_queue);
if(queue_empty(my_queue)) {
printf("Queue is empty at startup!\n");
}
printf("Queue Size: %d\n", queue_size(my_queue));
queue_push(my_queue, 1);
queue_emplace(my_queue, 2);
if(!queue_empty(my_queue)) {
printf("Queue List is filled!\n");
}
printf("Queue Size: %d\n", queue_size(my_queue));
queue_dtr(my_queue);
return 0;
}
...The result then looks like this:
Queue is empty at startup!
Queue Size: 0
Queue List is filled!
Queue Size: 2Accessing Queue Elements in C
As already described, there is no way to access any element directly within the queue. This would completely contradict the sense of the data type. Instead you can only “see” the front or back element of the queue.
The front(…) element is the next one which means the oldest element in the queue. The back(…) element is the last element which therefore means the newest element in the queue. Our declarations in the interface are simple:
...
int queue_front(queue_t* obj);
int queue_back(queue_t* obj);
...The implementation also isn’t that hard. After the guard clause we return the first element of the elements for front() respectively the last element of the elements for back().
...
int queue_front(queue_t* obj)
{
if(NULL == obj || 0 == obj->size) {
return 0;
}
return obj->elements[0];
}
int queue_back(queue_t* obj)
{
if(NULL == obj || 0 == obj->size) {
return 0;
}
return obj->elements[obj->size-1];
}
...After getting information about the size of the queue in our last test program we now modify it so that we also get information about the first and last element. The empty() queries and messages are removed to keep the program clear.
...
int main(int argc, char** argv)
{
queue_t* my_queue = queue_new();
queue_ctr(my_queue);
printf("Queue Size: %d\n", queue_size(my_queue));
queue_push(my_queue, 1);
queue_emplace(my_queue, 2);
queue_push(my_queue, 3);
printf("Queue Size: %d\n", queue_size(my_queue));
printf("First Element: %d\n", queue_front(my_queue));
printf("Last Element: %d\n", queue_back(my_queue));
queue_dtr(my_queue);
return 0;
}
...The output shows how the list size increases and that we now have access to the first and last element of the queue.
Queue Size: 0
Queue Size: 3
First Element: 1
Last Element: 3Removing Queue Elements in C
The only way to remove an element from a queue is to pop it from its front. This way the First In First Out (FIFO) principle is preserved. The function pop(..) does exactly this.
...
void queue_pop(queue_t* obj);
...After our obligatory check of the obj values in a guard clause we start with preparing the shift of the queue content. The library function memmove(..) then shifts the elements inside the queue to the left while leaving the last element as it was. Now we have to decrement the size of the queue and reallocate lesser memory to map the new reality.
...
void queue_pop(queue_t* obj)
{
if(NULL == obj || 0 == obj->size) {
return;
}
int* temp = &obj->elements[1];
memmove(obj->elements, temp, obj->size);
obj->size--;
obj->elements = (int*) realloc(obj->elements, obj->size);
}
..We again modify our test program. We add a third value and then check what the front() element of our queue is, namely the first element that we put in the queue. After that we use the pop() function and again check the size and front element of the queue.
...
int main(int argc, char** argv)
{
queue_t* my_queue = queue_new();
queue_ctr(my_queue);
printf("Queue Size: %d\n", queue_size(my_queue));
queue_push(my_queue, 1);
queue_emplace(my_queue, 2);
queue_push(my_queue, 3);
printf("Queue Size: %d\n", queue_size(my_queue));
printf("First Element: %d\n", queue_front(my_queue));
queue_pop(my_queue);
printf("Queue Size: %d\n", queue_size(my_queue));
printf("First Element: %d\n", queue_front(my_queue));
queue_dtr(my_queue);
return 0;
}
...The Terminal Output shows us that the pop(..) function did exactly what we wanted it to do.
Queue Size: 0
Queue Size: 3
First Element: 1
Queue Size: 2
First Element: 2Swapping Queues in C
We have one more feature of the queue to cover and that is swapping. The swap(…) function exchanges the complete contents of one queue with those from another queue.
The swap function is implemented with a bool return value and takes the source and target queue which should be swapped.
#pragma once
#include <stdbool.h> /* Remember that we have to include this for bool */
...
bool queue_swap(queue_t** source, queue_t** target);
...Its a simple swap algorithm, we swap the contents of each queue including the elements and size via the use of a temporary queue. It returns true after a successful swap and false if any queue is NULL.
bool queue_swap(queue_t** source, queue_t** target)
{
if(NULL == source || NULL == target) {
return false;
}
queue_t* temp = *source;
*source = *target;
*target = temp;
return true;
}In the final test program we create to seperate queues and fill them with different values. Then we call the swap(…) function and check via the output of size(), front() and back() if the contents are successfully swapped.
...
int main(int argc, char** argv)
{
queue_t* int_values = queue_new();
queue_ctr(int_values);
queue_t* tni_values = queue_new();
queue_ctr(tni_values);
queue_push(int_values, 1);
queue_push(int_values, 2);
queue_push(tni_values, 5);
queue_push(tni_values, 4);
queue_push(tni_values, 3);
queue_swap(&int_values, &tni_values); /* TODO: Check return value */
printf("Int Values Size: %d\n", queue_size(int_values));
printf("First Int Element: %d\n", queue_front(int_values));
printf("Last Int Element: %d\n", queue_back(int_values));
printf("Tni Values Size : %d\n", queue_size(tni_values));
printf("First Tni Element: %d\n", queue_front(tni_values));
printf("Last Tni Element: %d\n", queue_back(tni_values));
queue_dtr(int_values);
queue_dtr(tni_values);
return 0;
}The output shows that everything works as we would expect it:
Int Values Size: 3
First Int Element: 5
Last Int Element: 3
Tni Values Size : 2
First Tni Element: 1
Last Tni Element: 2Summary & Further Ideas
…and this is all there is to a queue. We implemented all STL functionality in our C class, so feel free to use it in your projects.
You may want to optimize it if you need it, you could for instance try the suggested implementaion with pre-reserved memory in order to optimize for speed. Another thing you can do is implementing a double ended queue.
If you need LIFO (Last In First Out) instead of the FIFO queue, you may want to take a look at the Stack Class in C.
