Implementation Of Queue in Java using Array and Generics

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());      
  }  
}

You can also try this code with Online Java Compiler

Run Code

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();
	}
}

You can also try this code with Online Java Compiler

Run Code

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());

	}
}

You can also try this code with Online Java Compiler

Run Code

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:

• Doubly Linked List
• Generics in Java
• Circular Queue Implementations and Operations
• Implementation of Deque using Doubly Linked Lists
• How to Remove Specific Elements from the Queue
• FIFO: First in First Out
• Queue Data Structure in Java
• Advantages of Circular Queue
• Array in Javascript

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!