This is an implementation of a dynamically resizing queue in C. A queue is a data structure that has two operations associated with it: a push or enqueue operation that inserts an object into the queue and a pop or dequeue operation that removes an object from the queue. The user can place objects into the queue whatever order he or she wishes; however, when pop is called, the object that has been in the queue the longest is the one that is removed. This is called a first-in—first-out behaviour. The operation front or head returns the object that would be removed if pop was called.

This is an implementation that uses a circular array internally to store the values of the queue. If we get to the end of the array, we start again at location 0. If the array is filled up, the capacity of the array is doubled and the entries are copied from the original array to the new one.

Usage

When declaring an instance of this structure, it must be immediately initialized:

    Queue my_queue;
    init( &my_queue );

Note that we are passing the address of my_queue. That way, the initialization routine can access memory of my_queue. If we just passed in my_queue, C would pass by value: that is, it would make a copy of the data structure and the initialization routine would then initialize the copy but not the original!

In order to manipulate the queue, we will use an object-oriented approach: each function takes the address of the data structure as a first argument. That data structure is then manipulated by the functions:

	int i, j, k;

	push( &my_queue, &i );     // push the address of 'i' onto the queue
	push( &my_queue, &k );     // push the address of 'k' onto the queue

	printf( "The size of the queue is %p\n", size( &my_queue ) );
	printf( "The front of the queue is %p\n", front( &my_queue ) );
	pop( &my_queue );
	printf( "The front of the queue is %p\n", front( &my_queue ) );

	int *ptr = (int *)front( &my_queue );

This will print the addresses of i and k, respectively. Note that popping these addresses off of the queue does not destroy them: the array inside the queue simply stores 32- or 64-bit addresses. If you, however, want to store the current front of the queue, it is necessary to recast it to the appropriate type.

Finally, the memory allocated for the queue must be cleaned up:

    deinit( &my_queue );

If this step is not performed, it will result in a memory leak.

Notes

A note on design: unlike Java where it is possible to create a queue that stores instances of the class Object or C++ where it is possible to use templates to create, for example, a queue of integers (queue<int>) or a queue of doubles (queue<double>), in C, it really is only possible to create a data structure storing pointers to objects. Thus, this queue stores pointers and each function call requires the address of the queue in question to be passed. Unlike C++ and Java where the constructor and destructors are automatically called by the compiler, it is necessary to explictly call init(...) and deinit(...).

Each time an object is inserted, only its address is stored.

The naming convention is based on the naming convention of the C++ Standard Template Library (STL). This is a standard tool used in C++ and the names used in those classes is appropriate.