Have you ever been in a queue at a Store or a Cinema Hall and noticed how people stand in line and wait for their turn?
Well, a queue data structure works in a similar way, but instead of people waiting in line, it’s elements in a computer program waiting to be processed.
Queues are commonly used in programming for tasks that need to be executed in a specific order.
In this tutorial, we’ll explore the Queue Data Structure in detail and implement it in programming languages, including C++, Java, C#, Python, JavaScript, and C.
What is Queue Data Structure?
A Queue is a collection of elements that supports two primary operations: adding an element to the back of the Queue (enqueuing) and removing an element from the front of the Queue (dequeuing).
Elements are processed in the order in which they were added, so the first element to be enqueued is the first to be dequeued.
In a Queue, elements are added to the back and removed from the front, which means the Queue follows a “First-In-First-Out” (FIFO) data structure.
In the image below, you can see a queue of people in a supermarket. People are standing in line, waiting for their turn to be served by the cashier. This is a perfect illustration of how a queue works.
The first person in line will be served first, and as each person is served, they are removed from the front of the line while new customers are added to the back of the line. This creates a first-in, first-out (FIFO) order, ensuring that the customers are served in the order they arrive.
This property makes Queues ideal for tasks that need to be executed in the order they were added.
Basic Operations of Queue
The Queue data structure supports two fundamental operations: Enqueue and Dequeue.
Enqueue(): This operation is used to add an element to the back of the queue. When you add an element to the queue, it becomes the last element and is known as the rear of the queue.
Dequeue(): This operation is used to remove an element from the front of the queue. When you remove an element from the queue, the first element is removed, and the second element becomes the new front of the queue.
Together, these two operations form the basic building blocks of the Queue data structure and help maintain the order of the elements in the queue.
In addition to these fundamental operations, some other operations that can be performed on a Queue data structure are:
Peek(): This operation is used to retrieve the front element of the queue without removing it. The peek operation allows you to inspect the front element of the queue without modifying the queue itself.
IsEmpty(): This operation is used to check if the queue is empty. A queue is empty if it contains no elements. This operation returns a Boolean value (true/false) indicating whether the queue is empty or not.
IsFull(): This operation is used to check if the queue is full. A queue can be considered full if it has reached its maximum capacity and cannot store any more elements. Not all implementations of Queue data structure have a maximum capacity. In such cases, the IsFull operation is not applicable, and the queue is considered to be always not full.
Working of Queue Data Structure
Let’s assume that we have an empty Queue of size 5. This means that we can add up to 5 elements to the Queue. Initially, the values of FRONT and REAR are both set to -1.
Enqueue Operation:
Add the element ‘A’ to the Queue:
Check if the Queue is full. Since it is empty, the Queue is not full.
Set the value of FRONT to 0 (since this is the first element).
Increase the REAR index by 1, making it 0.
Add the new element ‘A’ to the position pointed to by REAR.
Add the element ‘B’ to the Queue:
Check if the Queue is full. Since the REAR pointer is 0 and the size of the Queue is 5, the Queue is not full yet.
Increase the REAR index by 1, making it 1.
Add the new element ‘B’ to the position pointed to by REAR.
Add the element ‘C’ to the Queue:
Check if the Queue is full. Since the REAR pointer is 1 and the size of the Queue is 5, the Queue is not full yet.
Increase the REAR index by 1, making it 2.
Add the new element ‘C’ to the position pointed to by REAR.
Dequeue Operation:
Remove the element at the front of the Queue (i.e., ‘A’):
Check if the Queue is empty. Since FRONT is 0 and REAR is 2, the Queue is not empty.
Return the value pointed to by FRONT, which is ‘A.’
Increase the FRONT index by 1, making it 1.
Remove the element at the front of the Queue (i.e., ‘B’):
Check if the Queue is empty. Since FRONT is 1 and REAR is 2, the Queue is not empty.
Return the value pointed to by FRONT, which is ‘B.’
Increase the FRONT index by 1, making it 2.
Remove the element at the front of the Queue (i.e., ‘C’):
Check if the Queue is empty. Since FRONT is 2 and REAR is 2, the Queue is not empty.
Return the value pointed to by FRONT, which is ‘C.’
At this point, there are no more elements in the Queue, and FRONT is equal to REAR. We can reset the values of FRONT and REAR to -1 to indicate that the Queue is empty.
The above steps demonstrate how we can add and remove elements to and from a Queue using the Enqueue and Dequeue operations, respectively. By following the FIFO (First In, First Out) principle, we can ensure that elements are processed in the order in which they were added to the Queue.
Implementation of Queue Data Structure in C++, Java, C#, Python, JavaScript, and C
//Implementation of Queue Data Structure in C++
#include<iostream>
using namespace std;
// Create a class Queue
class Queue {
int *arr; // array to store queue elements
int front; // front points to front element in the queue (if any)
int rear; // rear points to last element in the queue
int capacity; // maximum capacity of the queue
public:
// Constructor to initialize queue
Queue(int size = 5);
// Destructor to delete queue
~Queue();
// Utility functions
void enqueue(int item); // insert an element
int dequeue(); // remove an element
bool isEmpty(); // check if queue is empty
bool isFull(); // check if queue is full
int getFront(); // get front element
int getRear(); // get rear element
};
// Constructor to initialize queue
Queue::Queue(int size) {
arr = new int[size];
capacity = size;
front = -1;
rear = -1;
}
// Destructor to delete queue
Queue::~Queue() {
delete[] arr;
}
// Utility function to add an element x in the queue
void Queue::enqueue(int item) {
// check if the queue is full
if (isFull()) {
cout << "Queue is Full!" << endl;
return;
}
// check if the queue is empty
if (isEmpty()) {
front = 0;
rear = 0;
}
else {
rear = (rear + 1) % capacity;
}
arr[rear] = item;
cout << "\nElement " << item << " enqueued to the queue." << endl;
}
// Utility function to remove an element from the queue
int Queue::dequeue() {
// check if the queue is empty
if (isEmpty()) {
cout << "Queue is Empty!" << endl;
return -1;
}
int item = arr[front];
// check if the queue has only one element
if (front == rear) {
front = -1;
rear = -1;
}
else {
front = (front + 1) % capacity;
}
cout << "\nElement " << item << " dequeued from the queue." << endl;
return item;
}
// Utility function to check if the queue is empty or not
bool Queue::isEmpty() {
return (front == -1 && rear == -1);
}
// Utility function to check if the queue is full or not
bool Queue::isFull() {
return ((rear + 1) % capacity == front);
}
// Utility function to return front element in the queue
int Queue::getFront() {
// check if the queue is empty
if (isEmpty()) {
cout << "Queue is Empty!" << endl;
return -1;
}
return arr[front];
}
// Utility function to return rear element in the queue
int Queue::getRear() {
// check if the queue is empty
if (isEmpty()) {
cout << "Queue is Empty!" << endl;
return -1;
}
return arr[rear];
}
// main function
int main() {
int size, choice, item;
cout << "Enter the size of the queue: ";
cin >> size;
Queue q(size);
while (true) {
cout << "\n1. Enqueue" << endl;
cout << "2. Dequeue" << endl;
cout << "3. Get Front Element" << endl;
cout << "4. Get Rear Element" << endl;
cout << "5. Quit" << endl;
cout << "\nEnter your choice: ";
cin >> choice;
switch (choice) {
case 1:
if(!q.isFull()) {
cout << "Enter the element to enqueue: ";
cin >> item;
q.enqueue(item);
}
else {
cout << "\nQueue is full. No more elements can be added to the queue!" << endl;
}
break;
case 2:
item = q.dequeue();
if (item != -1) {
cout << "Dequeued Element: " << item << endl;
}
break;
case 3:
item = q.getFront();
if (item != -1) {
cout << "Front Element: " << item << endl;
}
break;
case 4:
item = q.getRear();
if (item != -1) {
cout << "Rear Element: " << item << endl;
}
break;
case 5:
exit(0);
default:
cout << "Invalid choice!" << endl;
}
cout << endl;
}
return 0;
}
//Implementation of Queue Data Structure in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Queue q = new Queue();
int choice, item;
while (true) {
System.out.println("\n1. Enqueue");
System.out.println("2. Dequeue");
System.out.println("3. Get Front Element");
System.out.println("4. Get Rear Element");
System.out.println("5. Quit");
System.out.print("Enter your choice: ");
choice = scanner.nextInt();
switch (choice) {
case 1:
if (!q.isFull()) {
System.out.print("Enter the element to enqueue: ");
item = scanner.nextInt();
q.enqueue(item);
} else {
System.out.println("\nQueue is full. No more elements can be added to the queue!");
}
break;
case 2:
if (!q.isEmpty()) {
item = q.dequeue();
System.out.println("\nDequeued element is " + item);
} else {
System.out.println("\nQueue is empty. No elements can be dequeued from the queue!");
}
break;
case 3:
if (!q.isEmpty()) {
item = q.getFront();
System.out.println("\nFront element is " + item);
} else {
System.out.println("\nQueue is empty. No front element found!");
}
break;
case 4:
if (!q.isEmpty()) {
item = q.getRear();
System.out.println("\nRear element is " + item);
} else {
System.out.println("\nQueue is empty. No rear element found!");
}
break;
case 5:
System.exit(0);
break;
default:
System.out.println("\nInvalid choice! Please enter a valid choice between 1 and 5.");
}
}
}
}
class Queue {
private int front, rear, size;
private int[] arr;
public Queue() {
front = 0;
rear = -1;
size = 0;
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the size of the queue: ");
int capacity = scanner.nextInt();
arr = new int[capacity];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == arr.length;
}
public void enqueue(int item) {
if (rear == arr.length - 1) {
rear = -1;
}
arr[++rear] = item;
size++;
}
public int dequeue() {
int temp = arr[front++];
if (front == arr.length) {
front = 0;
}
size--;
return temp;
}
public int getFront() {
return arr[front];
}
public int getRear() {
return arr[rear];
}
}
//Implementation of Queue Data Structure in C
#include<stdio.h>
#include<stdlib.h>
// Create a structure Queue
struct Queue {
int *arr; // array to store queue elements
int front; // front points to front element in the queue (if any)
int rear; // rear points to last element in the queue
int capacity; // maximum capacity of the queue
};
// Constructor to initialize queue
struct Queue* createQueue(int size) {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->arr = (int*)malloc(sizeof(int) * size);
q->capacity = size;
q->front = -1;
q->rear = -1;
return q;
}
// Utility function to add an element x in the queue
void enqueue(struct Queue* q, int item) {
// check if the queue is full
if (isFull(q)) {
printf("Queue is Full!");
return;
}
// check if the queue is empty
if (isEmpty(q)) {
q->front = 0;
q->rear = 0;
}
else {
q->rear = (q->rear + 1) % q->capacity;
}
q->arr[q->rear] = item;
printf("\nElement %d enqueued to the queue.", item);
}
// Utility function to remove an element from the queue
int dequeue(struct Queue* q) {
// check if the queue is empty
if (isEmpty(q)) {
printf("Queue is Empty!");
return -1;
}
int item = q->arr[q->front];
// check if the queue has only one element
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
}
else {
q->front = (q->front + 1) % q->capacity;
}
printf("\nElement %d dequeued from the queue.", item);
return item;
}
// Utility function to check if the queue is empty or not
int isEmpty(struct Queue* q) {
return (q->front == -1 && q->rear == -1);
}
// Utility function to check if the queue is full or not
int isFull(struct Queue* q) {
return ((q->rear + 1) % q->capacity == q->front);
}
// Utility function to return front element in the queue
int getFront(struct Queue* q) {
// check if the queue is empty
if (isEmpty(q)) {
printf("Queue is Empty!");
return -1;
}
return q->arr[q->front];
}
// Utility function to return rear element in the queue
int getRear(struct Queue* q) {
// check if the queue is empty
if (isEmpty(q)) {
printf("Queue is Empty!");
return -1;
}
return q->arr[q->rear];
}
// main function
int main() {
int size, choice, item;
printf("Enter the size of the queue: ");
scanf("%d", &size);
struct Queue* q = createQueue(size);
while (1) {
printf("\n1. Enqueue");
printf("\n2. Dequeue");
printf("\n3. Get Front Element");
printf("\n4. Get Rear Element");
printf("\n5. Quit");
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
if(!isFull(q)) {
printf("Enter the element to enqueue: ");
scanf("%d", &item);
enqueue(q, item);
}
else {
printf("\nQueue is full. No more elements can be added to the queue!");
}
break;
case 2:
item = dequeue(q);
if (item != -1) {
printf("Dequeued Element: %d", item);
}
break;
case 3:
item = getFront(q);
if (item != -1) {
printf("Front Element: %d", item);
}
break;
case 4:
item = getRear(q);
if (item != -1) {
printf("Rear Element: %d", item);
}
break;
case 5:
exit(0);
default:
printf("Invalid choice!");
}
printf("\n");
}
return 0;
}
# Implementation of Queue Data Structure in Python
# Create a class Queue
class Queue:
def __init__(self, size = 5):
self.arr = [None] * size
self.front = -1
self.rear = -1
self.capacity = size
# Utility function to add an element x in the queue
def enqueue(self, item):
# check if the queue is full
if self.isFull():
print("Queue is Full!")
return
# check if the queue is empty
if self.isEmpty():
self.front = 0
self.rear = 0
else:
self.rear = (self.rear + 1) % self.capacity
self.arr[self.rear] = item
print("\nElement " + str(item) + " enqueued to the queue.")
# Utility function to remove an element from the queue
def dequeue(self):
# check if the queue is empty
if self.isEmpty():
print("Queue is Empty!")
return -1
item = self.arr[self.front]
# check if the queue has only one element
if self.front == self.rear:
self.front = -1
self.rear = -1
else:
self.front = (self.front + 1) % self.capacity
print("\nElement " + str(item) + " dequeued from the queue.")
return item
# Utility function to check if the queue is empty or not
def isEmpty(self):
return (self.front == -1 and self.rear == -1)
# Utility function to check if the queue is full or not
def isFull(self):
return ((self.rear + 1) % self.capacity == self.front)
# Utility function to return front element in the queue
def getFront(self):
# check if the queue is empty
if self.isEmpty():
print("Queue is Empty!")
return -1
return self.arr[self.front]
# Utility function to return rear element in the queue
def getRear(self):
# check if the queue is empty
if self.isEmpty():
print("Queue is Empty!")
return -1
return self.arr[self.rear]
# main function
if __name__ == '__main__':
size = int(input("Enter the size of the queue: "))
q = Queue(size)
while True:
print("\n1. Enqueue")
print("2. Dequeue")
print("3. Get Front Element")
print("4. Get Rear Element")
print("5. Quit")
choice = int(input("\nEnter your choice: "))
if choice == 1:
if not q.isFull():
item = int(input("Enter the element to enqueue: "))
q.enqueue(item)
else:
print("\nQueue is full. No more elements can be added to the queue!")
elif choice == 2:
item = q.dequeue()
if item != -1:
print("Dequeued Element: " + str(item))
elif choice == 3:
item = q.getFront()
if item != -1:
print("Front Element: " + str(item))
elif choice == 4:
item = q.getRear()
if item != -1:
print("Rear Element: " + str(item))
elif choice == 5:
exit(0)
else:
print("Invalid choice!")
//Implementation of Queue Data Structure in C#
using System;
namespace QueueProgram
{
class Queue
{
int[] arr; // array to store queue elements
int front; // front points to front element in the queue (if any)
int rear; // rear points to last element in the queue
int capacity; // maximum capacity of the queue
// Constructor to initialize queue
public Queue(int size = 5)
{
arr = new int[size];
capacity = size;
front = -1;
rear = -1;
}
// Destructor to delete queue
~Queue()
{
arr = null;
}
// Utility functions
public void enqueue(int item) // insert an element
{
// check if the queue is full
if (isFull())
{
Console.WriteLine("Queue is Full!");
return;
}
// check if the queue is empty
if (isEmpty())
{
front = 0;
rear = 0;
}
else
{
rear = (rear + 1) % capacity;
}
arr[rear] = item;
Console.WriteLine("\nElement " + item + " enqueued to the queue.");
}
public int dequeue() // remove an element
{
// check if the queue is empty
if (isEmpty())
{
Console.WriteLine("Queue is Empty!");
return -1;
}
int item = arr[front];
// check if the queue has only one element
if (front == rear)
{
front = -1;
rear = -1;
}
else
{
front = (front + 1) % capacity;
}
Console.WriteLine("\nElement " + item + " dequeued from the queue.");
return item;
}
public bool isEmpty() // check if queue is empty
{
return (front == -1 && rear == -1);
}
public bool isFull() // check if queue is full
{
return ((rear + 1) % capacity == front);
}
public int getFront() // get front element
{
// check if the queue is empty
if (isEmpty())
{
Console.WriteLine("Queue is Empty!");
return -1;
}
return arr[front];
}
public int getRear() // get rear element
{
// check if the queue is empty
if (isEmpty())
{
Console.WriteLine("Queue is Empty!");
return -1;
}
return arr[rear];
}
}
class Program
{
static void Main(string[] args)
{
int size, choice, item;
Console.Write("Enter the size of the queue: ");
size = Convert.ToInt32(Console.ReadLine());
Queue q = new Queue(size);
while (true)
{
Console.WriteLine("\n1. Enqueue");
Console.WriteLine("2. Dequeue");
Console.WriteLine("3. Get Front Element");
Console.WriteLine("4. Get Rear Element");
Console.WriteLine("5. Quit");
Console.Write("\nEnter your choice: ");
choice = Convert.ToInt32(Console.ReadLine());
switch (choice)
{
case 1:
if (!q.isFull())
{
Console.Write("Enter the element to enqueue: ");
item = Convert.ToInt32(Console.ReadLine());
q.enqueue(item);
}
else
{
Console.WriteLine("\nQueue is full. No more elements can be added to the queue!");
}
break;
case 2:
item = q.dequeue();
if (item != -1)
{
Console.WriteLine("Dequeued Element: " + item);
}
break;
case 3:
item = q.getFront();
if (item != -1)
{
Console.WriteLine("Front Element: " + item);
}
break;
case 4:
item = q.getRear();
if (item != -1)
{
Console.WriteLine("Rear Element: " + item);
}
break;
case 5:
Environment.Exit(0);
break;
default:
Console.WriteLine("Invalid choice!");
break;
}
Console.WriteLine();
}
}
}
}
//Implementation of Queue Data Structure in JavaScript
// Create a class Queue
class Queue {
constructor(size = 5) {
this.arr = new Array(size);
this.front = -1;
this.rear = -1;
this.capacity = size;
}
// Utility functions
enqueue(item) {
// check if the queue is full
if (this.isFull()) {
console.log("Queue is Full!");
return;
}
// check if the queue is empty
if (this.isEmpty()) {
this.front = 0;
this.rear = 0;
}
else {
this.rear = (this.rear + 1) % this.capacity;
}
this.arr[this.rear] = item;
console.log(`\nElement ${item} enqueued to the queue.`);
}
// Utility function to remove an element from the queue
dequeue() {
// check if the queue is empty
if (this.isEmpty()) {
console.log("Queue is Empty!");
return -1;
}
let item = this.arr[this.front];
// check if the queue has only one element
if (this.front == this.rear) {
this.front = -1;
this.rear = -1;
}
else {
this.front = (this.front + 1) % this.capacity;
}
console.log(`\nElement ${item} dequeued from the queue.`);
return item;
}
// Utility function to check if the queue is empty or not
isEmpty() {
return (this.front == -1 && this.rear == -1);
}
// Utility function to check if the queue is full or not
isFull() {
return ((this.rear + 1) % this.capacity == this.front);
}
// Utility function to return front element in the queue
getFront() {
// check if the queue is empty
if (this.isEmpty()) {
console.log("Queue is Empty!");
return -1;
}
return this.arr[this.front];
}
// Utility function to return rear element in the queue
getRear() {
// check if the queue is empty
if (this.isEmpty()) {
console.log("Queue is Empty!");
return -1;
}
return this.arr[this.rear];
}
}
// main function
function main() {
let size, choice, item;
console.log("Enter the size of the queue: ");
size = prompt();
let q = new Queue(size);
while (true) {
console.log("\n1. Enqueue");
console.log("2. Dequeue");
console.log("3. Get Front Element");
console.log("4. Get Rear Element");
console.log("5. Quit");
console.log("\nEnter your choice: ");
choice = prompt();
switch (choice) {
case '1':
if(!q.isFull()) {
console.log("Enter the element to enqueue: ");
item = prompt();
q.enqueue(item);
}
else {
console.log("\nQueue is full. No more elements can be added to the queue!");
}
break;
case '2':
item = q.dequeue();
if (item != -1) {
console.log("Dequeued Element: " + item);
}
break;
case '3':
item = q.getFront();
if (item != -1) {
console.log("Front Element: " + item);
}
break;
case '4':
item = q.getRear();
if (item != -1) {
console.log("Rear Element: " + item);
}
break;
case '5':
return;
default:
console.log("Invalid choice!");
}
console.log();
}
}
main();
Limitations of Queue Data Structure
Like any other data structure, the queue has certain limitations that are important to consider:
Fixed-size: Queues are typically implemented with a fixed size, which means that once the queue is full, it cannot accept any more elements until some elements are dequeued.
Overhead: Since the queue uses pointers to keep track of the front and rear of the queue, there is some overhead involved in managing these pointers. This overhead can increase the overall memory usage of the program.
Lack of flexibility: Queues are designed to operate under the “First In, First Out” principle. While this principle is useful in many situations, it can limit the flexibility of the queue in certain cases.
Not suitable for all data types: Queues typically store elements of the same data type. This means they may not be suitable for situations where different types of data need to be stored in the same data structure.
Limited access: Queues only provide access to the first and last elements in the queue. This means that elements in the middle of the queue cannot be accessed directly. To access these elements, all elements in front of them must be dequeued first.
Despite these limitations, the queue data structure is still very useful in many applications, particularly in situations where elements need to be processed in the order in which they were added to the queue.
Complexity Analysis of Queue Data Structure
When implemented using an array with a fixed size, the time complexity of enqueue and dequeue operations in a queue data structure is O(1) for both the best and worst-case scenarios.
However, if the size is not fixed and the array needs to be resized dynamically, the time complexity for enqueue and dequeue operations becomes O(n) in the worst case, where n is the current number of elements in the queue.
Applications Of Queue Data Structure
Queue data structure finds its applications in various domains such as:
Operating Systems: Queues are used for scheduling processes in Operating Systems. The process with higher priority is placed at the front of the queue and executed first.
Computer Networks: In computer networks, queues are used to store and forward the packets from the sender to the receiver.
Customer Service Systems: In customer service systems, queues are used to manage customer requests. The customers are served on a first-come, first-serve basis.
Traffic Management Systems: In traffic management systems, queues are used to manage the flow of vehicles. The vehicles are allowed to pass through the intersection in the order they arrive.
Printers: Queues are used in printers to hold print jobs. The print jobs are printed in the order they are added to the queue.
BFS Traversal: Queues are used in Breadth-First Search (BFS) algorithm to traverse graphs and trees in a level-wise manner.
These are some of the common applications of Queue data structure. There are many more use cases where the Queue data structure simplifies the problem and improves the solution’s efficiency.
I am a Computer Science graduate from the University of Chitral. Alongside my studies, I work in IT and have a strong interest in technology, especially AI, with a deep passion for programming. I’m a determined individual with an entrepreneurial mindset and passionate about sharing my insights as a Tech Blogger. I offer my freelance services in Web Development, Content Writing, and SEO on Fiverr, where I am committed to delivering high-quality work to my clients. My blog (techabu.co) allows me to further explore and discuss the latest tech and business trends, including topics like Programming, WordPress, SEO, AI, and more.
Abu Zar Mishwani
