Generic queue in Java
Before understanding how to implement a generic queue in java, one must know about generics and queue in java.
Generics in Java
Generics are parameterized types. The goal is to enable type (Integer, String,... etc., and user-defined types) to be a parameter to methods, classes, and interfaces. Generics can be used to make classes that function with various data types. A generic entity is one that functions on a parameterized type, such as a class, interface, or method.
Why Generics?
The Object is the superclass of all other classes, and Object reference can refer to any object. These features lack type safety. Generics add that type of safety feature. We will discuss that type of safety feature in later examples.
Types of Java Generics
Generic Method: A generic Java method performs an operation and then returns some value. Similar to a normal function, a generic method has type parameters that are listed according to the actual type. This enables a broader application of the generic method. Since the compiler handles type safety, programmers can write code more quickly because they do not need to carry out long, individual type castings.
Generic Classes: The implementation of a generic class is identical to that of a non-generic class. The presence of a type parameter section is the only distinction. There may be different parameter types, each separated by a comma. The classes are referred to as parameterized classes or parameterized types if they accept one or more parameters.
Filename: Main.java
// Java program to show the working of user-defined
// Generic classes
// We use < > to specify Parameter type
// Driver class to test above
class Main {
public static void main(String[] args)
{
// instance of Integer type
Test<Integer> iObj = new Test<Integer>(15) ;
System.out.println(iObj.getObject()) ;
// instance of String type
Test<String> sObj
= new Test<String>("Hello World") ;
System.out.println(sObj.getObject()) ;
}
}
class Test<T> {
// An object of type T is declared
T obj;
Test(T obj) { this.obj = obj; } // constructor
public T getObject() { return this.obj; }
}
Output
Generic Functions: Additionally, we can create generic functions that, depending on the kind of arguments supplied to the generic method, can be called with various types of arguments. Each method is handled by the compiler.
Program
Filename: FuncTest.java
// Java program to show the working of user-defined
// Generic functions
class FuncTest {
// A Generic method example
static <T> void genericDisplay(T element)
{
System.out.println(element.getClass().getName()
+ " = " + element) ;
}
// Driver method
public static void main(String[] args)
{
// Calling generic method with an Integer argument
genericDisplay(11) ;
// Calling generic method with a String argument
genericDisplay("Hello") ;
// Calling generic method with a double argument
genericDisplay(1.0) ;
}
}
Output
Queue in Java
The java.util package contains the Queue interface, which extends the Collection interface and is used to hold elements in FIFO (First In First Out) sequence that are about to be processed. It is an ordered list of objects that can only be used to add items to the end of the list and remove items from the beginning, adhering to the FIFO or First-In-First-Out concept.
The queue is a linear data structure that adheres to the FIFO rule (first in first out). We can use Queue not only for integers but also for strings, floats, or characters. There are 5 main operations in Queue:
- enqueue() adds element x to the front of the queue.
- dequeue() removes the last element of the queue.
- front() returns the front element.
- rear() returns the rear element.
- empty() returns whether the queue is empty or not.
Note: For all operations, the time complexity is of order 1.
How to Implement Queue in Java using Generics?
Below is the program to implement the Generic queue in java.
Filename: EXAMPLE.java
// Java Program to Implement Queue using Array and Generics
// Importing input-output classes
import java.io.* ;
// Importing all utility classes
import java.util.* ;
// Class 1
// Helper Class(user defined - generic queue class)
// Class 2
// Main class
class EXAMPLE {
// Main driver method
public static void main(String args[])
{
// Case 1 : Integer Queue
// Creating object of queue Class (user defined)
// Declaring object of integer type
queue<Integer> q1 = new queue<>() ;
// Pushing elements to the integer object created
// Custom input integer entries
q1.enqueue(5) ;
q1.enqueue(10) ;
q1.enqueue(20) ;
// Print the queue after inserting integer elements
System.out.println(
"q1 after enqueue of 3 elements:\n" + q1) ;
q1.dequeue();
System.out.println("q1 after dequeue :\n" + q1) ;
// Case 2 : String Queue
// Creating object of queue Class (user defined)
// Declaring object of string type
queue<String> q2 = new queue<>() ;
// Pushing elements to the String object created
// Custom input string entries
q2.enqueue("hello") ;
q2.enqueue("world") ;
q2.enqueue("EXAMPLE") ;
// Print the queue after inserting string elements
System.out.println(
"\nq2 after enqueue of 3 elements:\n" + q2) ;
// Printing front and rear of the above queue
System.out.println("q2 front = " + q2.front()
+ ", q2 rear = " + q2.rear()) ;
// Case 3 : Float Queue
// Creating object of queue Class (user defined)
// Declaring object of float type
queue<Float> q3 = new queue<>() ;
// Display message only
System.out.println(
"\nCreated new Float type queue q3...") ;
// Display whether the queue is empty or not
// using the empty() method
System.out.println(
"Checking if the queue is empty or not:\n"
+ q3.empty()) ;
}
}
class queue<T> {
// front and rear variables are initially initiated to
// -1 pointing to no element that controls the queue
int front = -1, rear = -1 ;
// Creating an object of ArrayList class of T type
ArrayList<T> A = new ArrayList<>() ;
// Method 1
// Returns value of the element at the front
T front()
{
// If it is not pointing to any element in the queue
if (front == -1)
return null ;
// else return the front element
return A.get(front) ;
}
// Method 2
// Returns value of element at rear
T rear()
{
// If it is not pointing to any element in the queue
if (rear == -1)
return null ;
return A.get(rear) ;
}
// Method 3
// Inserts element at the front of the queue
void enqueue(T X)
{
// If the queue is empty
if (this.empty()) {
front = 0 ;
rear = 0 ;
A.add(X) ;
}
// If the queue is not empty
else {
front++ ;
if (A.size() > front) {
// Mov front pointer to next
A.set(front, X) ;
}
else
// Add element to the queue
A.add(X) ;
}
}
// Method 4
// Deletes elements from the rear of the queue
void dequeue()
{
// if the queue doesn't have any elements
if (this.empty())
// Display message when the queue is already empty
System.out.println("Queue is already empty") ;
// If the queue has only one element
else if (front == rear) {
// Both are pointing to the same element
front = rear = -1 ;
}
// If the queue has more than one element
else {
// Increment the rear
rear++ ;
}
}
// Method 5
// Checks whether the queue is empty
boolean empty()
{
// Both are initialized to the same value
// as assigned at declaration means no queue was made
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(A.get(i)) + "->" ;
}
Ans += String.valueOf(A.get(front)) ;
return Ans ;
}
}
Output
Benefits of Generics
Generic code provides several advantages over non-generic code for programs.
- Code reuse: Once a method, class, or interface is written, it can be applied to any type.
- Type Safety: Generics cause faults to show up during compilation rather than during execution. It is preferable to find problems in your code during compilation rather than having it fail during execution. If the programmer accidentally adds an integer object instead of a string to an ArrayList intended to contain student names, the compiler will still allow it. However, there are issues at runtime when we receive this data from an ArrayList.