Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Queue?
3.
Implementation of Queue using Array Operations
3.1.
Initialize
3.2.
Enqueue
3.3.
Dequeue
3.4.
Peek
3.5.
isEmpty
3.6.
isFull
4.
How to Implement Queue Using Arrays?
4.1.
Java
5.
Execution of Supportive Queue Operations
6.
Implementation of Enqueue Operation
7.
Implementation of Dequeue Operation
8.
What is Generics?
8.1.
Syntax to create an instance of a generic class
8.2.
Java
8.3.
Implementation Of Queue in Java
8.4.
Java
8.5.
Analysis of Complexity
9.
Drawbacks of Queue Implementation Using Array
10.
Limitations of Array Representation of Queue
11.
Frequently Asked Questions
11.1.
What is the implementation of queue using array?
11.2.
How to implement queue in C++ using array?
11.3.
How can a queue be implemented using an array and a linked list explain?
12.
Conclusion
Last Updated: Mar 27, 2024
Medium

Implementation Of Queue in Java using Array and Generics

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

A queue is a linear data structure that follows the First-In-First-Out principle. The first element added to the queue will be the first one to be removed. For example, a line of people waiting for a service, where the person at the front of the line gets served first. In programming, a queue is commonly used to manage tasks or data in a sequential manner. Elements are added at the rear (enqueue) and removed from the front (dequeue).

array implementation of queue

Questions are frequently asked related to Queues, especially for freshers. Queue follows FIFO(First In First Out) principle for performing operations.

In this article, we will be covering Queue data structure and see an intriguing implementation in Java using Arrays and Generics. 

What is Queue?

A queue is a linear data structure and follows FIFO methodology to perform operations on elements, which states that the data stores first will be accessed. Here we will remove the element that is recently added.

Basic Operations Associated With Queue

  • enqueue() - add an element to the front of the queue.
  • dequeue() - removes the last element of the queue.
  • peek() - returns the front element of the queue.
  • isempty() - checks if the queue is empty.
  • isfull() - checks if the queue is full.
What is Queue?

Time taken by all the operations is O(1). 

A queue can also be implemented using Arrays, Linked-lists, Pointers, and Structures, and for now, we will use arrays and generics.

Must Read Difference between ArrayList and LinkedList

You can watch the video below to get a better understanding of Queue Implementation Using Arrays beforehand.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation of Queue using Array Operations

Here are the basic array operations that can be used to implement a queue:

Initialize

Create an array to store the elements of the queue and initialize the front and rear pointers to -1.

int[] queue = new int[MAX_SIZE];
int front = -1, rear = -1;

Enqueue

Add an element to the rear of the queue.

if (rear == MAX_SIZE - 1) {
   System.out.println("Queue is full");
} else {
   rear++;
   queue[rear] = element;
   if (front == -1) {
       front = 0;
   }
}

Dequeue

Remove an element from the front of the queue.

if (front == -1 || front > rear) {
   System.out.println("Queue is empty");
} else {
   int element = queue[front];
   front++;
   return element;
}

Peek

Get the element at the front of the queue without removing it.

if (front == -1 || front > rear) {
   System.out.println("Queue is empty");
} else {
   return queue[front];
}

isEmpty

Check if the queue is empty.

return front == -1 || front > rear;

isFull

Check if the queue is full.

return rear == MAX_SIZE - 1;

How to Implement Queue Using Arrays?

To implement a queue using arrays in Java, you can follow these steps:

  1. Create an array to store the elements of the queue.
  2. Create variables to keep track of the front and rear of the queue.
  3. Initialize the front variable to 0 and the rear variable to -1.
  4. To add an element to the queue, increment the rear variable and add the element to the position indicated by the rear variable.
  5. To remove an element from the queue, increment the front variable and return the element at the position indicated by the front variable.
  6. Implement methods to check if the queue is empty or full, as well as to get the size of the queue.

Let us understand the implementation of queue using arrays in Java with the help of an example:

  • Java

Java

public class QueueUsingArrays {
private int[] arr;
private int front;
private int rear;
private int size;

// Creating Constructor
public QueueUsingArrays(int capacity) {
arr = new int[capacity];
front = 0;
rear = -1;
size = 0;
}

// Adds the element in the queue
public void enqueue(int item) {
if (isFull()) {
System.out.println("Queue is full");
return;
}
rear++;
arr[rear] = item;
size++;
}

// Removes the element from the queue
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
int item = arr[front];
front++;
size--;
return item;
}

// Returns the front element in the queue
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
return arr[front];
}

// Returns a boolean value if queue is empty
public boolean isEmpty() {
return size == 0;
}

