Queue

Operations associated with a Queue in C

A queue being an Abstract Data Structure provides the following operations for manipulation on the data elements:
1. dequeue(): Removes the element from the frontal side of the queue.
2. enqueue(): It inserts elements to the end of the queue.
3. display(): Displays all the element present in a queue.
4. Front: Pointer element responsible for fetching the first element from the queue.
5. Rear: Pointer element responsible for fetching the last element from the queue.

Working of Queue Data Structure

Queue follows the First-In-First-Out pattern. The first element is the first to be pulled out from the list of elements.
- Front and Rear pointers keep the record of the first and last element in the queue.
- At first, we need to initialize the queue by setting Front = -1 and Rear = -1.
- In order to insert the element (enqueue), we need to check whether the queue is already full i.e. check the condition for Overflow. If the queue is not full, we'll have to increment the value of the Rear index by 1 and place the element at the position of the Rear pointer variable. When we get to insert the first element in the queue, we need to set the value of Front to 0.
- In order to remove the element (dequeue) from the queue, we need to check whether the queue is already empty i.e. check the condition for Underflow. If the queue is not empty, we'll have to remove and return the element at the position of the Front pointer, and then increment the Front index value by 1. When we get to remove the last element from the queue, we will have set the values of Front and Rear index to -1.

Applications of Queue Data Structure

CPU Scheduling: In computer operating systems, queues are used to manage processes and threads. The scheduler maintains a queue of processes waiting for the CPU. When a process completes its execution, it is removed from the queue, and the next process in the queue is executed.
Networking: In computer networking, queues are used to manage network traffic. Packets arriving at a router or a switch are placed in a queue and are processed in a first-in, first-out (FIFO) order. This helps to prevent congestion and ensures that all packets are processed in a fair manner.
Printers: Printers often use queues to manage print jobs. When multiple users are sending print jobs to a printer, the printer places them in a queue and processes them in the order they were received.
Gaming: Queues can be used to implement game mechanics like turn-based games, player-vs-player matchmaking, and other game mechanics that require sequencing of actions.
Disk Scheduling
Breadth-First Search Algorithm (BFS)

Implementation of Linear Queue using array in C

Linear queue video ⇗

                  
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int queue[MAX];
int rear = -1;
int front = -1;
void enqueue()
{
    if (rear == MAX - 1)
    {
        printf("\nQueue is full");
        return;
    }
    if (front == -1 && rear == -1)
        front = rear = 0;
    else
        rear++;
    printf("\nEnter the element : ");
    scanf("%d", &queue[rear]);
}
void dequeue()
{
    if (front == -1 && rear == -1)
    {
        printf("\nQueue is empty");
        return;
    }
    int val = queue[front];
    if (front == rear)
        front = rear = -1;
    else
        front++;
    printf("\n%d is deleted", val);
}
void display()
{
    int i;
    if (front == -1 && rear == -1)
    {
        printf("\nQueue is empty\n");
        return;
    }
    for (i = front; i <= rear; i++)
    {
        printf("\n%d", queue[i]);
    }
}
int main()
{
    int ch;
    while (1)
    {
        printf("\n------- MENU -------");
        printf("\n1.Enqueue Operation\n");
        printf("2.Dequeue Operation\n");
        printf("3.Display the Queue\n");
        printf("4.Exit\n");
        printf("Enter your choice of operations : ");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1:
            enqueue();
            break;
        case 2:
            dequeue();
            break;
        case 3:
            display();
            break;
        case 4:
            exit(0);
        default:
            printf("\nIncorrect choice \n");
        }
    }
    return 0;
}

Circular queue

A circular queue is a data structure that allows efficient insertion and deletion of elements at both ends. It is similar to a regular queue in that it follows the "first-in, first-out" (FIFO) principle, but the main difference is that the last element is connected to the first element, forming a loop.
When circular queue is implemented using array and when the rear pointer reaches the end of the array, it wraps around to the beginning of the array. Similarly, when the front pointer reaches the end of the array, it also wraps around to the beginning of the array. This allows the circular queue to efficiently use the available space in the array
And when circular queue is implemented using linked linked then the last node points to the front.
Cicular queue is used in music player.

Circular queue video lecture ⇗

Problems with linear queue:

When the queue is full and we perform dequeue twice that means there are 2 place are empty (not literally) but then when if we do enqueue then it will show queue is full because rear = MAX - 1.

