Implementation Of Queue in Java using Array and Generics

Introduction

To be an average or good programmer, one should implement various approaches like brute force, naive or efficient. For this, one should know all the Data Structures and Algorithms to optimize the complex problems in technical rounds of interviews.

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.

How to Implement Queue Using Arrays?

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

Create an array to store the elements of the queue.
Create variables to keep track of the front and rear of the queue.
Initialize the front variable to 0 and the rear variable to -1.
To add an element to the queue, increment the rear variable and add the element to the position indicated by the rear variable.
To remove an element from the queue, increment the front variable and return the element at the position indicated by the front variable.
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:

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.

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.

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.

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

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

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

Implementation of Queue using Array Operations

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

1. 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;

2. 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;
   }
}

3. 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;
}

4. 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];
}

5. isEmpty: Check if the queue is empty.

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

6. isFull: Check if the queue is full.

return rear == MAX_SIZE - 1;

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.

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.

Frequently Asked Questions

Can queue be implemented using array?

Yes, a queue can be implemented using an array in Java. You can use a circular buffer to allow for efficient enqueue and dequeue operations and also include methods to check if the queue is empty or full, as well as to get the size of the queue.

What is the time complexity to implement the queue?

The time complexity needed to add and remove elements using operations is O(1).

What are the different ways to implement queues?

A queue can be implemented using Arrays, LinkedList, pointers, etc.

Conclusion

This blog covers queue, generics, and queue implementation using arrays and generics in the Java language. With this done, you must try different questions based on the Queue data structure.

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

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

Keep Coding!