// Returns a boolean value if queue is full
public boolean isFull() {
return rear == arr.length - 1;
}

// Returns size of the queue
public int size() {
return size;
}

public static void main(String[] args)
{
QueueUsingArrays queue = new QueueUsingArrays(5);
queue.enqueue(7);
queue.enqueue(9);
System.out.println("Peek element: "+queue.peek());
System.out.println("Deleted element: " + queue.dequeue());
System.out.println("Deleted element: " + queue.dequeue());
queue.enqueue(11);
System.out.println("Deleted element: " + queue.dequeue());
}
}

Output 

Peek element: 7
Deleted element: 7
Deleted element: 9
Deleted element: 11

 

This implementation uses an array to store the elements of the queue and includes methods to enqueue and dequeue elements, as well as to peek at the front element of the queue. It also includes methods to check if the queue is empty or full, and to get the queue size.

Execution of Supportive Queue Operations

Let us understand the execution of the above supportive queue operations with the help of an example:
 

QueueUsingArrays queue = new QueueUsingArrays(5);
// Return true
System.out.println(queue.isEmpty()); 


// Return false
System.out.println(queue.isFull()); 


// Size is 0 currently
System.out.println(queue.size()); 


// Adding elements
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);


// false
System.out.println(queue.isEmpty()); 


// true
System.out.println(queue.isFull()); 


// 5
System.out.println(queue.size());


// "Queue is full!" message will be printed
queue.enqueue(6); 


// 1
System.out.println(queue.dequeue());


// 2
System.out.println(queue.dequeue()); 


// 3
System.out.println(queue.peek()); 


// 3
System.out.println(queue.size());


In this example, we create a QueueUsingArrays object with a maximum size of 5. We then use the isEmpty(), isFull(), and size() methods to check the initial state of the queue, which is empty.

We then use the enqueue() method to add five elements to the queue. Since the maximum size of the queue is 5, attempting to add a sixth element will result in an error message being printed.

We then use the dequeue() method to remove the first two elements from the queue, and the peek() method to check the element at the front of the queue without removing it. Finally, we use the size() method to check the current size of the queue.

Implementation of Enqueue Operation

Let us understand the implementation of the enqueue operation for a queue with the help of an example using an array in Java:

public void enqueue(int data) {
   if (isFull()) {
       System.out.println("Queue is full!");
       return;
   }
   rear = (rear + 1) % capacity;
   arr[rear] = data;
   size++;
}

 

In this implementation, we first check if the queue is full by using the isFull() method. If the queue is full, we print an error message and return without adding the new element.

Otherwise, we increment the rear index of the array by 1. We then add the new element to the arr array at the updated rear index.

Finally, we increment the queue size after adding the new element. 

Implementation of Dequeue Operation

Let us understand the implementation of the dequeue operation for a queue with the help of an example using an array in Java:

public int dequeue() {
   if (isEmpty()) {
       System.out.println("Queue is empty!");
       return -1;
   }
   int data = arr[front];
   front = (front + 1) % capacity;
   size--;
   return data;
}

 

In this implementation, we first check if the queue is empty by using the isEmpty() method. If the queue is empty, we print an error message and return -1 to indicate that there is no valid data value to return.

Otherwise, we retrieve the element at the front index of the arr array. We then increment the front index of the array by 1 to remove the first element from the queue.

Finally, we decrement the queue size after removing the element and return the data value that was dequeued.

Read about Application of Queue in Data Structure here.

What is Generics?

Generics is a vast topic of Java used in programming to make the code stable by detecting the bugs at compile time. Generics are used to store a specific type of object. Using Generics, it is possible to create classes that work with different data types. 

Syntax to create an instance of a generic class

  • Java

Java

Class <Type> objname = new Class<Type>()
A quick example of a generic class to move your concept more transparent before heading to the implementation of a queue.
class Solution<T, U>
{
T obj1; // An object of type T
U obj2; // An object of type U

// constructor
Solution(T obj1, U obj2)
{
this.obj1 = obj1;
this.obj2 = obj2;
}

// Method to print the objects 
public void print()
{
System.out.println(obj1);
System.out.println(obj2);
}
}

// Main function
class Main
{
public static void main (String[] args)
{
Solution <String, Integer> obj =
new Solution<String, Integer>("Coding Ninjas", 50);

obj.print();
}
}

Output

Coding Ninjas
50

Implementation Of Queue in Java

  • Java

Java

import java.io.*;
import java.util.*;

