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>.

• chux: Constant time enqueue() and dequeue() does not require 2 pointers in queue. One is sufficient. Simple have member .tail and let the tail of the queue point to the head. Adding to either end of queue is O(1) Removing from the head is also O(1).
• vnp: @chux Right. Circular queue is better. I was pondering that as well, but decided against for purely didactical reasons.