Queue in Data Structure

Imagine yourself in the same example as we discussed in the last article on stacks. You are standing in a line for buffet dinner and many people are standing ahead of and behind you. People ahead of you in the line get there early. They get the food before you and they can leave before you.

On the other hand, people behind you get served after you and leave after you. This line for buffet dinner is a queue. The first object to enter the queue is the first one to exit and the last object to enter in the queue is the last one to exit.

In this article, we will learn about queues, types of queues, and array and linked list implementation of each type of queue. We will also see the advantages and disadvantages of different types of queues.

Queue in Data Structure

A queue is an abstract data type data structure that allows operations on both ends. Just like in the above example, people exit from the front and enter from behind. Similarly, in a queue, you can add elements at one end and remove elements from the other. This makes the queue a FIFO structure.

FIFO stands for First In First Out. The first object to enter the queue will be the first that can be accessed and removed. Elements after that will follow the same order.

Complexity of Queue

Applications of Queues

Queues are used:

1. As waiting buffered in printers, Disk, and CPU. The printer takes on the first request in the waiting queue and executes it. The new instructions are appended in the last of the waiting queue.

2. In the asynchronous transfer of data in PIPES, Sockets, etc.

3. In operating systems for handling interrupts and scheduling, semaphores.

4. As Buffer in many applications like CD Player etc.

5. In networking as a buffer queue in routers and switches.

6. In Breadth-first search. A queue is maintained for the adjacent nodes of the current node that need to be traversed before going to the next level.

7. To maintain the playlists in the media players.

Basic operations on Queue

1. Enqueue(): insert a new element at the rear end of the queue. 

2. Dequeue(): delete the element at the front end of the queue and return the deleted element.

3. Peek(): returns the front element of the queue

4. Isfull(): check if the queue is full or not

5. Isempty(): check if the queue is empty or not.

6. size(): returns the current size of the queue.

Implementation of Queue in Data Structure

1. Using Array

An array is used for the implementation of a queue. Implementation and its operation are all carried out on an array.

2. Using Linked list

This is the linked list implementation of a queue. Implementation and its operations are all carried out on a linked list.

Types of queue in Data Structure

1. Linear queue 

2. Circular queue

3. Priority queue

4. Deque

Let’s learn each of these types of queues now:

1. Linear queue

In a linear queue, insertion of an element takes place at one end, known as the rear end and deletion takes place on the other end which is the front end. This strictly is a FIFO structure that stands for first in first out. 

A major disadvantage of a linear linked list is that the elements are inserted on a rear end only. So once the rear pointer points to the last element of the queue no element can be added in a queue even if there is a space and it will return to an overflow condition. 

In the above example, we can see that every time addition of data is at the rear end and deletion is at the front end.

Array implementation

Array implementation is very easy for a queue. Variables ‘front’ and ‘rear’ point to the two positions from where deletion and insertion of elements take place respectively. For an empty queue, front point to index -1.

In the above figure, we can see the queue forming a word. The value of rear increases by 1 for every insertion of the new element in the above queue. After inserting ‘r’ in the last position, the queue will look something like below:

After deleting an element the value of the front will increase by 1 every time and the queue will look like something below.

a. Insert a new element in Queue

1. Check if the queue is already full. If yes then return an overflow condition.

2. If insertion is at the first position then set the value of the front and rear as 0 and insert the element at the rear end.

3. Otherwise, keep increasing the value of the rear after inserting each element at the rear end

Algorithm of Inserting Element in Queue

Step 1: If Rear = MaxSize - 1
Display “Overflow”
Go to step 4
Step 2: If Front = -1 and Rear = -1
set Front = Rear = 0
else
set Rear = Rear + 1

Step 3: set queue[Rear] = new

Step 4: Stop

Queue in C

void insert (int queue[], int max, int front, int rear, int item)   
       {
            rear = rear + 1;   
            queue[rear]=item;  
    }  

b. Delete element in Queue

1. If the value of the front is -1 or greater than the rear, return “queue is empty”
2. Increment the value of front by one and return the items stored at the front end each time.

Algorithm to delete element in queue

Step 1: if Front = -1 or Front > Rear
Display “Underflow”
else
set Value = queue[front]
set front = front + 1

Step 2: Stop

Delete element in queue in C Language

int delete (int queue[], int max, int front, int rear)  
{  
    int y;   
     y = queue[front]; 
     front = front + 1;      
     return y;  
    } 

c. peek() in queue

