Implement a Queue with liked lists

Question

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

typedef struct node{
    int info;
    struct node * next;
}Node;

typedef Node * List;

struct queue{
    int size;
    List tail;
    List head;
};

typedef struct queue *Queue;


/* post: creates an empty queue */
Queue initqueue(){
    Queue q;
    q = malloc(sizeof(struct queue));
    q->tail = q->head = NULL;
    q->size = 0;
    return q;
}

/*post: returns 1 if the queue is empty 0 otherwise  */
int queueempty(Queue q){
    return (q->head) == NULL ? 1 : 0;
}

/*post: inserts an element at the end */
void enqueue(Queue q, int elem){
    List temp = (List)malloc(sizeof(Node));
    temp->info = elem;


    if(q->head == NULL){
        temp->next = q->head ;
        q->head = temp;
    }else{
        temp->next = q->tail;
        q->tail = temp;
    }
    (q->size)++;
}

/*pre: queue not empty */
/*post: returns and removes the first element of the queue */

int dequeue(Queue q){
    int ris;
    List temp;

    temp = q->head;
    q->head = q->head->next;
    ris = temp->info;
    free(temp);
    (q->size)--;

    return ris;
}

/*pre: queue not empty */
/*post: returns the first element of the queue */
int first(Queue q){
    return q->head != NULL ? q->head->info : -1;
}

/*post: returns the number of elements in the queue */
int sizequeue(Queue q){
    return q->size;
}

so this how i try to implement a queue with a liked list. The problem is that whenever i use the dequeue() function my q->head pointer becomes NULL so i lose the head that happens around this line of code:

q->head = q->head->next;

but i am not sure if it is this line that is wrong or if the enqueue() function is wrong because q->head and q->tail should point at the same linked list but i guess hey dont so i've tested it a bit and this is what i get:

if i do a dequeue() on a not empty queue the first() funtion returns -1(q->head == NULL) then after if i do an enqueue(q,10) the first() funtion will return 10 as the head of the queue so the enqueue() puts the element in front of the queue instead of the end and i can't seem to understand what is wrong.

If someone could help me sort out my code that would be very heplful,thank you.

Take a closer look at the code to insert (enqueue) a node into a non-empty list. Try to use some rubber duck debugging there. And try to draw it out on paper. — Some programmer dude
i did a little bit of drawing and i got to the answer guess yesterday was to tiered to get it right, thank you. — Alex

4386427 4386427 · Accepted Answer · 2016-12-23T12:20:25

1) You don't update tail when adding the first element

2) The code for adding other elements is wrong.

Try this instead

void enqueue(Queue q, int elem){
    List temp = (List)malloc(sizeof(Node));
    temp->info = elem;
    temp->next = NULL;   // Always set next to NULL as you add to the tail


    if(q->head == NULL){
        q->head = temp;
        q->tail = temp;        // Also update tail
    }else{
        q->tail->next = temp;  // Make current tail element link the new element
        q->tail = temp;        // Update the tail to the new element
    }
    (q->size)++;
}

Implement a Queue with liked lists

1 Answers