0

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!

4
  • How are you running the code? Where do you call intqueue_construct? Commented Dec 3, 2017 at 21:20
  • "I'm assuming queue->rear->next is the front" is dubious. If queue == NULL or queue->rear == NULL the code breaks. Assume nothing. Commented Dec 3, 2017 at 21:21
  • 1
    Closely related to previous questions by the same OP: How to implement a queue in a linked list in C? and How to call the front of the queue in a linked list? Commented Dec 3, 2017 at 21:24
  • Since intqueue_t only has a rear and size, I wasn't sure what to use when I call the front, since it is a circular queue and the next value after rear would go back to front. Commented Dec 3, 2017 at 21:28

1 Answer 1

1

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.

Sign up to request clarification or add additional context in comments.

7 Comments

I was told that for this code, in a circular linked list, the tail node (the node at the rear of the queue) points to the head node (the node at the front of the queue). We don't need variable front.
Oh okay, that's somewhat unusual but I guess it's a good exercise. The first part of my answer still answers your question. I'll update the second half to reflect a circular linked list.
The code works for when the queue is empty when it is not empty, I get another runtime error. queue->rear->next=p; } queue->rear=p; queue->size++; }
You'll need to assign p->next to something, that's what I was alluding to in my hint. What do you think it should point to?
would p->next = queue->rear?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.