Page Content

Tutorials

What is the Queue Interface in Java? With Code Examples

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:

  1. add(E obj): Adds an element to the queue. If the queue is capacity-restricted and full, it throws an IllegalStateException.
  2. offer(E obj): Adds an element to the queue, but returns false if the element cannot be added due to capacity restrictions, rather than throwing an exception.
  3. remove(): Retrieves and removes the element at the head of the queue. Throws a NoSuchElementException if the queue is empty.
  4. poll(): Retrieves and removes the element at the head of the queue, returning null if the queue is empty.
  5. element(): Retrieves, but doesn’t remove, the element at the head of the queue. Throws a NoSuchElementException if empty.
  6. peek(): Retrieves, but doesn’t remove, the element at the head of the queue, returning null 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), and push(E obj) (for stack-like behaviour).
  • Removing elements: removeFirst(), removeLast(), pollFirst(), pollLast(), and pop() (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.

  1. 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.
  2. 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 and ArrayList is generally preferred unless explicit synchronisation is required.
  3. 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 than HashSet (O(log n)) but provide ordered traversal.
  4. 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 custom Comparator).
  5. 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 and CopyOnWriteArrayList, which do not require external synchronisation techniques.

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.

Index