Best implementation of Java Queue?

I am working (in Java) on a recursive image processing algorithm that recursively traverses the pixels of the image, outwards from a center point.

Unfortunately, that causes a Stack Overflow. So I have decided to switch to a Queue-based algorithm.

Now, this is all fine and dandy- but considering the fact that its queue will be analyzing THOUSANDS of pixels in a very short amount of time, while constantly popping and pushing, WITHOUT maintaining a predictable state (It could be anywhere between length 100, and 20000), the queue implementation needs to have significantly fast popping and pushing abilities.

A linked list seems attractive due to its ability to push elements onto itself without rearranging anything else in the list, but in order for it to be fast enough, it would need easy access to both its head, AND its tail (or second-to-last node if it were not doubly-linked). Sadly, I cannot find any information related to the underlying implementation of linked lists in Java, so it's hard to say if a linked list is really the way to go...

This brings me to my question. What would be the best implementation of the Queue interface in Java for what I intend to do? (I do not wish to edit or even access anything other than the head and tail of the queue -- I do not wish to do any sort of rearranging, or anything. On the flip side, I DO intend to do a lot of pushing and popping, and the queue will be changing size quite a bit, so preallocating would be inefficient)

Use:

Queue<Object> queue = new LinkedList<>();

You can use .offer(E e) to append an element to the end of the queue and .poll() to dequeue and retrieve the head (first element) of the queue.

Java defined the interface Queue, the [LinkedList][1] provided an implementation.

It also maintains references to the Head and Tail elements, which you can get by .getFirst() and .getLast() respectively.

credit to @Snicolas for suggesting queue interface

[1]: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html "LinkedList<E>"

If you use LinkedList be careful. If you use it like this:

LinkedList<String> queue = new LinkedList<String>();

then you can violate queue definition, because it is possible to remove other elements than first (there are such methods in LinkedList).

But if you use it like this:

Queue<String> queue = new LinkedList<String>();

it should be ok,as this is heads-up to users that insertions should occur only at the back and deletions only at the front.

You can overcome defective implementation of the Queue interface by extending the LinkedList class to a PureQueue class that throws UnsupportedOperationException of any of the offending methods. Or you can take approach with aggreagation by creating PureQueue with only one field which is type LinkedList object, list, and the only methods will be a default constructor, a copy constructor, isEmpty(), size(), add(E element), remove(), and element(). All those methods should be one-liners, as for example:

/**
* Retrieves and removes the head of this queue.
* The worstTime(n) is constant and averageTime(n) is constant.
*
* @return the head of this queue.
* @throws NoSuchElementException if this queue is empty.
*/
public E remove()
{
    return list.removeFirst();
} // method remove()

Check out the Deque interface, which provides for insertions/removals at both ends. LinkedList implements that interface (as mentioned above), but for your use, an ArrayDeque may be better -- you won't incur the cost of constant object allocations for each node. Then again, it may not matter which implementation you use.

Normal polymoprhism goodness comes to play: the beauty of writing against the Deque interface, rather than any specific implementation of it, is that you can very easily switch implementations to test which one performs best. Just change the line with new in it, and the rest of the code stays the same.

It's better to use ArrayDeque instead of LinkedList when implementing Stack and Queue in Java. ArrayDeque is likely to be faster than Stack interface (while Stack is thread-safe) when used as a stack, and faster than LinkedList when used as a queue. Have a look at this link Use ArrayDeque instead of LinkedList or Stack.

If you know the upper bound of possible quantity of items in the queue, circular buffer is faster than LinkedList, as LinkedList creates an object (link) for each item in the queue.

I think you can some up with simple like implementation

package DataStructures;

public class Queue<T> {

   private Node<T> root;

   public Queue(T value) {
      root = new Node<T>(value);
   }

   public void enque(T value) {
      Node<T> node = new Node<T>(value);
      node.setNext(root);
      root = node;
   }

   public Node<T> deque() {

      Node<T> node = root;
      Node<T> previous = null;

      while(node.next() != null) {
         previous = node;
         node = node.next();
      }
      node = previous.next();
      previous.setNext(null);
      return node;
   }

   static class Node<T> {

      private T value;
      private Node<T> next;

