How to Instantiate a Queue in Java
-
Use the
LinkedList
Class to Implement aQueue
Object in Java -
Use the
ArrayDeque
Class to Implement aQueue
Object in Java -
Use the
PriorityQueue
Class to Implement aQueue
Object in Java -
Instantiate a Synchronous Queue to Implement a
Queue
Object in Java -
Using
Queue
Interface Implementations - Conclusion
In Java, a Queue
represents a collection designed for holding elements before processing. It follows the FIFO (First-In-First-Out) principle, making it a fundamental data structure in many applications. Instantiating a Queue
can be accomplished through various approaches, each tailored to specific use cases and requirements.
This article will introduce methods to instantiate a Queue
object in Java. We will further describe and implement the method calls from the instantiated object in this tutorial.
A Queue
is an interface, and we cannot create an object directly. But we can implement the class that already implements the Queue
interface.
Some of those classes are AbstractQueue
, ArrayDeque
, DelayQueue
, and LinkedList
. Therefore, we will be using the LinkedList
and ArrayDeque
classes to instantiate Queue
in this tutorial.
Use the LinkedList
Class to Implement a Queue
Object in Java
One of the most common ways to create a Queue
in Java is by using the LinkedList
class. It implements the Queue
interface, making it an ideal choice for queue operations.
The LinkedList
class implements the LinkedList
data structure concept. It is a part of the collection framework and available in the java.util
package.
The elements in the LinkedList
are stored in the form of pointers and addresses. The element is known as a node. We cannot access the node directly in LinkedList
.
To access a node, we have to start from the head and follow through to reach the node that we want to access. The LinkedList
implements the List
interface, and it inherits all the methods present in the List
interface and collection interface.
Queue
is also available in the same package. We can create an object of Queue
implementing the LinkedList
class. We can use the add()
function to append the data in the queue.
Example Code:
import java.util.LinkedList;
import java.util.Queue;
public class QueueDemo {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.add(8);
queue.add(9);
queue.add(10);
queue.add(2);
queue.add(5);
System.out.println("Added Queue in memory: " + queue);
}
}
Output:
Added Queue in memory: [8, 9, 10, 2, 5]
Firstly, import Queue
and LinkedList
using the import java.util.Queue
and the import java.util.LinkedList
respectively. Then, create a class QueueDemo
and declare the main method.
Next, instantiate an object queue
by implementing the LinkedList
class. Call the add()
method with the object and add five integer values. Finally, print the elements of the Queue
.
In the example, we used a LinkedList
class that implements the Queue
interface to create a queue object. This is because the Queue
is an interface, and we cannot create its object directly.
We have specified the generic type Integer
while creating the object because we store the integer value in the queue. The output section displays the elements stored in the queue.
Use the ArrayDeque
Class to Implement a Queue
Object in Java
Another option to create a Queue
is through the ArrayDeque
class. It provides a resizable array implementation of the Deque
interface, which extends the Queue
interface.
Java language has defined the ArrayDeque
class as a part of the collection framework. It creates an empty set of locations in memory with an initial capacity sufficient to hold sixteen elements.
ArrayDeque
is also called “Array Double Ended Queue”, which allows us to insert or delete an element from both sides. It implements a Stack
(Last-In-First-Out) or a Queue
(First-In-First-Out).
Therefore, we can create an object of Queue
with the implementation of the ArrayDeque
class.
Example code:
import java.util.ArrayDeque;
import java.util.Queue;
public class Demo {
public static void main(String[] args) {
Queue<String> aq = new ArrayDeque<String>();
aq.add("first");
aq.add("second");
aq.add("third");
aq.add("fourth");
System.out.println("Added Queue in memory: " + aq);
}
}
Output:
Added Queue in memory: [first, second, third, fourth]
Import the packages like the previous method, but make sure to import the ArrayDeque
in this method instead of the LinkedList
. Then, create a class Demo
and declare the main
method.
Then, implement the ArrayDeque
class by instantiating the Queue
interface. Create an object of Queue
as aq
.
Use the aq
object to call the add()
method four times. Append four different strings. Finally, print the aq
object.
In the example above, we have used the generic type String
while creating the object. It is because we are adding string items in the queue.
Thus, we have instantiated a Queue
object implementing the ArrayDeque
class.
Use the PriorityQueue
Class to Implement a Queue
Object in Java
In Java, the PriorityQueue
class offers a versatile and efficient implementation of the Queue
interface. Unlike a traditional queue, a PriorityQueue
does not strictly follow the FIFO (First-In-First-Out) principle.
Instead, it orders elements based on their natural order or a custom comparator. This powerful feature makes it suitable for various scenarios where element ordering matters.
Java offers a PriorityQueue
class that maintains the elements in a sorted order based on a specified comparator or the natural ordering of elements.
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
// Instantiate Priority Queue
Queue<Double> priorityQueue = new PriorityQueue<>();
}
}
PriorityQueue
implements the Queue
interface and sorts elements according to their natural order or using a custom comparator. Here, Queue<Double>
represents a priority queue to store double values.
To establish custom ordering for elements, a Comparator
can be specified during PriorityQueue
creation:
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> customPriorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
}
}
This code initializes a PriorityQueue
named customPriorityQueue
to hold strings in descending order, achieved by providing Comparator.reverseOrder()
as an argument.
Here’s a complete code example demonstrating the use of the PriorityQueue
class to implement a Queue
object in Java:
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
// Creating a PriorityQueue with natural ordering (ascending)
Queue<Integer> priorityQueue = new PriorityQueue<>();
// Adding elements to the PriorityQueue
priorityQueue.offer(10);
priorityQueue.offer(5);
priorityQueue.offer(8);
priorityQueue.offer(12);
// Displaying elements in the PriorityQueue (natural order)
System.out.println("Elements in PriorityQueue (Natural Order):");
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
// Creating a PriorityQueue with a custom comparator (descending)
Queue<String> customPriorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
// Adding elements to the custom PriorityQueue
customPriorityQueue.offer("Apple");
customPriorityQueue.offer("Banana");
customPriorityQueue.offer("Orange");
customPriorityQueue.offer("Mango");
// Displaying elements in the custom PriorityQueue (custom order)
System.out.println("Elements in Custom PriorityQueue (Custom Order):");
while (!customPriorityQueue.isEmpty()) {
System.out.println(customPriorityQueue.poll());
}
}
}
The code above demonstrates the use of PriorityQueue
in two scenarios: one with the default natural ordering and another with a custom ordering.
For the natural order PriorityQueue
, integers are added randomly, and the queue is polled, displaying elements in ascending order.
The custom order PriorityQueue
is created using Comparator.reverseOrder()
, resulting in elements being displayed in descending order based on the default string comparison.
Output:
Elements in PriorityQueue (Natural Order):
5
8
10
12
Elements in Custom PriorityQueue (Custom Order):
Orange
Mango
Banana
Apple
This example illustrates the basic usage of PriorityQueue
to implement a Queue
object in Java, showcasing both natural and custom ordering of elements.
Instantiate a Synchronous Queue to Implement a Queue
Object in Java
A SynchronousQueue
is a specialized blocking queue that enables communication between threads in a producer-consumer pattern. This queue does not have any capacity to hold elements, and every put
operation by a producer thread blocks until a consumer thread performs a take
operation.
The SynchronousQueue
class is an implementation of the BlockingQueue
interface, allowing elements to be passed synchronously between threads.
Unlike other queues, it doesn’t store elements. Instead, it acts as a rendezvous point where a producer thread must wait for a consumer thread to retrieve the element and vice versa, making it an interesting choice for certain synchronization scenarios.
import java.util.Queue;
import java.util.concurrent.SynchronousQueue;
public class Main {
public static void main(String[] args) {
// Instantiate Synchronous Queue
Queue<Boolean> syncQueue = new SynchronousQueue<>();
}
}
SynchronousQueue
implements the BlockingQueue
interface, supporting blocking insertion and retrieval operations. Queue<Boolean>
creates a synchronous queue containing Boolean elements.
Example:
import java.util.concurrent.SynchronousQueue;
public class SyncQueueUseCase {
public static void main(String[] args) {
SynchronousQueue<String> syncQueue = new SynchronousQueue<>();
// Producer thread
new Thread(() -> {
try {
syncQueue.put("Data");
// Data is handed over to the consumer
} catch (InterruptedException e) {
// Handle InterruptedException
}
}).start();
// Consumer thread
new Thread(() -> {
try {
String data = syncQueue.take();
// Process data received from the producer
} catch (InterruptedException e) {
// Handle InterruptedException
}
}).start();
}
}
This code showcases the usage of a SynchronousQueue
for synchronized communication between producer and consumer threads. It initializes the queue, starts a producer thread that places an element into the queue, and a consumer thread that retrieves the element for processing.
The SynchronousQueue
allows direct handoff of elements between threads, blocking if necessary until both producer and consumer are ready, enabling synchronized communication in a threaded environment.
Using Queue
Interface Implementations
In Java, the Queue
interface represents a collection designed for holding elements before processing, typically following the First-In-First-Out (FIFO) principle. Java offers multiple implementations of the Queue
interface, each with its unique characteristics and suitability for specific use cases.
The Queue
interface extends the Collection
interface and inherits its basic operations such as add
, remove
, and element
. It includes additional operations inherited from the Collection
interface and defines methods such as offer
, poll
, and peek
that facilitate queue-specific functionalities.
Common Methods in the Queue
Interface:
offer(E e)
: Adds an element to the queue if space permits; returnstrue
if successful,false
otherwise.poll()
: Retrieves and removes the head of the queue; returnsnull
if the queue is empty.peek()
: Retrieves but does not remove the head of the queue; returnsnull
if the queue is empty.
In addition to specific classes, Java provides various implementations of the Queue
interface, each serving distinct purposes.
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
public class Main {
public static void main(String[] args) {
// Using Queue interface implementations
Queue<Character> queue3 = new LinkedList<>();
Queue<String> queue4 = new PriorityQueue<>();
Queue<Integer> queue5 = new ArrayBlockingQueue<>(10);
Queue<Long> queue6 = new LinkedBlockingQueue<>();
}
}
LinkedList
and PriorityQueue
classes implement the Queue
interface directly. ArrayBlockingQueue
and LinkedBlockingQueue
offer thread-safe operations and bounded/unbounded capacities, respectively.
Different Implementations of Queue
LinkedList
LinkedList
is a classic implementation of the Queue
interface in Java, providing a doubly-linked list-based implementation.
It offers efficient add
, remove
, and peek
operations. However, iteration over elements might be slower compared to other implementations.
Example:
Queue<Integer> linkedQueue = new LinkedList<>();
linkedQueue.offer(10);
int head = linkedQueue.peek();
int removed = linkedQueue.poll();
This code initializes a queue using a linked list implementation, adds an element to the queue, retrieves the element at the head of the queue without removing it, and then removes the element at the head of the queue.
ArrayDeque
ArrayDeque
implements the Deque
interface but can be used as a Queue
. It’s a resizable array-based implementation that provides better performance than LinkedList
in most scenarios.
It’s not thread-safe for concurrent access without external synchronization.
Example:
Queue<Integer> arrayDequeQueue = new ArrayDeque<>();
arrayDequeQueue.offer(20);
int head = arrayDequeQueue.peek();
int removed = arrayDequeQueue.poll();
This code initializes a queue using an ArrayDeque
implementation, adds an element to the queue, retrieves the element at the head of the queue without removing it, and then removes the element at the head of the queue.
PriorityQueue
PriorityQueue
is a priority-based implementation that doesn’t strictly follow FIFO. It’s based on a priority heap and orders elements based on their natural order or a custom comparator.
Higher-priority elements are retrieved before lower-priority ones.
Example:
Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(30);
int head = priorityQueue.peek();
int removed = priorityQueue.poll();
This code initializes a queue using a PriorityQueue
, adds an element to the queue based on its priority, retrieves the element at the head of the queue without removing it, and then removes the highest-priority element from the queue.
Use Cases for Different Implementations
- Use
LinkedList
for a simple FIFO queue with good insertion and deletion performance. - Prefer
ArrayDeque
for a high-performance general-purpose queue. - Use
PriorityQueue
when elements need to be retrieved based on their priority order.
Considerations
- Thread Safety: None of the implementations are inherently thread-safe for concurrent access.
- Iterating Performance:
LinkedList
might have a slower iteration performance compared toArrayDeque
.
Conclusion
Instantiating a Queue
in Java involves choosing an appropriate implementation based on the requirements. Whether it’s a simple FIFO structure, a priority-based arrangement, or thread-safe operations, Java’s versatile Queue
implementations cater to diverse scenarios.
By employing different approaches, developers can leverage the efficiency, ordering, synchronization, and specific functionalities offered by various Queue
implementations, ensuring optimal performance and functionality in their Java applications.