All About Queue Data Structure

In general , a queue is a line of people or thing waiting to be served in sequential order. The concept of a queue can be explained by observing a line at a reservation counter. The person who is at the front of the line will be served first and he will exit the queue.

What is Queue?

Queue is a linear data structure in which insertions are done at one end (rear) and deletions are done at other end(front).The first element to be inserted is the first one to be deleted . Hence, it is called First in First out (FIFO) or Last in Last out(LILO).

Types of Queue:

There are 4 types of Queue-

1. Simple Queue: It is the normal queue we have discussed here.

1. Priority Queue: Every element has a priority associated with it. An element with higher priority is dequeued before an element with low priority. If two elements have the same priority ,they are served according to their order in the queue.

1. Circular Queue: Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.

1. Double-ended queue/ Deque: Here, insertion and deletion can be occur at both ends.

Basic Operations in a Queue:

1. enqueue(): Add an element to the end of the queue.
2. dequeue():Remove an element from the front of the queue.
3. is_full():Check if the queue is empty.
4. is_empty():Check if the queue is full.
5. peek():Get the value of the front of the queue without removing it.

NOTE:

Queue Overflow: Trying to add an element in a full queue is called Queue overflow.

Queue underflow: Trying to delete an element from a empty queue is called queue underflow.

Working of Queue:

Queue operations work as follows:

• two points FRONT and REAR.
• FRONT track the first element of the queue.
• REAR track the last element of the queue.
• initially, set value of FRONT and REAR to -1

The steps involved in the Enqueue() operation:

1. Check if the queue is full or not.
2. For the first element, set the value of Front to 0.
3. Increase the rear index by 1.
4. Add the new element in the position pointed to by rear.

The steps involved in the Dequeue() operation:

1. Check if the queue is empty or not .
2. Return the value pointed by front.
3. Increase the front index by 1.
4. For the last element , reset the values of front and rear to -1.

Queue Implementation (C programming)Using Array:

#include<stdio.h>
int queue[5];
int size = 5;
int front = -1 ;
int rear = -1 ;
void display()          //display function
{
 int i ; 
 printf(“************Queue**********\n”);
 for(i=front;i<=4;i++)
 {
 printf(“%d\n”,queue[i]);
 }
 
}
void enqueue(int element)            //function for insertion
{
 if(rear==size-1)                   ////is_full condition
 {
 printf(“Queue overflow\n”);          
 }
 else if(rear==-1 && front==-1)
 {
 front=rear=0;
 queue[rear]=element;
 }
 else
 {
 rear++;
 queue[rear]=element;
 
 }
 display();
}
void dqueue()                    //function for deletion
{
 if(front==-1)                     //is_empty condition
 {
 printf(“Queue underflow”);
 }
 else if(front==rear)
 {
 front=rear=-1;
 }
 else
 {
 printf(“The deleted element = %d\n “, queue[front]);
 front++;
 display();
 }
}
int main()
{
 int choice = 0 ;
 int value ;
 int dequed_value=0;
 
 printf(“Enter 1 to Enqueue\n”);
 printf(“Enter 2 to Dqueue\n”);
 printf(“Enter 3 to break\n”);
 
 while(1)
 {
 printf(“Enter your choice: “);
 scanf(“%d”,&choice);
 
 if(choice==1)
 {
 printf(“Enter the value:”);
 scanf(“%d”,&value);
 enqueue(value);
 }
 
 if(choice==2)
 {
 dqueue();
 
 
 }
 if(choice==3)
 {
 break ; 
 }
 }
}

Time complexity for enqueue() operation: O(1)

Time complexity for dequeue() operation: O(1)

Space complexity( for n) enqueue() operation: o(n)

Application of Queue:

1. When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk scheduling.
2. In Operating systems:

a) Spooling in printers.
b) Buffer for devices like keyboard.

3. In Networks:
a) Queues in routers/ switches .
b) Mail Queues.

4. Asynchronous data transfer.

5. Multiprogramming.