// Class 1
//  generic queue class(defined by user)
class queue<T> {
// front and rear variables are initially initiated to
// -1 pointing to no element
int front = -1, rear = -1;

// Create an object of ArrayList class of T type
ArrayList<T> list = new ArrayList<>();


// Returns value of the element at the front of the queue
T front()
{

if (front == -1)

return null;

return list.get(front);
}
// Method 2
// Returns value of the element at the rear of the queue
T rear()
{
if (rear == -1)
return null;
return list.get(rear);
}

// Inserts element at the front of the queue
void enqueue(T x)
{
// If queue is empty
if (this.empty()) {
front = 0;
rear = 0;
list.add(x);
}

else {
front++;
if (list.size() > front) {

// Move the front pointer to next
list.set(front, x);
}
else

// Add element to the queue
list.add(x);
}
}

// Deletes elements from the rear from the queue
void dequeue()
{
// if queue is empty
if (this.empty())

System.out.println("Queue is already empty");

// If queue has only one element
else if (front == rear) {

front = rear = -1;
}

// If queue has more than one element
else {
rear++;
}
}

// To check whether the queue is empty
boolean empty()
{

if (front == -1 && rear == -1)
return true;
return false;
}
// Method 6
// Print the queue

// @Override
public String toString()
{
if (this.empty())
return "";

String ans = "";

for (int i = rear; i < front; i++) {
ans += String.valueOf(list.get(i)) + "->";
}

ans += String.valueOf(list.get(front));

return ans;
}
}


// Main class
class Solution {

// Main function 
public static void main(String args[])
{

// Creating object of queue Class (user defined)
queue<Integer> q = new queue<>();

// inserting the elements into the queue
q.enqueue(10);
q.enqueue(15);
q.enqueue(20);

// Print the queue after inserting integer elements
System.out.println("after enqueue of elements:\n" + q);
q.dequeue();
System.out.println("after dequeue :\n" + q);

// Example 2:

// Declare the object of String type
queue<String> q1 = new queue<>();

// Inserting elements in the queue
q1.enqueue("Coding");
q1.enqueue("Ninjas");

// Print the queue after enqueue operation
System.out.println("\n after enqueue of elements:\n" + q1);

// Printing
System.out.println("q1 front = " + q1.front()+ ", q1 rear = " + q1.rear());

}
}

 

Output

after enqueue of elements:
10->15->20
after dequeue :
15->20

after enqueue of elements:
Coding->Ninjas
q1 front = Ninjas, q1 rear = Coding

Analysis of Complexity

The taken and space taken by all the operations is O(1).

Drawbacks of Queue Implementation Using Array

There are several drawbacks to implementing a queue using an array:

  • Insertion and deletion operations can be slow in the array implementation of a queue. Especially when the front of the queue needs to be shifted after each deletion operation. This is because all the elements in the array need to be shifted to add the new front element.
     
  • In the array implementation of a queue, memory is allocated for the maximum size of the queue, even if the queue is not full. This can result in inefficient use of memory.
     
  • The array implementation of a queue does not support all the operations that can be performed on a queue, such as priority queuing or dequeuing from both ends.
     

These drawbacks make the array implementation of a queue less suitable for scenarios where dynamic memory allocation is required or where the queue size may change frequently.

Limitations of Array Representation of Queue

The array representation of a queue has some limitations that are mentioned below:

  • The array has a fixed size. The maximum number of elements that can be stored in the queue is limited by the array size. If the queue becomes full, it cannot accommodate any more elements.
     
  • A significant amount of memory will be wasted if the array size is much larger than the number of elements in the queue. The unused elements in the array will remain unoccupied.
     
  • It may be challenging to allocate additional memory for the queue if the queue size needs to be increased dynamically, especially if the available memory is limited.
     
  • In the array representation of a queue, the insertion and deletion operations can be costly. It can be costly in terms of time complexity, especially when the queue is large and the front of the queue needs to be shifted after each deletion operation.

    Must Read Array of Objects in Java

Frequently Asked Questions

What is the implementation of queue using array?

A queue using an array involves maintaining front and rear pointers. Elements are added at the rear and removed from the front, adhering to the FIFO principle.

How to implement queue in C++ using array?

In C++, a queue can be implemented using an array by managing front and rear indices. Enqueue adds elements at the rear, and dequeue removes from the front.

How can a queue be implemented using an array and a linked list explain?

In array implementation, use front and rear pointers. For a linked list, each node has a data field and a pointer to the next node, linking elements sequentially. Enqueue and dequeue operations manage these pointers accordingly.

Conclusion

In this blog, we have discussed the implementation of queue using array. We have also discussed limitations and drawbacks of implementation of queue using array. We have also explained an example to implement queue using generics.

Recommended Readings:


Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Keep Coding!

Previous article
Applications of Queue Data Structure
Next article
Queue Data Structure and Implementation in Java
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass