# Queue using doubly linked list

I have implemented my queue based on doubly linked list. The codes is tested and works, however, I am interested in some improvement ideas, thanks

Based on some review remarks on my previous implementation of stack, I made the front a pointer, and I kept the size for reverse for example, and I kept the doubly linked list just for the dequeue so I don't have to run again from head to get to tail.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;

typedef struct Queue {
int size;
Node* tail;
} Queue;

const Queue queue_init = { .size = 0, .head = NULL, .tail = NULL };

int is_empty_q(Queue *q) {
return q->tail == NULL;
}

Node* create_node(int elm) {
Node* node = malloc(sizeof * node);
if (!node) return node;
node->data = elm;
node->prev = NULL;
node->next = NULL;
return node;
}

void enqueue(Queue *q, int elm) {
}
else {
}
q->size++;
}

int dequeue(Queue *q) {
if (!is_empty_q(q)) {
Node* node = q->tail;
int elm = q->tail->data;
q->tail = node->prev;
if (q->tail) {
q->tail->next = NULL;
}
else {
}
free(node);
q->size--;
return elm;
}
return -111; //assuming it -111 won't be in the queue
}

int front(Queue *q) {
int front;
if (q->tail)
front = q->tail->data;
else
front = -111;
return front;
}

void clear_q(Queue *q) {
while (q->tail)
dequeue(q);
printf("Queue Cleared");
}

Queue* reverse_q(Queue *q) { //iterative
Queue *q2 = malloc(sizeof *q2);
if (!q2) return q2;
*q2 = queue_init;
size_t size_e = q->size, size = q->size;
for (size_t i = 0; i < size_e; i++) {
while (size-- - 1)
enqueue(q, dequeue(q));
enqueue(q2, dequeue(q));
size = q->size;
}
return q;
}

void print_q(Queue *q) {
for(Node* trav = q->head; trav != NULL; trav = trav->next)
printf("%d ", trav->data);
printf("\n");
}

int main() {

Queue q1 = queue_init;
enqueue(&q1, 5);
enqueue(&q1, 4);
print_q(&q1);
reverse_q(&q1);
print_q(&q1);
return 0;
}

• What did the compiler say about void enqueue(Queue *q, int elm) which has return updated_head;? Commented Feb 16, 2023 at 17:23

• Naming is kind of surprising. front returns the value at tail. I would expect that front is referred by head; they are almost synonymous.

• void enqueue returns:

  if (!updated_head) return updated_head;


You need to enable warnings.

• reverse_q leaks memory

q2 is allocated

  Queue *q2 = malloc(sizeof *q2);


but is never freed.

• clear_q prints a message. It should not.

• Streamline the code. In enqueue, the assignment q->head = updated_head;is present in both branches ofif. Take it out:

if (!q->head) {
} else {
}

• Special value -111 is there to bite you. It is much better to report success/failure by other means, e.g. bool dequeue(Queue * queue, int * value). Ditto for front.

• reverse_q has an quadratic time complexity

  Node * n = q->head;
while (n->next) {
Node * next = n->next;
n->next = n->prev;
n->prev = next;
n = n->next;
}

q->tail = n;

• I am having a queue there, that means to reverse I only want to use enqueue and dequeue the version you di I already have in the doubly linked list version! Commented Feb 15, 2023 at 13:05
• @user21078706 If reverse is left to the client to implement, then indeed it may only use en/de-queue. However, in the context of the question reverse is a part of an API, and as such it is free to exercise an intimate knowledge of implementation.
– vnp
Commented Feb 16, 2023 at 5:42

Why use a doubly-linked list? We can use a singly-linked list and just keep pointers to the head and tail. All the insertion is at the tail end and all the removal is at the head, so a singly-linked list will save you space and time (both coding time and execution time).

Why do we have a reverse_q function? I've never heard of any application using a queue that's ever had a need to create a reversed copy of it.

The main() function sets a poor example, as it fails to deallocate any of the structures created. A demonstration program ought to run cleanly under Valgrind with no leaks or other issues, so that users clearly understand what's required.

Consider replacing the unchecked demo with some self-checking unit tests that confirm the functions' results are as expected, and result in appropriate exit status.

Compile with more warnings enabled, and pay attention to them:

