Use a Vector to Implement Your Queue
A vector (that is, a resizable dynamic array) with begin and end indices, which increments end on enqueue and begin on dequeue, will have lower memory usage, better locality of reference, and fewer calls to the heap. The only potentially-expensive operation is resizing to add a new element, which might force the data to move to a different block of memory. This is extremely rare, and enqueueing only takes amortized constant time. Furthermore, inserting that many elements into a doubly-linked list would be even slower than shifting a vector.
Consider Making the Code More Generic
The only information you actually need to implement this queue in a reasonably generic way is the size of the elements. (You can code defensively around object alignment.)
Consider Another Naming Scheme
For the rest of this review, I’ll assume that you really do only need a queue of int values, but I’ll call it q_int_t, just in case you later need another type.
It’s also good practice to give the functions from the same module, which operate on the same type, the same prefix, such as q_int_enqueue, q_int_dequeue, and so on.
Handle Errors Out-of-Band
You currently deal with the logic error of dequeing from an empty queue with:
return -111; //assuming it -111 won't be in the queue
How can you assume that? -111 is a perfectly legal value. Even if that assumption were valid for this program (yet without being able to store a short int or int8_t instead of an int), it wouldn’t be reuseable in other programs. And if it were a safe assumption, you should be checking at runtime that the user never enqueue the magic value. And even then, it should be a symbolic constant, such as Q_EMPTY_ERR, and not a magic number in the code.
Dequeuing from an empty queue is a logic error that it makes no sense to handle by checking the return value at runtime. If the caller is unsure whether the queue is empty, it should always test whether the queue is empty before calling dequeue. I’d suggest you make this a fatal error.
If, however, you do want to report an error in-band, you want to make the return type wider (for example, a 64-bit long long int for a queue that stores 32-bit values) and make your magic value outside the range of valid results, such as values between INT_MIN-1LL and LLONG_MIN.
In this case, the only possible errors are dequeueing from an empty queue (which is a logic error that can be made fatal without restricting the valid use of the library) and memory-allocation errors (which I will also treat here as fatal).
Allow const Pointers to Queues
Currently, the entire API requires that the input data be mutable, even functions such as testing whether the queue is empty that do not need to mutate any data. This is a bug attractor and makes immutable references useless.
You should generally also use static single assignments where you can, which includes declaring your function arguments as const or * const. Unless you really do need to modify the function arguments themselves, but that’s rare.
Other Useful Library Functions
It’s no more difficult to write to an arbitrary FILE* as to stdout, and once you have a fprint routine, it’s trivial to implement print.
It’s very useful to be able to swap two queues, and since you could do this by swapping references to data you do not need to move, this operation is cheap.
Most programmers would also want to be able to make a deep copy.
You might want an operation to free the memory of a queue (potentially leaving it in an invalid state) without mutating its data. This would be suitable for a const Queue*, a temporary whose lifetime is about to end, or a queue that is about to be overwritten.
The operations to reserve memory for a number of elements in advance, and to release any extra memory it holds, don’t apply to a list implementation, but would be important for optimizing a vector implementation.
Harmless Pet Peeves
In C, main() is a K&R-style function declaration, which can be called with any number of elements of any type. This happens to be harmless here, but a function that takes no arguments should be declared as int main(void) in ANSI C.
It’s also legal to return 0 from main, but I personally prefer return EXIT_SUCCESS to a magic number.
Putting it All Together
Header file:
#ifndef Q_INT_INCLUDED
#define Q_INT_INCLUDED
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
/* A type representing a queue of int.
* It maintains the following invariants:
*
* 1. Either begin < end or begin == end == 0
* 2. end <= allocated
* 3, data points to a heap-allocated array of [allocated] elements, OR
* allocated == 0 and data == NULL
*/
typedef struct q_int_t {
int* data;
size_t begin;
size_t end;
size_t allocated;
} q_int_t;
/* An expression suitable to initialize an empty queue" */
#define Q_INT_INITIALIZER { NULL, 0, 0, 0 }
/* Tests if the queue is empty. */
extern bool q_int_is_empty( const q_int_t* const q );
/* Number of elements currently in the queue. */
extern size_t q_int_count( const q_int_t* const q );
/* Enqueues an element. */
extern void q_int_enqueue( q_int_t* const q, const int x );
/* Dequeues an element from a NON-EMPTY queue. */
extern int q_int_dequeue(q_int_t* const q);
/* Erases a queue and frees its memory. */
extern void q_int_clear(q_int_t* const q);
/* Reverses a queue. */
extern void q_int_reverse(q_int_t* const q);
/* Serializes a queue to the given FILE*.
*/
extern void q_int_fprint( FILE* const out, const q_int_t* const q );
/* Serializes a queue to standard output. */
extern void q_int_print( const q_int_t* const q );
#endif // Q_INT_INCLUDED
C source file:
#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "q_int.h"
/* Tests if the queue is empty. */
extern bool q_int_is_empty( const q_int_t* const q )
{
return q->begin == q->end;
}
/* Number of elements currently in the queue. */
size_t q_int_count( const q_int_t* const q )
{
assert(q->end >= q->begin);
return q->end - q->begin;
}
/* Enqueues an element. */
void q_int_enqueue( q_int_t* const q, const int x )
{
if (q->allocated == 0) {
static const size_t default_allocation = 1024;
q->data = malloc(sizeof(int)*default_allocation);
assert(q->data);
q->allocated = default_allocation;
q->begin = 0;
q->end = 1;
q->data[0] = x;
return;
}
assert(q->data);
if (q->end == q->allocated) { // Need more space.
if (q->begin > 0) {
/* First, see if we have any dequeued space at the front.
* if so, shift the data without reallocating.
*/
memmove( q->data, q->data+q->begin, sizeof(int)*(q->end - q->begin) );
q->end -= q->begin;
q->begin = 0;
// The allocation is unchanged.
} else {
// Must reallocate.
static const size_t max_alloc = SIZE_MAX / sizeof(int);
assert( q->allocated < max_alloc ); // Have we overflowed a size_t?
const size_t delta = q->allocated / 2U;
// New size is 1.5x the old size or the maximum possible allocation, whichever is less.
const size_t new_alloc = (max_alloc - delta > q->allocated) ? q->allocated + delta : max_alloc;
q->data = realloc( q->data, sizeof(int)*new_alloc );
assert(q->data);
q->allocated = new_alloc;
// If we reached this branch, q->begin was and remains 0
// and q->end indexes the first unallocated element.
}
} // end check for space
/* At this point in the program, the vector is large enough to hold one
* more element.
*/
q->data[q->end++] = x;
}
/* Dequeues an element from a NON-EMPTY queue. */
int q_int_dequeue(q_int_t* const q)
{
assert(q->end > q->begin);
const int dequeued = q->data[q->begin++];
// If that emptied the queue, reset begin and end.
if (q->begin == q->end) {
q->begin = q->end = 0U;
}
return dequeued;
}
/* Erases a queue and frees its memory. */
void q_int_clear(q_int_t* const q)
{
static const q_int_t empty_queue = Q_INT_INITIALIZER;
free(q->data);
memcpy( q, &empty_queue, sizeof(empty_queue) );
}
/* Reverses a queue. */
void q_int_reverse(q_int_t* const q)
{
if (q->end == q->begin) {
return;
}
for ( int* left = q->data + q->begin, *right = q->data + q->end - 1;
right > left;
++left, --right ) {
const int temp = *left;
*left = *right;
*right = temp;
}
}
/* Serializes a queue to the given FILE*.
*/
void q_int_fprint( FILE* const out, const q_int_t* const q )
{
size_t current = q->begin;
const size_t sentinel = q->end;
fputs( "[", out );
if (current < sentinel) {
fprintf( out, "%d", q->data[current++] );
}
while (current < sentinel) {
fprintf( out, ", %d", q->data[current++] );
}
fputs( "]", out );
}
/* Serializes a queue to standard output. */
void q_int_print( const q_int_t* const q )
{
q_int_fprint( stdout, q );
}
Test driver (which does not have complete code coverage, so use at your own risk):
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "q_int.h"
int main(void)
{
q_int_t q1 = Q_INT_INITIALIZER;
assert(q_int_is_empty(&q1));
q_int_enqueue(&q1, 6);
assert(!q_int_is_empty(&q1));
q_int_clear(&q1);
assert(q_int_is_empty(&q1));
q_int_enqueue(&q1, 5);
q_int_enqueue(&q1, 4);
assert(q_int_count(&q1) == 2);
q_int_enqueue(&q1, 3);
assert(q_int_count(&q1) == 3);
q_int_print(&q1);
fputs("\n", stdout);
q_int_reverse(&q1);
q_int_print(&q1);
assert(q_int_dequeue(&q1) == 3);
assert(q_int_dequeue(&q1) == 4);
assert(q_int_dequeue(&q1) == 5);
assert(q_int_is_empty(&q1));
const clock_t start_time = clock();
static const int COUNT = 10000;
for ( int i = 0; i < COUNT; ++i ) {
q_int_enqueue( &q1, i );
assert(q1.allocated > (unsigned)i);
}
for ( int i = 0; i < COUNT; ++i ) {
const int got = q_int_dequeue(&q1);
if (got != i) {
fflush(stdout);
fprintf( stderr, "Expected: %d, found: %d", i, got );
exit(EXIT_FAILURE);
}
}
const clock_t end_time = clock();
printf( "\nElapsed: %f.\n", (double)(end_time - start_time)*(double)(CLOCKS_PER_SEC)/1e6);
return EXIT_SUCCESS;
}
You could tweak some of my design decisions here. For example, you might want to shift the whole array to the left only when this would reclaim a certain amount of memory, not whenever there are one or two free words at the front.
void enqueue(Queue *q, int elm)which hasreturn updated_head;? \$\endgroup\$