Queue Interface: Implementation Classes
A Queue interface is one of the widely used Collection interfaces. Queue interface as shown in the below figure extends Collection interface, and hence it inherits all the operations from Collection interface. Queue, in general is a very popular data structure and is used in many scenarios. More details about Queue is available in our data structures modules understanding data structure Queue.
Figure: Queue Interface and Class Hierarchy
Queue, typically follows the notion, FIFO (first in first out). The elements that inserted first into the queue are deleted first. This is opposite to an other very popular data structure "Stack", which follows the notion LIFO (last in first out), more details about Stack is available here understanding data structure Stack. Elements into the Queue are always inserted at the "tail" of the Queue and removed from the "head" of the Queue. Both "head" and "tail" points to the same position when the Queue is empty.
There is a long list of interfaces and classes that are derived from Queue interface, we will learn about all them here.
Implementation Classes
There is a long list of classes that implements Queue interface. Some of them implement the Queue interface directly, while the rest of them implement the child interfaces of Queue interface. Deque, Blocking Queue, Blocking deque are some of the sub interfaces of the Queue interface. Some of the important classes, that implement Queue interface are summarized below.
LinkedList
As we know List is an ordered Collection, and objects in the List can be accessed/manipulated using an integer index, which represents the position at which they are stored in the List. More details about List interface is available here. One of the two classes that implements the interface List, is a LinkedList. The LinkedList class implements all the methods defined in the List interface and it also provides some extra methods that helps in manipulating the objects stored in the LinkedList.
The linked list offered by the LinkedList class implementation is, a Doubly-Linked list. To refresh your memory about doubly-linked list, visit this page Understanding Doubly-Linked list. LinkedList class provides all the standard operations that are associated with a Doubly-Linked list. LinkedList class also implements Deque interface. An example program, demonstrating the usage of LinkedList class in the context of the Queue interface is available here, Example Program.
ArrayDeque
ArrayDeque implements Deque interface and is one of the popular implementation classes of Queue interface. It is recommended to go through Deque interface before getting into the details of ArrayDeque. ArrayDeque, unlike other implementation classes of Queue interface does not have capacity restrictions. It is a re-sizable-array and also does not allow "Null" elements. Operations like add/retrieve on an ArrayDeque happens in constant time. This class is faster than a Stack when used as a stack and faster than LinkedList when used as a Queue.
ArrayBlockingQueue
ArrayBlockingQueue implements BlockingQueue interface and is one of the popular implementation classes of Queue interface. It is recommended to go through BlockingQueue interface before getting into the details of ArrayBlockingQueue. ArrayBlockingQueue, has all the properties of a Queue and BlockingQueue interfaces. ArrayBlockingQueue, unlike ArrayDeque, has capacity restrictions. If we attempt to insert an element into a full Queue or retrieve elements from an empty Queue, then it leads to the similar behavior as described in the BlockingQueue interface.
LinkedBlockingQueue
LinkedBlockingQueue implements BlockingQueue interface and is one of the popular implementation classes of Queue interface. It is recommended to go through BlockingQueue interface before getting into the details of LinkedBlockingQueue. LinkedBlockingQueue, has all the properties of a Queue and BlockingQueue interfaces. The difference between ArrayBlockingQueue and LinkedBlockingQueue is similar to the difference between an Array vs LinkedList. The nodes of a LinkedList can be added dynamically and hence LinkedBlockingQueue will not have Capacity Restrictions.
LinkedBlockingDeque
LinkedBlockingDeque implements BlockingDeque interface and is one of the popular implementation classes of Queue interface. It is recommended to go through Deque interface before getting into the details of LinkedBlockingDeque. LinkedBlockingDeque, has all the properties of a Queue and BlockingQueue interfaces. The difference between LinkedBlockingQueue and LinkedBlockingDeque is that one is a Queue while the other is a Deque (Double ended Queue).