To Save us from this problem we use circular queue.

                  
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int queue[MAX];
int rear = -1;
int front = -1;
void enqueue()
{
    if ((rear + 1) % MAX == front)
    {
        printf("\nQueue is full");
        return;
    }
    if (front == -1 && rear == -1)
        front = rear = 0;
    else
        rear = (rear + 1) % MAX;
    printf("\nEnter the element : ");
    scanf("%d", &queue[rear]);
}
void dequeue()
{
    if (front == -1 && rear == -1)
    {
        printf("\nQueue is empty");
        return
    }
    int val = queue[front];
    if (front == rear)
        front = rear = -1;
    else
        front = (front + 1) % MAX;
    printf("\n%d is deleted", val);
}
void display()
{
    int i;
    if (front == -1 && rear == -1)
    {
        printf("\nQueue is empty\n");
        return;
    }
    if (front <= rear)
    {
        for (i = front; i <= rear; i++)
            printf("%d\n", queue[i]);
    }
    else
    {
        for (i = front; i < MAX; i++)
            printf("%d\n", queue[i]);
        for (i = 0; i <= rear; i++)
            printf("%d\n", queue[i]);
    }
}
int main()
{
    int ch;
    while (1)
    {
        printf("\n------- MENU FOR CIRCULAR QUEUE -------");
        printf("\n1.Enqueue Operation\n");
        printf("2.Dequeue Operation\n");
        printf("3.Display the Queue\n");
        printf("4.Exit\n");
        printf("Enter your choice of operations : ");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1:
            enqueue();
            break;
        case 2:
            dequeue();
            break;
        case 3:
            display();
            break;
        case 4:
            exit(0);
        default:
            printf("\nIncorrect choice \n");
        }
    }
    return 0;
}

Deque (Double Ended Queue)

It is a type of queue in which insertion and deletion are allowed from both the ends.
Deque supports properties of both stack and queue.
- stack - LIFO
- queue - FIFO

Types of Deque

Input restricted: Here insertion is allowed only from one end but deletion is allowed from both the ends.
Output restricted: Here deletion is allowed only from one end but insertion is allowed from both the ends.

Types of operation performed on deque

Insert at front
Delete from front
Insert at rear
Delete from rear

Application of deque

It is used to perform redo and undo operation.
It can also be used as a palindrome checker.
It is used in multi-processor scheduling.

                  
#include <stdio.h>
#include <stdlib.h>
#define N 5
int deque[N];
int F = -1, R = -1;
void display();
void enqueueFront();
void enqueueRear();
void dequeueFront();
void dequeueRear();
int main()
{
   int ch;
   while (1)
   {
      printf("\n------- MENU FOR DEQUE -------");
      printf("\n1.Enqueue Front Operation\n");
      printf("2.Enqueue Rear Operation\n");
      printf("3.Dequeue  Front Operation\n");
      printf("4.Dequeue  Rear Operation\n");
      printf("5.Display the Queue\n");
      printf("6.Exit\n");
      printf("Enter your choice of operations : ");
      scanf("%d", &ch);
      switch (ch)
      {
      case 1:
         enqueueFront();
         break;
      case 2:
         enqueueRear();
         break;
      case 3:
         dequeueFront();
         break;
      case 4:
         dequeueRear();
         break;
      case 5:
         display();
         break;
      case 6:
         exit(0);
      default:
         printf("\nIncorrect choice \n");
      }
   }
   return 0;
}

void display()
{
   int i;
   if (F == -1 && R == -1)
      printf("\nQueue is empty\n");
   else
   {
      if (F <= R)
      {
         for (i = F; i <= R; i++)
            printf("%d\n", deque[i]);
      }
      else
      {
         for (i = F; i < N; i++)
            printf("%d\n", deque[i]);
         for (i = 0; i <= R; i++)
            printf("%d\n", deque[i]);
      }
   }
}

void enqueueFront()
{
   if ((F == 0 && R == N - 1) || (F == R + 1))
   {
      printf("\nDeque is Full\n");
      return;
   }
   else if (F == -1 && R == -1)
      F = R = 0;
   else if (F == 0)
      F = N - 1;
   else
      F--;
   printf("\nEnter the value you want to enter : ");
   scanf("%d", &deque[F]);
}

void enqueueRear()
{
   if ((F == 0 && R == N - 1) || (F == R + 1))
   {
      printf("\nDeque is Full\n");
      return;
   }
   else if (F == -1 && R == -1)
      F = R = 0;
   else if (R == N - 1)
      R = 0;
   else
      R++;
   printf("\nEnter the value you want to enter : ");
   scanf("%d", &deque[R]);
}

void dequeueFront()
{
   int val;
   if (F == -1 && R == -1)
   {
      printf("\nDeque is Empty\n");
      return;
   }
   else if (F == R)
   {
      val = deque[F];
      F = R = -1;
   }
   else if (F == N - 1)
   {
      val = deque[F];
      F = 0;
   }
   else
   {
      val = deque[F];
      F++;
   }
   printf("\n%d is deleted", val);
}
void dequeueRear()
{
   int val;
   if (F == -1 && R == -1)
   {
      printf("\nDeque is Empty\n");
      return;
   }
   else if (F == R)
   {
      val = deque[R];
      F = R = -1;
   }
   else if (R == 0)
   {
      val = deque[R];
      R = N - 1;
   }
   else
   {
      val = deque[R];
      R--;
   }
   printf("\n%d is deleted", val);
}