gcc-12 -std=c17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wmissing-braces -Wconversion  -Wstrict-prototypes -fanalyzer       283307.c    -o 283307
283307.c: In function ‘enqueue’:
283307.c:34:31: warning: ‘return’ with a value, in function returning void [-Wreturn-type]
|                               ^~~~~~~~~~~~
283307.c:32:6: note: declared here
32 | void enqueue(Queue *q, int elm) {
|      ^~~~~~~
283307.c: In function ‘reverse_q’:
283307.c:84:21: warning: conversion to ‘size_t’ {aka ‘long unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
84 |     size_t size_e = q->size, size = q->size;
|                     ^
283307.c:84:37: warning: conversion to ‘size_t’ {aka ‘long unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
84 |     size_t size_e = q->size, size = q->size;
|                                     ^
283307.c:89:16: warning: conversion to ‘size_t’ {aka ‘long unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
89 |         size = q->size;
|                ^
283307.c: At top level:
283307.c:101:5: warning: function declaration isn’t a prototype [-Wstrict-prototypes]
101 | int main() {
|     ^~~~
283307.c: In function ‘reverse_q’:
283307.c:92:12: warning: leak of ‘q2’ [CWE-401] [-Wanalyzer-malloc-leak]
92 |     return q;
|            ^
‘main’: events 1-2
|
|  101 | int main() {
|      |     ^~~~
|      |     |
|      |     (1) entry to ‘main’
|......
|  104 |     enqueue(&q1, 5);
|      |     ~~~~~~~~~~~~~~~
|      |     |
|      |     (2) calling ‘enqueue’ from ‘main’
|
+--> ‘enqueue’: events 3-4
|
|   32 | void enqueue(Queue *q, int elm) {
|      |      ^~~~~~~
|      |      |
|      |      (3) entry to ‘enqueue’
|   33 |     Node* updated_head = create_node(elm);
|      |                          ~~~~~~~~~~~~~~~~
|      |                          |
|      |                          (4) calling ‘create_node’ from ‘enqueue’
|
+--> ‘create_node’: events 5-7
|
|   23 | Node* create_node(int elm) {
|      |       ^~~~~~~~~~~
|      |       |
|      |       (5) entry to ‘create_node’
|   24 |     Node* node = malloc(sizeof * node);
|   25 |     if (!node) return node;
|      |        ~              ~~~~
|      |        |              |
|      |        |              (7) ...to here
|      |        (6) following ‘true’ branch (when ‘node’ is NULL)...
|
<------+
|
‘enqueue’: events 8-10
|
|   33 |     Node* updated_head = create_node(elm);
|      |                          ^~~~~~~~~~~~~~~~
|      |                          |
|      |                          (8) returning to ‘enqueue’ from ‘create_node’
|      |        ~                      ~~~~~~~~~~~~
|      |        |                      |
|      |        |                      (10) ...to here
|      |        (9) following ‘true’ branch (when ‘updated_head’ is NULL)...
|
<------+
|
‘main’: events 11-12
|
|  104 |     enqueue(&q1, 5);
|      |     ^~~~~~~~~~~~~~~
|      |     |
|      |     (11) returning to ‘main’ from ‘enqueue’
|  105 |     enqueue(&q1, 4);
|      |     ~~~~~~~~~~~~~~~
|      |     |
|      |     (12) calling ‘enqueue’ from ‘main’
|
+--> ‘enqueue’: events 13-14
|
|   32 | void enqueue(Queue *q, int elm) {
|      |      ^~~~~~~
|      |      |
|      |      (13) entry to ‘enqueue’
|   33 |     Node* updated_head = create_node(elm);
|      |                          ~~~~~~~~~~~~~~~~
|      |                          |
|      |                          (14) calling ‘create_node’ from ‘enqueue’
|
+--> ‘create_node’: events 15-17
|
|   23 | Node* create_node(int elm) {
|      |       ^~~~~~~~~~~
|      |       |
|      |       (15) entry to ‘create_node’
|   24 |     Node* node = malloc(sizeof * node);
|   25 |     if (!node) return node;
|      |        ~              ~~~~
|      |        |              |
|      |        |              (17) ...to here
|      |        (16) following ‘true’ branch (when ‘node’ is NULL)...
|
<------+
|
‘enqueue’: events 18-20
|
|   33 |     Node* updated_head = create_node(elm);
|      |                          ^~~~~~~~~~~~~~~~
|      |                          |
|      |                          (18) returning to ‘enqueue’ from ‘create_node’
|      |        ~                      ~~~~~~~~~~~~
|      |        |                      |
|      |        |                      (20) ...to here
|      |        (19) following ‘true’ branch (when ‘updated_head’ is NULL)...
|
<------+
|
‘main’: events 21-22
|
|  105 |     enqueue(&q1, 4);
|      |     ^~~~~~~~~~~~~~~
|      |     |
|      |     (21) returning to ‘main’ from ‘enqueue’
|  106 |     print_q(&q1);
|      |     ~~~~~~~~~~~~
|      |     |
|      |     (22) calling ‘print_q’ from ‘main’
|
+--> ‘print_q’: event 23
|
|   95 | void print_q(Queue *q) {
|      |      ^~~~~~~
|      |      |
|      |      (23) entry to ‘print_q’
|
‘print_q’: events 24-25
|
|   96 |     for(Node* trav = q->head; trav != NULL; trav = trav->next)
|      |                                    ^
|      |                                    |
|      |                                    (24) following ‘false’ branch (when ‘trav’ is NULL)...
|   97 |         printf("%d ", trav->data);
|   98 |     printf("\n");
|      |     ~~~~~~~~~~~~
|      |     |
|      |     (25) ...to here
|
<------+
|
‘main’: events 26-27
|
|  106 |     print_q(&q1);
|      |     ^~~~~~~~~~~~
|      |     |
|      |     (26) returning to ‘main’ from ‘print_q’
|  107 |     reverse_q(&q1);
|      |     ~~~~~~~~~~~~~~
|      |     |
|      |     (27) calling ‘reverse_q’ from ‘main’
|
+--> ‘reverse_q’: events 28-35
|
|   80 | Queue* reverse_q(Queue *q) { //iterative
|      |        ^~~~~~~~~
|      |        |
|      |        (28) entry to ‘reverse_q’
|   81 |     Queue *q2 = malloc(sizeof *q2);
|      |                 ~~~~~~~~~~~~~~~~~~
|      |                 |
|      |                 (29) allocated here
|   82 |     if (!q2) return q2;
|      |        ~
|      |        |
|      |        (30) assuming ‘q2’ is non-NULL
|      |        (31) following ‘false’ branch (when ‘q2’ is non-NULL)...
|   83 |     *q2 = queue_init;
|      |     ~~~~~~~~~~~~~~~~
|      |         |
|      |         (32) ...to here
|   84 |     size_t size_e = q->size, size = q->size;
|   85 |     for (size_t i = 0; i < size_e; i++) {
|      |                        ~~~~~~~~~~
|      |                          |
|      |                          (33) following ‘false’ branch (when ‘i >= size_e’)...
|......
|      |               ~~~~~~~~
|      |                 |
|      |                 (34) ...to here
|   92 |     return q;
|      |            ~
|      |            |
|      |            (35) ‘q2’ leaks here; was allocated at (29)
|


I recommend you fix these problems and the interface weirdness before attempting further improvement.

• It seems that this asker has been advised of similar problems in previous reviews - if you solicit a review, we expect that you're going to learn from it. Repeating the same mistakes again and again doesn't encourage others to help you. Commented Feb 16, 2023 at 8:40
• Thank you very much! Commented Feb 16, 2023 at 14:19
• "Compile with more warnings enabled, and pay attention to them" --> Oh the joy if this was required before posting! Saves everybody time. Commented Feb 16, 2023 at 17:15

# Hide it!

There are many things to say about OP's code but enabling all warnings and re-writing for opaqueness are the 2 biggies.

Drop public global variables and hide the members of Queue from the public.

Think FILE * as an example. You use a pointer to FILE, but never really care what is inside FILE or its type. Do the same here. Public only needs to use a pointer to Queue.

Note that even the existence of Node is not needed by the public at all.

In a Queue.h file

// Apply a code guard here
#ifndef Queue_included
#define Queue_included 1

typedef struct Queue Queue;

Queue *Queue_create(void); // new
void Queue_delete(Queue *); // new

int is_empty_q(Queue *q);
void enqueue(Queue *q, int elm);
int dequeue(Queue *q);
int front(Queue *q);
void clear_q(Queue *q);
Queue* reverse_q(Queue *q);
void print_q(Queue *q);

#endif


Within Queue.c

#include "Queue.h"

typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;

typedef struct Queue {
int size;
Node* tail;
} Queue;

// Function definitions, etc.



In main.c

#include "Queue.h"

int main(void) {
Queue *q1 = Queue_create();
enqueue(q1, 5);
enqueue(q1, 4);
print_q(q1);
reverse_q(q1);
print_q(q1);
Queue_create(q1);
return 0;
}


Uniform naming

Rather than

void enqueue(Queue *q, int elm);
int dequeue(Queue *q);
int front(Queue *q);
void clear_q(Queue *q);
...


Consider

void Queue_enq(Queue *q, int elm);
int Queue_deq(Queue *q);
int Queue_front(Queue *q);
void Queue_clear(Queue *q);
...


## 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

#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.

• This is a C language question, not C++. There is no vector. Commented Feb 17, 2023 at 15:05
• @pacmaninbw Vectors are a data structure used in many languages. The term is much older than Alexander Stepanov’s STL (It’s in, for example, the Wizard Book and “Context-Dependent Names,” a manuscript written by Edsgar Dijkstra between 1964 and 1967.) and C++ is not the only language to have them. The same is true of the other names in the STL, such asstring, list and array, Commented Feb 17, 2023 at 17:33
• @pacmaninbw Edited a clarification of the definition of vector I meant, since there are a few of them, in case it wasn’t clear from the code sample at the bottom. Commented Feb 19, 2023 at 0:50