Implementation Of Queue in Java using Array and Generics

Soumya Agrawal
Last Updated: May 13, 2022
Difficulty Level :
EASY

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. 

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.

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

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

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

FAQ’S

  1. What do you mean by generics?
    Java generics aim to improve the code, and it is the set of related methods or a set of similar types.
     
  2. What is the time complexity to implement the queue?
    The time complexity needed to add and remove elements using operations is O(1).
     
  3. What are the different ways to implement queue?
    A queue can be implemented using Arrays, LinkedList, pointers, etc.

Key Takeaways

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.

Don’t stop here; you can use CodeStudio to practice various DSA questions typically asked in interviews. It will help you in mastering efficient coding techniques.

Keep Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think