      public Node (T value) {
         this.value = value;
      }

      public void setValue(T value) {
         this.value = value;
      }

      public T getValue() {
         return value;
      }

      public void setNext(Node<T> next) {
         this.next = next;
      }

      public Node<T> next() {
         return next;
      }
   }
}

However, if you still want to use the recursive algorithm, you can change it to be "tail-recursive" which probably is optimized in the JVM to avoid stack overflows.

O(1) access to first and last nodes.

class Queue {

    private Node head;
    private Node end;

    public void enqueue(Integer data){

        Node node = new Node(data);
        if(this.end == null){
            this.head = node;
            this.end = this.head;
        }
        else {
            this.end.setNext(node);
            this.end = node;
        }
    }

    public void dequeue (){

        if (head == end){
            end = null;
        }

        head = this.head.getNext();
    }


    @Override
    public String toString() {
        return head.getData().toString();
    }

    public String deepToString() {

        StringBuilder res = new StringBuilder();
        res.append(head.getData());

        Node cur = head;
        while (null != (cur = cur.getNext())){
            res.append(" ");
            res.append(cur.getData());

        }
        return res.toString();
    }
}

class Node {

    private Node next;
    private Integer data;


    Node(Integer i){
        data = i;
    }

    public Integer getData() {
        return data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

Here is the Queue Implementation with Iterator and Iterable interface

Queue Size will increase as It gets full

Queue Interface

package com.practice.ds.queue;

import com.practice.ds.queue.exception.QueueException;

public interface QueueInterface<T> {
	
	public boolean empty();
	
	public void enqueue(T item);
	
	public void dequeue() throws QueueException;
	
	public T front() throws QueueException;
	
	public void clear();
}

Custom Exception Class

package com.practice.ds.queue.exception;

public class QueueException extends Exception {

	private static final long serialVersionUID = -884127093599336807L;

	public QueueException() {
		super();
	}

	public QueueException(String message) {
		super(message);
	}

	public QueueException(Throwable e) {
		super(e);
	}

	public QueueException(String message, Throwable e) {
		super(message, e);
	}
}

Implementation of Queue

package com.practice.ds.queue;

import java.util.Iterator;

import com.practice.ds.queue.exception.QueueException;

public class Queue<T> implements QueueInterface<T>, Iterable<T> {

	private static final int DEFAULT_CAPACITY = 10;
	private int current = 0;
	private int rear = 0;
	private T[] queueArray = null;
	private int capacity = 0;

	@SuppressWarnings("unchecked")
	public Queue() {
		capacity = DEFAULT_CAPACITY;
		queueArray = (T[]) new Object[DEFAULT_CAPACITY];
		rear = 0;
		current = 0;
	}

	@Override
	public boolean empty() {
		return capacity == current;
	}

	@Override
	public void enqueue(T item) {
		if(full())
			ensureCapacity();
		queueArray[current] = item;
		current++;
	}

	@Override
	public void dequeue() throws QueueException {
		T dequeuedItem = front();
		rear++;
		System.out.println("Dequed Item is " + dequeuedItem);
	}

	@Override
	public T front() throws QueueException {
		return queueArray[rear];
	}

	@Override
	public void clear() {
		for (int i = 0; i < capacity; i++)
			queueArray[i] = null;
		current = 0;
		rear = 0;
	}

	@SuppressWarnings("unchecked")
	private void ensureCapacity() {
		if (rear != 0) {
			copyElements(queueArray);
		} else {
			capacity *= 2;
			T[] tempQueueArray = (T[]) new Object[capacity];
			copyElements(tempQueueArray);
		}
		current -= rear;
		rear = 0;
	}
	
	private void copyElements(T[] array) {
		for (int i = rear; i < current; i++)
			array[i - rear] = queueArray[i];
		queueArray = array;
	}

	@Override
	public Iterator<T> iterator() {
		return new QueueItearator<T>();
	}

	public boolean full() {
		return current == capacity;
	}

	private class QueueItearator<T> implements Iterator<T> {

		private int index = rear;

		@Override
		public boolean hasNext() {
			return index < current;
		}

		@SuppressWarnings("unchecked")
		@Override
		public T next() {
			return (T) queueArray[index++];
		}
	}

}