Priority queue

A priority queue is a type of queue that arranges elements based on their priority values.
It is a type of data structure in computer science where each element has a priority assigned to it.
The priority of an element determines the order in which it will be processed or removed from the queue.
The element with the highest priority is processed first, followed by the next highest priority element, and so on.
However, if elements with the same priority occur, they are served according to their order in the queue.

Types of Priority Queue:

Ascending Order Priority Queue:
- Here the element with a lower priority value is given a higher priority in the priority list.
- For example, if we have the following elements in a priority queue arranged in ascending order like 4,6,8,9,10. Here, 4 is the smallest number, therefore, it will get the highest priority in a priority queue and so when we dequeue from this type of priority queue, 4 will remove from the queue and dequeue returns 4.
Descending Oder Priority Queue:
- Here the element with higher priority value is given a higher priority in the priority list.

Difference between Priority queue and normal queue?

There is no priority attached to elements in a queue, the rule of first-in-first-out(FIFO) is implemented whereas, in a priority queue, the elements have a priority. The elements with higher priority are served first.

Queue implementation using linked list

                                    
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
   int data;
   struct node *next;
} node;
node *front = NULL;
node *rear = NULL;
void enqueue();
void dequeue();
void display();

int main()
{
   int choice;
   while (1)
   {
         printf("\n\n-!-!-!-!-!- MENU -!-!-!-!-!-");
         printf("\n1. Enqueue");
         printf("\n2. Dequeue");
         printf("\n3. DISPLAY");
         printf("\n4. EXIT");
         printf("\n Enter your choice : ");
         scanf("%d", &choice);
         switch (choice)
         {
         case 1:
            enqueue();
            break;
         case 2:
            dequeue();
            break;
         case 3:
            display();
            break;
         case 4:
            exit(0);
         }
   }
   return 0;
}

void enqueue()
{
   node *temp = (node *)malloc(sizeof(node));
   if (temp == NULL)
   {
         printf("\nOverflow");
         return;
   }
   printf("\nEnter a digit : ");
   scanf("%d", &temp->data);
   temp->next = NULL;
   if (front == NULL)
   {
         front = rear = temp;
   }
   else
   {
         rear->next = temp;
         rear = temp;
   }
}

void dequeue()
{
   if (front == NULL)
   {
         printf("\nUnderflow");
         return;
   }
   node *temp = front;
   if (front == rear)
   {
         front = rear = NULL;
   }
   else
   {
         front = front->next;
   }
   printf("\n%d is deleted", temp->data);
   free(temp);
}

void display()
{
   if (front == NULL)
   {
         printf("\nUnderflow");
         return;
   }
   node *temp = front;
   while (temp != NULL)
   {
         printf("%d ---> ", temp->data);
         temp = temp->next;
   }
}

Circular Queue implementation using linked list

                  
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
      int data;
      struct node *next;
} node;
node *front = NULL;
node *rear = NULL;
void enqueue();
void dequeue();
void display();

int main()
{
      int choice;
      while (1)
      {
         printf("\n\n-!-!-!-!-!- MENU -!-!-!-!-!-");
         printf("\n1. Enqueue");
         printf("\n2. Dequeue");
         printf("\n3. DISPLAY");
         printf("\n4. EXIT");
         printf("\n Enter your choice : ");
         scanf("%d", &choice);
         switch (choice)
         {
         case 1:
            enqueue();
            break;
         case 2:
            dequeue();
            break;
         case 3:
            display();
            break;
         case 4:
            exit(0);
         }
      }
      return 0;
}

void enqueue()
{
      node *temp = (node *)malloc(sizeof(node));
      if (temp == NULL)
      {
         printf("\nOverflow");
         return;
      }
      printf("\nEnter a digit : ");
      scanf("%d", &temp->data);
      temp->next = front;
      if (front == NULL)
      {
         front = rear = temp;
      }
      else
      {
         rear->next = temp;
         rear = temp;
      }
}

void dequeue()
{
      if (front == NULL)
      {
         printf("\nUnderflow");
         return;
      }
      node *temp = front;
      if (front == rear)
      {
         free(front);
         front = rear = NULL;
      }
      else
      {
         front = front->next;
         rear->next = front;
      }
      printf("\n%d is deleted", temp->data);
      free(temp);
}

void display()
{
      if (front == NULL)
      {
         printf("\nUnderflow");
         return;
      }
      node *temp = front;
      while (temp->next != front)
      {
         printf("%d ---> ", temp->data);
         temp = temp->next;
      }
      printf("%d", temp->data);
}