Implementing a queue using a linked-list

Question

In my intro CS class we're reviewing data structures. I'm currently working on implementing a queue using a linked list (FIFO) in C. I'd appreciate a review of the implementation as well as of my understanding of how a queue should work

// This program is implementation of queue data structure
// via linked list (FIFO)

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

typedef struct node
{
    int number;
    struct node *next;
} node;


node *enqueue(int element, node *temp);
node *dequeue(int n, node *temp);
void display(node *temp);
void destroy_queue(node *temp);

int main()
{
    node *queue = NULL;

    // add some elements to queue
    for (int i = 0; i < 5; i++)
    {
        queue = enqueue((i + 1), queue);
    }


    // display queue
    display(queue);

    // dequeue 2 elements from queue
    printf("Removing two elements from queue...\n");
    queue = dequeue(2, queue);

    //display queue
    display(queue);

    // free memory
    destroy_queue(queue);

}

node *enqueue(int element, node *temp)
{
    node *newElement = malloc(sizeof(node));
    node *head = temp;
    if (newElement == NULL)
    {
        fprintf(stderr, "No memory for the new queue element");
        return temp;
    }

    newElement->number = element;
    newElement->next = NULL;

    if (head == NULL)
    {
        return newElement;
    }
    else
    {
        while ((temp->next) != NULL)
        {
            temp = temp->next;
        }
        temp->next = newElement;
    }
    return head;
}

node *dequeue(int n, node *temp)
{
    node *aux;
    for (int i = 0; i < n; i++)
    {
        if (!temp)
        {
            fprintf(stderr,"No elements to remove!");
            return temp;
        }
        aux = temp->next;
        free(temp);
        temp = aux;
    }
    return temp;
}

void display(node *temp)
{
    while (temp)
    {
        printf("Elements in queue are: %i\n", temp->number);
        temp = temp->next;
    }
}

void destroy_queue(node *temp)
{
    node *aux = temp;
    while (temp)
    {
        aux = temp->next;
        free(temp);
        temp = aux;
    }
}

Answer 1

• Having a separate queue structure

  typedef struct {
      node * head;
      node * tail;
  } queue;
  

  will bring you several benefits:

  • Most important, enqueue would take a constant time (vs linear in queue length you have now).

  • The client would be relieved from responsibility to maintain the head node.

  • enqueue doesn't inform the client that it failed the allocation. fprintf is good for the human, but does nothing for the calling routine. Having the queue structure enables you to return an error code.

• The specialized utility functions, like enqueue and dequeue should not print anything. They must communicate success/error to the caller, and let it act appropriately.

• else in enqueue is redundant.

• I don't see why do you #include <string.h>.