Which Java Queue is best for recursive image processing?

General Discussions
, ,
1

What is the best Java Queue implementation for handling a recursive image processing algorithm?

I am working on an algorithm that traverses an image pixel by pixel, expanding outward from a center point. Initially, I used recursion, but it led to a Stack Overflow, so I decided to switch to a Queue-based approach.

Since this queue will process thousands of pixels rapidly, constantly pushing and popping elements while its size fluctuates (anywhere between 100 and 20,000 elements), I need an implementation that offers fast enqueue (push) and dequeue (pop) operations.

A LinkedList seems promising because it can append elements without reordering, but I need efficient access to both the head and tail. However, I couldn’t find clear information about Java’s linked list implementation to confirm if it’s the best choice.

This brings me to my question: How do I choose the best Java Queue implementation for my use case? Given my requirements—fast dynamic resizing, efficient push/pop operations, and no need for random access—which queue structure would be optimal?

2

From my experience with large-scale image processing pipelines, picking the right Java queue implementation makes a huge difference in performance.

Use ArrayDeque (Best All-Around Choice)

If you want blazing-fast queue operations, ArrayDeque is a solid pick. It offers efficient enqueue (addLast) and dequeue (pollFirst) operations with O(1) complexity. Since it uses a resizable array internally, it handles dynamic resizing better than a LinkedList and offers lower memory overhead.

:fire: Why ArrayDeque?

  • Faster than LinkedList for queue operations.
  • O(1) for adding and removing elements from both ends.
  • Minimal memory overhead (no node pointers).

Code Example:

Queue<Pixel> pixelQueue = new ArrayDeque<>();  

pixelQueue.add(new Pixel(10, 10));  // Push  
Pixel nextPixel = pixelQueue.poll();  // Pop
3

Building on @raimavaswani point, if you’re dealing with fluctuating queue sizes, you might want to consider LinkedList for its dynamic memory management.

Use LinkedList (Doubly-Linked Implementation) While ArrayDeque is great for speed, LinkedList shines when your queue size varies significantly. Since it uses a doubly-linked structure, it offers O(1) insertion and removal at both ends, without resizing overhead.

:fire: Why LinkedList?

  • O(1) enqueue/dequeue without resizing.
  • Grows dynamically without preallocation.
  • Ideal if the queue frequently fluctuates between 100 and 20,000 elements.

Code Example:

Queue<Pixel> pixelQueue = new LinkedList<>();  

pixelQueue.add(new Pixel(10, 10));  // Push  
Pixel nextPixel = pixelQueue.poll();  // Pop
4

To build on @dipen-soni answer, if you plan to scale your image processing with multiple threads, you’ll need a thread-safe Java queue implementation.

Use ConcurrentLinkedQueue (Thread-Safe Option) For parallelized image processing, ConcurrentLinkedQueue is a winner. It offers lock-free, thread-safe operations, making it perfect for multi-threaded environments. It still maintains O(1) enqueue and dequeue efficiency, just like LinkedList.

:fire: Why ConcurrentLinkedQueue?

  • Non-blocking and thread-safe.
  • Faster in multi-threaded environments.
  • No locks, ensuring smooth performance.

Code Example:

Queue<Pixel> pixelQueue = new ConcurrentLinkedQueue<>();  

pixelQueue.add(new Pixel(10, 10));  // Push  
Pixel nextPixel = pixelQueue.poll();  // Pop