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?

CodePudding user response：

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);
}

CodePudding user response：

For starters your approach is inefficient because the function frees and allocates all nodes anew.

And it has a bug.

Consider a queue that contains three nodes with values 1, 2, 3.

After the second and third recursive calls of the function you have the queue like

3, 2

Now due to the statement

q->head = node;

you have

1, 2

And after these calls

    tmp = dequeue(q);
    enqueue(q, tmp);

you have

2, 1

That is the node with the value 3 is lost.

Moreover the function can invoke undefined behavior called for an empty queue.

And the function should have only one parameter: the pointer to the queue.

The function can be defined simpler without redundant dynamic reallocations of nodes of the queue. For example

void reverse( queue *q )
{
    if (q->head != NULL && q->head->next != NULL)
    {
        node *current = q->head;
        q->head = q->head->next;
        reverse( q );
        q->tail->next = current;
        current->next = NULL;
        q->tail = current;
    }
}

Pay attention to that there is a typo

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

the name of the variable node in this declaration hides the typedef name node of the declared structure.

CodePudding user response：

Using recursion to reverse the list will result in a stack overflow error for an extremely long list.

You can reverse the list without recursion and without allocating any extra memory by just traversing the list and reversing the next member of each node to point to the previous element.

void reverse(queue* queue) {
    node* head = queue->head;
    node* tail = queue->tail;
    node* prev = queue->head;
    node* current = queue->head ? queue->head->next : NULL;
    node* next = current ? current->next : NULL;

    while (current) {
        current->next = prev;
        prev = current;
        current = next;
        next = current ? current->next : NULL;
    }

    // fix up the head and tail of the list
    queue->head = tail;
    queue->tail = head;
    if (queue->tail) {
        queue->tail->next = NULL;
    }
}