Queue - sivakrsna/Java-Interview GitHub Wiki

Queue

  • A collection designed for holding elements prior to processing.
  • Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner.
  • Queue implementations generally do not allow insertion of null elements

The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue's ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.

PriorityQueue

  • The PriorityQueue class is a priority queue based on the heap data structure.
  • This queue orders elements according to the order specified at construction time, which can be the elements' natural ordering or the ordering imposed by an explicit Comparator.
  • A priority queue does not permit null elements.
  • The queue retrieval operations — poll, remove, peek, and element — access the element at the head of the queue.
  • The head of the queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements; ties are broken arbitrarily.

Concurrent Queue Implementations

The java.util.concurrent package contains a set of synchronized Queue interfaces and classes. BlockingQueue extends Queue with operations that wait for the queue to become nonempty when retrieving an element and for space to become available in the queue when storing an element. This interface is implemented by the following classes:

  1. LinkedBlockingQueue — an optionally bounded FIFO blocking queue backed by linked nodes
  2. ArrayBlockingQueue — a bounded FIFO blocking queue backed by an array
  3. PriorityBlockingQueue — an unbounded blocking priority queue backed by a heap
  4. DelayQueue — a time-based scheduling queue backed by a heap
  5. SynchronousQueue — a simple rendezvous mechanism that uses the BlockingQueue interface

In JDK 7, TransferQueue is a specialized BlockingQueue in which code that adds an element to the queue has the option of waiting (blocking) for code in another thread to retrieve the element. TransferQueue has a single implementation:

  • LinkedTransferQueue — an unbounded TransferQueue based on linked nodes

DEQUE

  • A linear collection that supports element insertion and removal at both ends.
  • The name deque is short for "double ended queue" and is usually pronounced "deck".

General-purpose implementations

  1. LinkedList
  2. ArrayDeque
  • The ArrayDeque class is the resizable array implementation of the Deque interface, whereas the LinkedList class is the list implementation.
  • The basic insertion, removal and retieval operations in the Deque interface addFirst, addLast, removeFirst, removeLast, getFirst and getLast. The method addFirst adds an element at the head whereas addLast adds an element at the tail of the Deque instance.
  • The LinkedList implementation is more flexible than the ArrayDeque implementation. LinkedList implements all optional list operations. null elements are allowed in the LinkedList implementation but not in the ArrayDeque implementation.
  • In terms of efficiency, ArrayDeque is more efficient than the LinkedList for add and remove operation at both ends. The best operation in a LinkedList implementation is removing the current element during the iteration. LinkedList implementations are not ideal structures to iterate.
  • The LinkedList implementation consumes more memory than the ArrayDeque implementation.

Concurrent Deque Implementations

The LinkedBlockingDeque class is the concurrent implementation of the Deque interface. If the deque is empty then methods such as takeFirst and takeLast wait until the element becomes available, and then retrieves and removes the same element.