This returns the data at the front of the queue.

Algorithm:

start procedure peek
   return queue[front]
stop procedure

Function in C:

int peek() 
{
   return queue[front];
}

d. isfull() in queue

1. Check if the rear is at the last position of the array.

Algorithm:

Start procedure isfull

   if rear equals to MAXSIZE - 1
      return true
   else
      return false
   endif
   
Stop procedure

Function in C:

bool isfull() 
{
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

e. isEmpty() in queue

1.Check if the front is 0 or the front is greater than the rear.

Algorithm of isEmpty()

Start procedure isempty

   if front is less than MIN  OR front > rear
      return true
   else
      return false
   endif
   
Stop procedure

Function in C:

bool isempty() 
{
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

f. size() in queue

This function returns the current size of the queue.

Algorithm:

Start procedure size
        Return rear - front
Stop procedure

Function in C:

int size(int front, int rear) 
{
    return (rear - front);
}

Disadvantages of array implementation

1. Memory wastage

Memory that is used to store elements of queue, can never be reused, once it’s free because elements can be inserted at the rear position only. So all the space before the front end is useless and a wastage of memory.

2. Array size

One major disadvantage of array implementation is that the user needs to define the array size in advance. Since the queue might be required to change the size during the run time, this may lead to problems like memory wastage or memory shortage.

Linked list implementation of queue

We know the advantages of a linked list over an array. An alternative to implementing a queue other than the array is a linked list. Worst-case time complexity is o(1) for linked list implementation of a queue.

1. Insert a new element in queue

If the queue is empty then the front is null. A new element will be added as the only element of the linked list and will point to null.

If the queue is not empty, increment the rear pointer so that it points to the new node. This new node points to null.

Algorithm:

Step 1: set newnode -> data = value
Step 2: if front = null
set front = rear = newnode
set front -> next = rear -> next = null
else
set rear -> next = newnode
set rear = newnode
set rear -> next = null
Step 3: Stop

Function in C:

void insert(Node newNode)
{
newNode -> data = item;  
            rear -> next = newNode;  
            rear = newNode;  
            rear->next = NULL;  
   }     

2. Delete an element in queue

If the queue is empty then the value of the front is null and returns underflow condition.
Else delete the element from the front of the list and increment the front pointer to the next node.

Algorithm:

Step 1: if front = null
display " underflow "
go to step 5
Step 2: set deletenode = front
Step 3: set front = front -> next
Step 4: free deletenode
Step 5: end

Function in C:

int delete()
{
deletedNode = front;  
        front = front -> next;  
        free(DeletedNode);  
}

Circular queue

In a circular queue, all nodes are present in a circular order. This concept is very similar to the circular linked list. Also known as a ring buffer that connects all ends to another end.

Representation of circular queue:

The major objective behind the concept of the circular queue was to overcome the drawbacks of the linear queue. If space is available in a circular queue, a new element can be added by incrementing the value of the rear.

In the above example, you can see that although the space is available in the linear queue the new element will not be inserted. The rear is equal to the maximum size of the queue and it will return overflow condition.

But in the circular queue, as represented below, the addition of elements is possible and memory is used more efficiently.

Operations on Circular Queue

1. Front(): returns the front element.
2. Rear(): return the rear element.
3. Enqueue(): insert a new element at the rear end.
4. Dequeue(): delete element from the front end.

Applications of Circular Queue

1. Memory management: Circular queue performs better memory management than a linear queue. Memory is efficiently utilized by placing the elements in empty locations.

2. CPU scheduling: Operating systems use a circular queue to insert the processes and execute them.

3. Traffic Light: Computer-controlled traffic light system follows the circular queue.

Array implementation of the circular queue

1. Enqueue()

1. Check if the queue is full.
2. If the queue is empty, set front and rear to -1. Insert the first element and set both front and rear to 0
3. Increment the rear by one every time you insert a new element.

Algorithm:

Step 1: if (rear+1)%max = front
             Display " overflow "
             Goto step 4
Step 2: if front = -1 and rear = -1
             Set front = rear = 0
             Else if rear = max - 1 and front ! = 0
             Set rear = 0
             Else
             Set rear = (rear + 1) % max
Step 3: set circularqueue[rear] = value
Step 4: stop

Function in C:

void enqueue(int new)  
{  
    if(front==-1 && rear==-1)  
    {  
        front=rear=0;  
        count = 1;
        circularqueue[rear]=new;  
    }  
    else if((rear+1)%max==front)   
    {  
        printf("OverFlow");  
    }  
    else  
    {  
        rear=(rear+1)%max;       
        circularqueue[rear]=new; 
       count++;   
    }  
} 

2. Delete element in Circular Queue

1. Check if the queue is empty or not. If empty, return underflow.
2. Value of the front decreases by one, every time an element is deleted.
3. On deleting the only element left, set both front and rear to -1.

Algorithm:

Step 1: if front = -1
             Display " underflow "
             Goto step 4
Step 2: set value = circularqueue[front]
Step 3: if front = rear
             Set front = rear = -1
             Else
             If front = max -1
             Set front = 0
             Else
             Set front = front + 1
Step 4: Stop

Function in C:

int dequeue()  
{  
    if((front==-1) && (rear==-1))  
        printf("Underflow");  
      
 else if(front==rear)  
{    
   front=-1;  
   rear=-1; 
   count=0; 
}   
else    
   front=(front+1)%max;   
return queue[front];
count--;
}

3. size ()

Returns the size of the current circular queue.

int size(int count) 
{
    return count;
}

Linked list implementation of Circluar Queue

Linked list implementation of any data structure is always more efficient than array implementation. Inserting and deleting elements in a circular queue via a linked list has a worst-case time complexity of o(n).

1. Insert element

void enqueue(Node newNode , Int datanew)  
{  
    newNode -> data=datanew;  
    newnode->next=0;  
    if(rear==-1)  
    {  
        front=rear=newNode;  
        rear->next=front;  
    }  
    else  
    {  
        rear->next=newNode;  
        rear=newNode;  
        rear->next=front;  
    }  
}

2. Delete Element

void dequeue()  
{  
    if((front==-1)&&(rear==-1))     {  
        printf("Underflow");  
    }  
    else if(front==rear) 
        front=rear=-1;   
    else  
    {  
        front=front->next;  
        rear->next=front;  
    }  
} 

3. Peek()

This function returns the element at the front position.

int peek()  
{  
    if((front==-1) &&(rear==-1))   
        printf("Empty Queue");   
    else   
        printf(front->data);  
}  

Deque

Deque stands for double-ended queue. It does not follow the FIFO principle and insertion and deletion of elements can take from both ends. It is also said to be the generalized version of the queue. 

Deque can act as both stack and queue by limiting insert or delete of conditions on either end.

Input restricted queue: In input restricted queue we can insert data at only one end deletion is possible on both ends.

Output restricted queue: In output restricted queue we can delete data from only one end but insertion can be done on both ends.

Operations on Deque

1. Insert at front 
2. Delete from end
3. Insert at rear
4. Delete from rear
5. Isfull()
6. Isempty ()

Deque is implemented using two data structures: circular array and circular linked list.

1. Circular array

In a circular array, the last element is connected to the first element of the array. If we want to insert a new element but the rear is already at the last position, and the first position of the circular array is empty, then it will not show any error, since the last and first elements of the circular array are connected.

Applications of dequeue

1. Deque can be used as a stack or queue.

2. It is used as a palindrome checker since a string can be read from both ends.

3. Deque is used in multiprocessor scheduling. Multiprocessor scheduling using deque is done with the help of an A-steal algorithm.

Array implementation of Deque

Enqueue

1. If the array is empty, set both front and rear to -1.

2. Insert the first element and set front and rear to 0.

3. Insert the next element and increase the value of the rear by one every time.

4. If you want to insert a new element at the front, decrease the value of the front by one. If the front is at zero, after deletion the front is set to the last index of the circular array.

Dequeue

1. Delete an element from the front and increase the value of the front by one.

2. Delete an element from the rear and decrease the value of the rear by one.

3. If the rear is pointing to the first element, after deleting, set the rear to the last index of the circular array.

Working of Deque

Let us consider a queue of max size 9:

1: Deque is empty. Front = Rear = -1

2: Insert “D’ at the rear.

3: Insert ‘A’ and ‘T’ at the rear.

4: Insert ‘R’ at the front.

5: Insert ‘I’ at the front and ‘A’ at the rear.

6: Delete at rear and front.

7: Insert ‘A’, ‘F’, ‘L’ at the rear and ‘I’, ‘A’ at front.

Insert at front

void enqueue_front(int new)  
{  
  
    if((front==-1) && (rear==-1))  
    {  
        front=rear=0;  
        deque[front]=new;  
    }  
    else if(front==0)  
    {  
        front=size-1;  
        deque[front]=new;  
    }  
    else  
    {  
        front=front-1;  
        deque[front]=new;  
    }  
} 

Insert at rear

void enqueue_rear(int new)  
{  
      else if((front==-1) && (rear==-1))  
    {  
        rear=0;  
        deque[rear]=new;  
    }  
    else if(rear==size-1)  
    {  
        rear=0;  
        deque[rear]=new;  
    }  
    else  
    {  
        rear++;  
        deque[rear]=new;  
    }  
}

Delete at front

void dequeue_front()  
{  
    if((front==-1) && (rear==-1))  
    {  
        printf("Underflow");  
    }  
    else if(front==rear)  
    {  
        printf( deque[front]);  
        front=-1;  
        rear=-1;      
    }  
     else if(front==(size-1))  
     {  
         printf(deque[front]);  
         front=0;  
     }  
     else  
     {  
          printf(deque[front]);  
          front=front+1;  
     }  
} 

Delete at end

void dequeue_rear()  
{  
    if((front==-1) && (rear==-1))  
    {  
        printf("Underflow");  
    }  
    else if(front==rear)  
    {  
        printf(deque[rear]);  
        front=-1;  
        rear=-1;  
          
    }  
     else if(rear==0)  
     {  
         printf(deque[rear]);  
         rear=size-1;  
     }  
     else  
     {  
          printf(deque[rear]);  
          rear=rear-1;  
     }  
}  

Get front

int getfront()  
{  
    if((front==-1) && (rear==-1))  
    {  
        printf("Underflow");  
        return -1;
    }  
    else  
        return deque[front];  
} 

Get end

int getrear()  
{  
    if((front==-1) && (rear==-1))  
    {  
        printf("Underflow"); 
        return -1; 
    }  
    else  
    {  
       return deque[rear];  
    }   
} 

Priority queue

A priority queue is also an abstract data type similar to a linear queue. The only thing that makes it different from other types of queues is that each element has a priority assigned to it. Element with the highest priority comes first in a priority queue. Priority determines the order in which elements are accessed and removed from the queue.

In the priority queue, elements are either arranged in ascending or descending order.

Characteristics of priority queue

• Every element in the queue has some priority.
• Elements with higher priority are accessed and removed first.
• In case there are two elements with the same priority, the FIFO principle is followed.

Types of priority queue

1. Ascending order priority queue:

Here, a low-value number is given a higher priority than a high-value number. For example: 

2. Descending order priority queue:

Here, a high-value number is given a higher priority than a low-value number. For example:

Implementation of priority queue

There are four ways to implement priority queues:

• Array
• Linked list
• Heap data structure
• Binary search tree

1. Heap Data structure:  A tree-based Data Structure that forms a complete binary tree and satisfies heap property. If A is the parent of B, then A is ordered with respect to B for all A and B in a heap.

There are two types of heaps :

• MAX Heap: The value of the parent node is greater than the value of the child node.

• MIN Heap: The value of the parent node is less than the value of the child node.

Operations on a priority queue

Inserting the element in a priority queue (MAX Heap)

1. When we insert an element in a MAX heap priority queue, it is added to the first empty slot by looking from top to bottom and left to right.
2. If the element is not in the correct position, it is compared with the parent’s node. The position of the new element and parent node is interchanged if they are found to be not in order. This process is called heapify.
3. This process is repeated until the complete correct order is achieved.

Time Complexity

Applications of priority queue

1. Used for finding the shortest path in Dijkstra’s algorithm.
2. Used in Huffman Code and Heap sort.
3. Used by operation system for priority scheduling, interrupt handling, and load balancing
4. Used in prim’s algorithm.
5. Operating systems use a priority queue for maintaining the processes that are to be pulled for execution from their waiting states.

Linear queue implementation in C

#include <stdio.h>
#define MAXSIZE 5

void Enqueue(int);
void Dequeue();
void Display();

int items[MAXSIZE], front = -1, rear = -1;

int main() {

  Enqueue(10);
  Enqueue(29);
  Enqueue(31);
  Enqueue(44);
  Enqueue(57);
  Enqueue(63);

  Display();

  Dequeue();
  Display();

  return 0;
}

void Enqueue(int val) {
  if (rear == MAXSIZE - 1)
    printf("Overflow");
  else {
    if (front == -1)
      front = 0;
    rear++;
    items[rear] = val;
    printf("\nInserted Value -> %d", val);
  }
}

void Dequeue() {
  if (front == -1)
    printf("Underflow");
  else {
    printf("\nDeleted Value : %d", items[front]);
    front++;
    if (front > rear)
      front = rear = -1;
  }
}

void Display() {
  if (rear == -1)
    printf("Underflow");
  else {
    int i;
    printf("\nCurrent elements in Queue :\n");
    for (i = front; i <= rear; i++)
      printf("%d  ", items[i]);
  }
  printf("\n");
}

Linear queue implementation in C++

#include <iostream>
#define MAXSIZE 5

using namespace std;

class Queue {
   private:
  int items[MAXSIZE], front, rear;

   public:
  Queue() {
    front = -1;
    rear = -1;
  }

  bool isFull() {
    if (front == 0 && rear == MAXSIZE - 1) {
      return true;
    }
    return false;
  }

  bool isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  void Enqueue(int val) {
    if (isFull()) {
      cout << "Overflow";
    } else {
      if (front == -1) front = 0;
      rear++;
      items[rear] = val;
      cout << endl
         << "added " << val << endl;
    }
  }

  int Dequeue() {
    int element;
    if (isEmpty()) {
      cout << "Underflow" << endl;
      return (-1);
    } else {
      element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } 
      else {
        front++;
      }
      cout << endl
         << "Deleted -> " << element << endl;
      return (element);
    }
  }

  void Display() {
    
    int i;
    if (isEmpty()) {
      cout << endl
         << "Queue Empty" << endl;
    } else {
      cout << endl
         << "Front -> " << front;
      cout << endl
         << "Items -> ";
      for (i = front; i <= rear; i++)
        cout << items[i] << "  ";
      cout << endl
         << "Rear -> " << rear << endl;
    }
  }
};

int main() {
  Queue q;


  q.Dequeue();

  
  q.Enqueue(1);
  q.Enqueue(2);
  q.Enqueue(3);
  q.Enqueue(4);
  q.Enqueue(5);
  q.Enqueue(6);

  q.Display();
  q.Dequeue();
  q.Display();

  return 0;
}

Implementation of Linear queue in JAVA

public class Queue {
  int MAXSIZE = 5;
  int items[] = new int[MAXSIZE];
  int front, rear;

  Queue() {
    front = -1;
    rear = -1;
  }

  boolean isFull() {
    if (front == 0 && rear == MAXSIZE - 1) 
{
      return true;
    }
    return false;
  }

  boolean isEmpty() 
{
    if (front == -1)
      return true;
    else
      return false;
  }

  void Enqueue(int Val) 
{
    if (isFull()) 
{
      System.out.println("Overflow");
    } 
else 
{
      if (front == -1)
        front = 0;
      rear++;
      items[rear] = Valt;
      System.out.println("Inserted " + Val);
    }
  }

  int Dequeue() {
    int Val;
    if (isEmpty()) {
      System.out.println("Underflow");
      return (-1);
    } 
else 
{
     Val = items[front];
      if (front >= rear)
 {
        front = -1;
        rear = -1;
      } 

      else
 {
        front++;
      }
      System.out.println("Deleted -> " + Val);
      return (Val);
    }
  }

  void display() {
    
    int i;
    if (isEmpty()) {
      System.out.println("Empty Queue");
    } else {
      System.out.println("\nFront -> " + front);
      System.out.println("Items -> ");
      for (i = front; i <= rear; i++)
        System.out.print(items[i] + "  ");

      System.out.println("\nRear -> " + rear);
    }
  }

  public static void main(String[] args) {
    Queue q = new Queue();

    q.Enqueue();

    q.Enqueue(1);
    q.Enqueue(2);
    q.Enqueue(3);
    q.Enqueue(4);
    q.Enqueue(5);

    q.Enqueue(6);

    q.display();
    q.Dequeue();
    q.display();
  }
}

Linear queue implementation in Python

class Queue:

    def __init__(self):
        self.queue = []

   
    def Enqueue(self, item):
        self.queue.append(item)

  
    def Dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    
    def display(self):
        print(self.queue)

    def size(self):
        return len(self.queue)


q = Queue()
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
q.Enqueue(4)
q.Enqueue(5)

q.display()

q.Dequeue()

print("After removing an element")
q.display()

Conclusion

Queues are one of the major data structures used widely due to their multiple forms and their ability to act at both stack and queue. Multiple variations of queues make them suitable for different kinds of tasks.

In this article, we learned about different forms of queues, the different operations of each of them, and the implementation of a linear queue.