Implement Queue using Linked List in C

Question

This code is used to implement queues and some operations in C by using a linked list. I get unexpected output, especially the line "After removing front item: ", but I don't know why.

Here is my code:

// C program to implement linked list queue
#include <stdio.h>
#include <stdlib.h>

// Define a queue using linked list
typedef struct _Node {
    int data;
    struct _Node *next;
}Node;

typedef struct _Queue {
    Node *pFront, *pBack;
    int size;
}Queue;

// Initialize queue
Queue *init (void) {
    Queue *q = malloc(sizeof(*q));
    if (q) {
    q->size = 0;
    q->pFront = q->pBack = NULL;
    }
    return q;
}

// Check if queue is empty
int isEmpty (Queue q) {
    return (q.pFront == NULL);
}

// Length of train
int Length(Queue *q) {
    return q->size;
}

// Add new item
void enqueue (Queue *q, int val)
{
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = val;
    p->next = NULL;

    // If queue is empty
    if (q->pFront == NULL)
        q->pFront = q->pBack = p;

    // If queue has at least 1 element
    else {
        p->next = q->pBack;
        q->pBack = p;
    }
    q->size++;
}

// Remove item
int dequeue (Queue *q)
{
    if (isEmpty(*q))
        return 0;
    else {
        if (q->size == 1) {
            q->pFront = q->pBack = NULL;
            q->size--;
        }
        else {
            Node *p = q->pBack;
            while (p->next != q->pFront)
                p = p->next;
            q->pFront = p;
            q->pFront->next = NULL;
            q->size--;
        }
    }
    return 1;
}

// Display queue
void display(Queue *q) {
    Node *p = q->pBack;
    while (p != NULL) {
        printf("%d\t", p->data);
        p = p->next;
    }
}

// Free all memory used by the stack
void freeMemory(Queue *q) {
    Node* p = q->pFront;
    Node* next;

    while (p != NULL) {
        next = p->next;
        free(p);
        p = next;
    }

    q->pFront = NULL;
    q->size = 0;
}

int main()
{
    Queue *q;
    q = init();
    if (q)
    {
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    printf("Queue:\n");
    display(q);

    printf("\nAfter removing front item: %d", dequeue(q));
    display(q);

    printf("\nLength of the queue after all modification: %d", Length(q));

    freeMemory(q);
    return 0;
    }
}

Unexpected output: ** Queue: 10 20 30 After removing front item: 110 20 Length of the queue after all modification: 2 **

Answer 1

Your output is misleading you because you do not consistently print a newlines at the end. In particular, here:

    printf("\nAfter removing front item: %d", dequeue(q));
    display(q);

... the return value of dequeue() (always 1 or 0) is printed and then the values of the remaining queue items are printed without any leading space. Your

110 20

could thus be broken down as 1 (return value of dequeue()), 10 (queue item), 20 (queue item).

That would be wrong, because the first item dequeued should be the first one enqueued (10). That's not what your program prints for me, however. When I run your program, I get

After removing front item: 130  20
Length of the queue after all modification: 2

That shows the correct item having been removed. However, my naive expectation would be that that the queue would be printed in the order that the elements will be dequeued, which is the reverse of the order your program emits.

At minimum, add those missing newlines to your program's output. Do also verify the wanted output order for display(), and fix it if needed.