Queue Interface in Java
A collection is represented by the Queue
interface for storing elements prior to processing, usually (though not always) in a First-In, First-Out (FIFO) fashion. This indicates that the first element to be eliminated is the one that was inserted first.
The Queue
interface’s primary methods are as follows:
add(E obj)
: Adds an element to the queue. If the queue is capacity-restricted and full, it throws anIllegalStateException
.offer(E obj)
: Adds an element to the queue, but returnsfalse
if the element cannot be added due to capacity restrictions, rather than throwing an exception.remove()
: Retrieves and removes the element at the head of the queue. Throws aNoSuchElementException
if the queue is empty.poll()
: Retrieves and removes the element at the head of the queue, returningnull
if the queue is empty.element()
: Retrieves, but doesn’t remove, the element at the head of the queue. Throws aNoSuchElementException
if empty.peek()
: Retrieves, but doesn’t remove, the element at the head of the queue, returningnull
if empty.
Common implementations include PriorityQueue
and LinkedList
(when used as a FIFO queue).
Here’s a quick code example demonstrating basic Queue
operations:
import java.util.LinkedList;
import java.util.Queue;
import java.util.PriorityQueue;
public class QueueDemo {
public static void main(String[] args) {
System.out.println("--- LinkedList as a Queue ---");
Queue<String> fifoQueue = new LinkedList<>();
fifoQueue.offer("First in line"); // Adds to tail, returns boolean
fifoQueue.add("Second in line"); // Adds to tail, throws exception if capacity-restricted and full
fifoQueue.add("Third in line");
System.out.println("Queue: " + fifoQueue);
System.out.println("Peek: " + fifoQueue.peek()); // Retrieves head, doesn't remove
System.out.println("Queue after peek: " + fifoQueue);
System.out.println("Poll: " + fifoQueue.poll()); // Retrieves and removes head
System.out.println("Queue after poll: " + fifoQueue);
System.out.println("Remove: " + fifoQueue.remove()); // Retrieves and removes head
System.out.println("Queue after remove: " + fifoQueue);
System.out.println("\n--- PriorityQueue ---");
// Elements are sorted based on their natural order or a custom comparator
Queue<Integer> pq = new PriorityQueue<>();
pq.add(9);
pq.add(2);
pq.add(3);
pq.add(1);
System.out.println("PriorityQueue (internal order): " + pq);
System.out.println("Polling from PriorityQueue: " + pq.poll()); // Smallest element removed first
System.out.println("PriorityQueue after poll: " + pq);
}
}
Code Output:
--- LinkedList as a Queue ---
Queue: [First in line, Second in line, Third in line]
Peek: First in line
Queue after peek: [First in line, Second in line, Third in line]
Poll: First in line
Queue after poll: [Second in line, Third in line]
Remove: Second in line
Queue after remove: [Third in line]
--- PriorityQueue ---
PriorityQueue (internal order):
Polling from PriorityQueue: 1
PriorityQueue after poll:
Deque Interface
An extension of Queue
, the Deque
(Double-Ended Queue) interface is a linear collection that allows for element insertion and removal at both ends. For this reason, a Deque
can be used as a Last-In, First-Out (LIFO) stack or as a conventional FIFO queue.
The following are important Deque
interface methods:
- Adding elements:
addFirst(E obj)
,addLast(E obj)
,offerFirst(E obj)
,offerLast(E obj)
, andpush(E obj)
(for stack-like behaviour). - Removing elements:
removeFirst()
,removeLast()
,pollFirst()
,pollLast()
, andpop()
(for stack-like behaviour). - Inspecting elements (without removing):
getFirst()
,getLast()
,peekFirst()
,peekLast()
.
Implementations include ArrayDeque
and LinkedList
.
Here’s a code example for Deque
operations:
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeDemo {
public static void main(String[] args) {
System.out.println("--- ArrayDeque as a Queue ---");
Deque<String> myDeque = new ArrayDeque<>();
myDeque.addFirst("Front Item"); // Add to the head
myDeque.addLast("Back Item"); // Add to the tail
myDeque.add("Another Back Item"); // Same as addLast
System.out.println("Deque: " + myDeque);
System.out.println("Get First: " + myDeque.getFirst()); // Get head, don't remove
System.out.println("Get Last: " + myDeque.getLast()); // Get tail, don't remove
System.out.println("Poll First: " + myDeque.pollFirst()); // Remove head
System.out.println("Deque after pollFirst: " + myDeque);
System.out.println("Remove Last: " + myDeque.removeLast()); // Remove tail
System.out.println("Deque after removeLast: " + myDeque);
System.out.println("\n--- ArrayDeque as a Stack (LIFO) ---");
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10); // Adds element to the head (top of stack)
stack.push(20);
stack.push(30);
System.out.println("Stack: " + stack);
System.out.println("Peek: " + stack.peek()); // Retrieves head, doesn't remove (top of stack)
System.out.println("Pop: " + stack.pop()); // Retrieves and removes head (top of stack)
System.out.println("Stack after pop: " + stack);
}
}
Code Output:
--- ArrayDeque as a Queue ---
Deque: [Front Item, Back Item, Another Back Item]
Get First: Front Item
Get Last: Another Back Item
Poll First: Front Item
Deque after pollFirst: [Back Item, Another Back Item]
Remove Last: Another Back Item
Deque after removeLast: [Back Item]
--- ArrayDeque as a Stack (LIFO) ---
Stack: [41-43]
Peek: 30
Pop: 30
Stack after pop:
When to Use Which Collection Type (Best Practices)
Selecting an appropriate collection type is essential for code that is both efficient and maintainable. The choice frequently depends on the particular needs for thread safety, access patterns, ordering, and duplicates.
- Arrays:
- Use when: You need a fixed-size container for values of a single type and know the size at creation. They’re efficient for direct index access. Can be useful for saving memory in large arrays.
- Avoid when: You need dynamic sizing or plan frequent insertions/deletions, as arrays have fixed lengths. To overcome the fixed size limitation, you’d typically move to collections.
- Lists (e.g., ArrayList, LinkedList, Vector):
- Use when: You need an ordered collection that allows duplicate values and elements are accessed by their numerical index.
- ArrayList: Best for frequent retrieval/searching by index, as it offers constant-time access. However, deletion and insertion in the middle are slower due to element shifting. It’s generally non-synchronized, so not thread-safe by default.
- LinkedList: Best for frequent insertions and deletions (especially at the beginning or end) because elements are based on separate nodes, making these operations efficient. Searching/retrieving elements is slower as it may require traversing many nodes.
- Vector: Similar to
ArrayList
but is synchronized (thread-safe). It’s considered a legacy class andArrayList
is generally preferred unless explicit synchronisation is required.
- Sets (e.g., HashSet, TreeSet, LinkedHashSet):
- Use when: You need a collection that does not allow duplicate elements. They are primarily value-based.
- HashSet: Provides random (no guaranteed) order for its elements. Offers good performance for basic operations (O(1) average time complexity).
- LinkedHashSet: Maintains the insertion order of elements while still ensuring uniqueness.
- TreeSet: Stores elements in a sorted manner (either natural order or according to a specified
Comparator
). Operations are slower thanHashSet
(O(log n)) but provide ordered traversal.
- Maps (e.g., HashMap, TreeMap, LinkedHashMap, Hashtable):
- When to use: Each key must be unique in the key-value pairs you need to store.
- HashMap: Does not ensure order and permits various null values and one null key. It’s not coordinated.
- Hashtable: Synced and does not permit null keys or values. Moreover, it is a heritage class.
- TreeMap: Key-value pairs are stored in a
TreeMap
in a sorted order determined by the keys (natural order or customComparator
).
- Concurrent Collections:
- Use when: Developing multi-threaded programs that require simultaneous access to and modification of collections by several threads. Thread-safe operations are provided by classes such as
ConcurrentHashMap
andCopyOnWriteArrayList
, which do not require external synchronisation techniques.
- Use when: Developing multi-threaded programs that require simultaneous access to and modification of collections by several threads. Thread-safe operations are provided by classes such as
Immutability of Collections (Briefly)
Collections that cannot have their contents changed once they are created are known as immutable collections. Consequently, once the collection is initialised, it is impossible to add, remove, or alter pieces.
The following are some advantages of utilising immutable collections:
- Thread Safety: They are naturally thread-safe since their state is immutable, which removes the possibility of concurrent alteration in situations with many threads.
- Predictability and Reliability: Since their state is fixed, debugging and reasoning about programming is simpler.
- Security: They are able to stop unauthorised or malevolent data alteration.
In order to facilitate the creation of immutable collections, factory methods such as List.of()
, Set.of()
, and Map.of()
were introduced in Java 9. Collections.unmodifiableList()
, Collections.unmodifiableSet()
, and Collections.unmodifiableMap()
are methods from the Collections
utility class that can be used to build unmodifiable views of existing collections for older Java versions or for extra control. A wrapper that stops changes to an existing collection is returned by these methods, although the underlying collection may still be changeable. To ensure thread safety and prevent memory leaks, it is often a good idea to make enum instances immutable by making sure they have no extra fields or that all of these fields are final
and immutable in and of themselves.