Queue Data Structure and Implementation

09 Feb 2023


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 


rear ← rear + 1 

queue[rear] ← data

return true 

end procedure

Dequeue Operation in Queue

procedure dequeue 

 if queue is empty
 return underflow 

 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).

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

Applications of Queue in Data Structure

  • Schedulers in case of multiple processes in the Operating System. A queue is a waiting list for a single shared resource like a printer, disk, or CPU.

  • Used in radix sort, one of the most stable sorting methods.

  • Act as storage buffers in most applications like MP3 media players, CD players, etc., thus facilitating adding or deletion of songs in the playlist.

  • Efficiently handle hardware (real-time systems) interrupts.

  • Competently manage the website traffic.

  • Deal with routers and switches in networks.

  • Serve in optimizing research operations, ensuring the shortest route in the transportation of data elements from one memory location to the other.

  • Facilitate asynchronous data transfer in files, pipes, sockets, etc.

  • High-performing monitoring tools used in batch processing.

  • Excellent data management systems that help automate processes, improve operations, and ensure data -safety.


A Queue is an accumulation of similar data types stored in successive locations. The data elements are scheduled for processing, though not immediately but under analysis. The structure acts as a lifesaver in case of repetition with a dead end. A Queue introduced during the French Revolution has transformed the way of efficiently managing voluminous data today. Various queue operations in Data structure are explained in this session.

Accept cookies & close this