Queue Data Structure and Implementation

Print 5 min read

09 Feb 2023

Beginner

530 Views

Introduction

In 1837, Scottish historian Thomas Carlyle introduced a linear construct to address the people in a line, requesting to fulfill their needs and wants. The people followed specific rules that determined a way to choose from those on the waiting list. As the line of people increased like a tail, the structure was called a Queue (tail or cauda in Latin).

What is Queue?

A queue is a linear data structure from which the elements may be deleted at one end (FRONT) and inserted from another (REAR). It is also called the First In First Out (FIFO) data structure.

In other words, a queue is an unlimited, ordered collection of data elements maintained in sequential order. The capacity to store the number of data elements safely and ensure quick access is the size of the Queue. A Queue is said to be full if all the storage locations contain data elements. An element added to Full Queue results in an Overflow. A queue with no data element is said to be an Empty Queue, and the removal of any data element from an Empty Queue is impossible and causes an Underflow. Queue operations in Data structure can be demonstrated through the various constructs in a programming language. The queue program in Data structure has many advantages.

The insertion of a new data element is always at the REAR and does not affect the FRONT. The removal of all the data elements before the REAR element allows the removal of the REAR.

As the number of elements added to a Queue may be infinite, a Queue is an Abstract Data Type (ADT).

Here is a sample code to create Queue as an ADT

#define MAX 100
struct queue
{
 int front, rear;
 int element[MAX];
};
struct queue q;

There are four types of queues in data structures

A descending priority queue allows the deletion of only the largest element.

Queue Operations in Data Structure

The typical operations that can be done on a queue are:

Create an empty Queue (initialize) – This operation creates or initializes a queue as a data structure with no data element.
Check if a Queue is empty (Isempty(queue)) – This operation returns a Boolean true if the Queue is Empty
Addition of an element to the Queue (enQueue(value)) – This operation adds a value (data element) at the REAR of the Queue.
Displaying the front element (peek()) – This operation displays the FRONT element before any element is deleted from the Queue.
Removal of an element from the Queue (deQueue())- This operation removes the element from the FRONT of the queue.
Displaying an element from the queue (display()) – This operation displays all the elements of the queue
Check if a Queue is full (isfull()) – This operation returns a Boolean true if the Queue is full.

Here is a sample procedure to understand the queue operations in Data structure.

Enqueue Operation in Queue

procedure enqueuer (data) 

 if queue is full

 return overflow 

 endif

rear ← rear + 1 

queue[rear] ← data

return true 

end procedure

Dequeue Operation in Queue

procedure dequeue 

 if queue is empty
 
 return underflow 
 
endif 

 data = queue[front]

 front ← front + 1
 
return true 

end procedure

Queue Data Structure Using Array

A queue represents an array. The FRONT data element is indicated by A[0], the first element of an array, and the REAR points to the last element A[n]. Here is an algorithm to implement Queue as an Array

Create an array of “n” data elements;
Initialize FRONT=REAR=0;
To add an element, REAR = REAR +1;
To delete an element, FRONT= FRONT +1;
STOP

As the array size is essentially declared, it is impossible to implement a Queue where the array size is unknown.

Queue Data Structure Using Linked List

A Queue represents an array of unlimited elements - a linked list. The first node of a linked list is the FRONT, and its last node is the REAR. Here is an algorithm to implement Queue as a Linked List

Create a linked list with nodes comprising data elements and the pointer to the next node where the data is stored.
The first node is the FRONT. The last node is the REAR.
Initially, pointers to FRONT and REAR are NULL.
Adding a new element signifies the addition of a new node and incrementing the value of the REAR by 1 (REAR =REAR +1)
Deleting or removing an existing element from a Queue occurs at the FRONT, and the REAR is decremented by 1; REAR = REAR-1

Queue Time Complexity

As the addition and deletion of data elements in a Queue are both single-step operations, the time complexity is O(1). The space complexity for a Queue with n elements is O(n).