Converting linked list into queue (moving the nodes)

Question

I need some help with the logic whereby I need to create a queue from linked list. So I was given all these code from the question:

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode; // You should not change the definition of ListNode

typedef struct _linkedlist
{
    int size;
    ListNode *head;
} LinkedList;   // You should not change the definition of LinkedList

typedef struct _queue
{
    LinkedList ll;
} Queue;

And by using enqueue, dequeue and isEmptyQueue, I am supposed to create a queue from linked list.

So the logic that I have gotten is:

 Loop thru list size
      enqueue linked list head node
      removeNode to update linkedlist head node

Is that logic correct? I need a head start and thanks in advance.

So I have came out with this code to create a queue from linked list:

However, it crashes my program with no error message. I tried with dummy value enqueue(q,1) and it still crashes. Any ideas?

Answer 1

Truly speaking I have understood nothing.

You need not to convert a linked list to the queue. All you need is to initialize data member ll of the queue with the list.

Here is a demonstrative program

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

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode; // You should not change the definition of ListNode

typedef struct _linkedlist
{
    int size;
    ListNode *head;
} LinkedList;   // You should not change the definition of LinkedList


int insert( LinkedList *ll, int index, int value )
{
    if ( index < 0 || index > ll->size ) return -1;

    ListNode *tmp = malloc( sizeof( ListNode ) );

    tmp->item = value;

    if ( ll->head == NULL )
    {
        tmp->next = ll->head;
        ll->head = tmp;
    }
    else
    {        
        ListNode *current = ll->head; 

        while ( --index ) current = current->next;
        tmp->next = current->next;
        current->next = tmp;
    }

    ++ll->size;

    return 0;
}

void list_output( const LinkedList *ll )
{
    for ( ListNode *current = ll->head; current != NULL; current = current->next )
    {
        printf( "%d ", current->item );
    }

    printf( "\n" );
}

typedef struct _queue
{
    LinkedList ll;
} Queue;

void queue_output( const Queue *q )
{
    list_output( &q->ll );
}    

int main( void )
{
    LinkedList lst = { 0, 0 };
    const int N = 10;

    for ( int i = 0; i < N; i++ ) insert( &lst, i, i );

    list_output( &lst );

    Queue q = { lst };

    lst = ( LinkedList )  { 0, 0 };

    queue_output( &q );

     // call here the method that free allocated memory of the queue

    return 0;
}

Its output is

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9     

That is the queue now is the owner of the allocated nodes. The list in turn is empty.

It means that you indeed converted a list into a queue.

If you mean to copy elements of a list into the queue (it is a different operation compared with the converting operation) then the logic is the following

Traverse the list the same way as you would traverse it to output its element and call method enqueue of the queue for each data value of the node of the list

for ( ; head != NULL; head = head->next )
{
    enqueue( que, head->x );
}

The list itself will be unchanged.

If you need to delete nodes of the list after the copy operation when you can call the method of the list that performs this operation.

Take into account that there is no need to dynamically allocate a list or a queue. For example a declaration of the list could look like

typedef struct _linkedlist
{
    int size;
    ListNode *head;
} LinkedList;   // You should not change the definition of LinkedList

LinkedList lst = { 0, 0 };

It is the nodes of the list that are allocated dynamically.

The same is valid for the Queue.

You can declare a queue the following way

typedef struct _queue
{
    LinkedList ll;
} Queue;

Queue q = { { 0, 0 } };

If you have a list then to convert it to the queue it is enough to write

q.ll = lst;
lst = ( LinkedList ) { 0, 0 };

Also this method

void enqueue(Queue *que, int x)
{
    int counter = 0;
    insert(&(que->l), counter++, x);
}

does not make sense. And moreover the Queue does not have data member l. It has data member ll

You need to append nodes to the queue. So you have to use the value of data member size of the queue as an index where the new element must be inserted.

So the method should look like

void enqueue( Queue *que, int x )
{
    insert( &que->ll, que->ll.size, x) ;
}

Answer 2

void createQFrmLl(LinkedList *ll, Queue * q)
{
    while (ll->size) 
    {
        enqueue(q, ll->head->item); <-- CHANGE done here (passing 'q' instead of &q)
        removeNode(ll, 0);
    }
}

enqueue() expects 'Queue *' but you are passing 'Queue **', hence, inside enqueue() dereferencing q->ll is crashing since q is wrong memory address.

Answer 3

I think your logic is correct, but i would add a little more detail to make it easier to code

Loop through the link list, selecting nodes one by one (until NULL)
    select a node;
    enqueue the value to the queue;
    Free the memory of that enqueued node;
    adjust the pointers to point to the next node in the linked list;

Edit

Lets write the algorithm in a little detail

while(head != NULL)
//Loop to traverse the linked list, just as you would while displaying each node

    enqueue( que, head->item);
    //This function will work just like a normal enqueue() function
    //It should take the item, and insert it in the queue and nothing else
    //I would recommend use an array for the queue

    temp = head;          //save the current node address to free later
    head = head -> next;  //go to next node in the linked list
    free(temp);           //free the previous node