How to reverse a linked list implementation of a queue

Question

I'm trying to create a recursive function that reverses a linked list implementation of a queue using the enqueue and dequeue functions. I tried doing this:

void reverse(queue *q, node *node)  //this first node would be passed like: reverse(&queue, queue->first);
{
        if(node->next == NULL)
        {
            return;
        }
        reverse(q, node->next);
        int tmp;
        q->head = node;
        tmp = dequeue(q);
        enqueue(q, tmp);
}
    
    void enqueue(queue *q, int data)
{
        node *node = (node*)malloc(sizeof(node));
        node->data = data;
        node->next = NULL;
    
        if (q->tail != NULL)
            q->tail->next = node;

        q->tail = node;

        if (q->head == NULL)
            q->head = node;
    
        q->tail = node;
}
    
    int dequeue(queue *q)
{
        if (!empty(q)){
            node *tmp = q->head;
            int result = tmp->data;
            q->head = tmp->next;
            if (q->head == NULL)
                q->tail = NULL;
            free(tmp);
            return result;
        }
 }

It was actually making sense in my head but it just prints the 2 first numbers.

How can we code a recursive function to reverse a linked queue using enqueue and dequeue functions?

Answer 1

First of all, you have a problem in this line:

    node *node = (node*)malloc(sizeof(node));

As you shadow the type node by the pointer with the same name, the argument given to sizeof is wrong. Use a different variable name in that function.

Also, in C it is considered better not to cast what malloc returns:

    node *curnode = malloc(sizeof(node));
    // ...use curnode below ...

The reverse function

The problem is with this line:

q->head = node;

As you have just reversed the queue that starts at node->next, node->next will now be the tail of the queue, so when you do the above assignment, you limit the queue to two elements, and lose the reference to the other nodes.

As a solution, don't use a second function argument, nor next references. Just dequeue - recurse - and enqueue again:

void reverse(queue *q)
{
    if (empty(q))
        return;
    int tmp = dequeue(q);
    reverse(q);
    enqueue(q, tmp);
}