CODEWITHSUNDEEP
clinked-listqueue
student17
student17

Reputation: 791

Implementation of Queues in Linked Lists

I am given these structure declarations in order to implement a queue collection that uses a circular linked list.

typedef struct intnode {
    int value;
    struct intnode *next;
} intnode_t;

typedef struct {
    intnode_t *rear;   // Points to the node at the tail of the 
                       // queue's linked list
    int size;          // The # of nodes in the queue's linked list
} intqueue_t;

intnode_t *intnode_construct(int value, intnode_t *next)
{
    intnode_t *p = malloc(sizeof(intnode_t));
    assert (p != NULL);
    p->value = value;
    p->next = next;
    return p;
}


/* Return a pointer to a new, empty queue.
 * Terminate (via assert) if memory for the queue cannot be allocated.
 */

intqueue_t *intqueue_construct(void)
{
    intqueue_t *queue = malloc(sizeof(intqueue_t));
    assert(queue != NULL);

    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

I'm trying to create a function that will enqueue at a specified value (append it to the rear of the queue), and I need to consider the two cases in which the queue is empty and when the queue has one or more elements. This is the code I have so far:

void intqueue_enqueue(intqueue_t *queue, int value)
{

    intnode_t *p = intnode_construct(value, NULL);

    if(queue->rear->next == NULL) {
        //the queue is empty
        queue->rear->next =p;
    } else {
        //the queue is not empty
        queue->rear=p;
    }
    queue->rear=p;
    queue->size++;
}

This code gives me a runtime error so I'm not sure whats wrong. In the code, I'm assuming queue->rear->next is the front, however I think this is where the problem might be. All help is greatly appreciated. Thanks!

Upvotes: 0

Views: 608

Answers (1)

Tim Sweet
Tim Sweet

Reputation: 645

Your problem occurs on this line:

if(queue->rear->next == NULL) {

The first time you call the function, queue->rear is NULL. Thus when you try to dereference it to get queue->rear->next you get the runtime error.

To fix this code, update intqueue_enqueue to just check if queue->size==0, and if so then you need to initialize it by setting queue->rear=p and p->next=p. Then update the else clause so that it inserts the element between the two existing elements. Hint: you'll need to store queue->rear->next in p.

Edit

To address your comment, here's how to graphically think about a list with three elements:

<element1: next==element2> <element2: next==element3> <element3: next==element1>

And queue->rear points to element3. So, to insert a fourth element, you need to make it so that queue->rear points to element4 and element4->rear needs to point to element1. Remember that the location of element is stored in rear->next.

Upvotes: 1

Related Questions