Queues Using Linked List

A queue can be implemented using a linked list. This has various advantages over an array representation because the size of the queue does not have to be decided before the queue is created.

Linked list allows memory to be allocated dynamically depending on the elements added and therefore does not waste or take more memory than required.

Creating the queue

1. Include all the header files which are used in the program.
2. Define a Node structure with two members data and next.
3. Define two Node pointers front and rear and set both to NULL.

Inserting an element (EnQueue)

1. Create a newNode with the given value and set newNode → next = NULL.
2. Check whether the queue is empty (rear == NULL). 
3. If it is empty then, set front = newNode and rear = newNode.
4. If it is not empty then, set rear → next = newNode and rear = newNode.

void enQueue(int value)
{
  struct Node *newNode;
  newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode -> data = value;
  newNode -> next = NULL;
  if (front == NULL)
    front = rear = newNode;
  else {
    rear -> next = newNode;
    rear = newNode;
  }
  printf("\nInsertion is Successful\n");
}

Deleting an element (DeQueue)

1. Create a newNode with the given value and set newNode → next = NULL.
2. Check whether the queue is Empty (rear == NULL). Terminate the function if it is already empty.
3. Define a Node pointer temp and set it to front.
4. Set front = front → next and delete temp. (free(temp))

void deQueue()
{
   if (front == NULL)
      printf("\nUnderflow. Queue is Empty\n");
   else {
      struct Node *temp = front;
      front = front -> next;
      printf("\nDeleted element: %d\n", temp -> data);
      free(temp);
   }
}

Full Code with Menu

#inlcude 

struct Node
{
   int data;
   struct Node *next;
}*front = NULL, *rear = NULL;

void enQueue(int value)
{
  struct Node *newNode;
  newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode -> data = value;
  newNode -> next = NULL;
  if (front == NULL)
    front = rear = newNode;
  else {
    rear -> next = newNode;
    rear = newNode;
  }
  printf("\nInsertion is Successful\n");
}

void deQueue()
{
  if (front == NULL)
    printf("\nUnderflow. Queue is Empty\n");
  else
  {
    struct Node *temp = front;
    front = front -> next;
    printf("\nDeleted element: %d\n", temp -> data);
    free(temp);
  }
}

void display()
{
  if (front == NULL)
    printf("\nQueue is Empty!\n");
  else {
    struct Node *temp = front;
    while (temp -> next != NULL) {
      printf("%d--->", temp -> data);
      temp = temp -> next;
    }
    printf("%d--->NULL\n", temp -> data);
  }
}

void main()
{
  int choice, value;
  while(1) {
    printf("\nQueue using Linked List\n");
    printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
    printf("Enter your choice: ");
    scanf("%d", &choice);
    switch(choice) {
      case 1: printf("Enter the value to be inserted: ");
              scanf("%d", &value);
              enQueue(value);
              break;
      case 2: deQueue();
              break;
      case 3: display();
              break;
      case 4: exit(0);
      default: printf("\nWrong choice. Please try again\n");
    }
  }
}