What is Queue:
Queue is one of an important data structure which typically (but not necessarily) abide by rule of FIFO (First In First Out) i.e. the element which will be inserted first will be removed from the queue in that insertion order. The time complexity of queue in best case scenario should be O(1) both in case of element insertion or element removal.Queue in Java:
In Java, Queue (java.util.Queue) is defined as an interface. It means that any java class that can be called as Queue will need to abide by contract defined in java.util.Queue interface by either implementing Queue interface or its sub-interface (BlockingQueue, BlockingDeque, Deque, TransferQueue). If you need skeleton class on top of which you can write up your own queue implementation, then there is AbstractQueue class that will come handy (as name indicates its an abstract class).Queue Sub-interface:
There are four interface which extends Queue. These are:
- BlockingQueue - Provide additional feature of thread blocked (go to wait state) while fetching from empty queue and while trying to insert element when the queue is full.
- BlockingDeque - Provide additional feature of thread blocked (go to wait state) while fetching from empty queue and while trying to insert element when the deque is full.
- Deque - Deque is double ended queue, which means the insertion and deletion of element is allowed from both end.
- TransferQueue - The thread inserting element to TransferQueue may wait for any consuming thread to retreive the element. Useful in message passing applications.
Implementation in Java:
There are already ready-to-use Queue (Java Classes) provided in Java library. These are:- LinkedList - Similar to Double Linked list i.e. each element has reference to previous and next element. That is why it is preferred over ArrayList when the insertion and deletion operation is more than just reading the list. This is an important interview question on collection framework for fresher as the main difference between ArrayList and LinkedList.
- PriorityQueue - Inserted elements are ordered as per natural ordering or as per comparator provided. This means in PriorityQueue, the elements is not required to follow FIFO model as there can be comparator which can insert element based on comparator result in between the queue itself.
- ArrayBlockingQueue - A bounded blocking queue. Consider ArrayBlockingQueue as a fixed size array acting on FIFO model with additional feature of thread gets blocked when queue is full / empty.
- LinkedBlockingQueue - An optionally bounded blocking queue (Blocking queue feature can be applicable only to bounded collections). Consider LinkedBlockingQueue as Linkedlist following FIFO model with its size can be limited (bounded) or unlimited (Integer.MAX_VALUE). Threads cannot be blocked in unbounded LinkedBlockingQueue during insertion, so blockingqueue feature will not be fully applicable to unbounded LinkedBlockingQueue (only in case of retrieval).
- PriorityBlockingQueue - An unbounded Priority Queue with feature of Blocking Queue is limited to the retreival of its element (as this queue is unbounded).
- ConcurrentLinkedQueue - An unbounded LinkedBlockingQueue with thread-safety features. This means multiple threads can insert / delete / retreive elements on ConcurrentLinkedQueue parallely. Since it is unbounded, blocking queue feature is limited to the retreival of element only (i.e. thread attempting to retreive element from empty queue will get blocked only waiting till the insertion of element).
- ConcurrentLinkedDeque - An unbounded thread safe "double ended queue" based on linked nodes.
- ArrayDeque - A deque with resizeable array. Since it has array implementation, its performance is better than Stack and Linkedlist. However it is not thread-safe.
- DelayQueue - An unbounded Blocking queue (no limit on size) to which an element can only be retreived after its delay has expired.
- LinkedBlockingDeque - An optionally bounded blocking "double ended queue". If size is specified when creating LinkedBlockingDeque object it will belcome bounded otherwise unbounded. Thread will get blocked in LinkedBlockingDeque while retreiving an empty queue and will get blocked while adding an element to full bounded LinkedBlockingDeque. It is based on linked nodes.
- LinkedTransferQueue - An unbounded TransferQueue based on linked nodes. The size method is not a constant time operation and may vary.
- SynchronousQueue - It works by putting the insert operation thread to wait for remove operation by another thread. In other words, the thread inserting element to Synchronous Queue gets blocked till another thread takes the element out and vice-versa.
Queue Behaviour / Usage :
Queue provides additional way to insert, delete and examine object. For each insert, delete and examine operation, there are corresponding 2 methods, one throws exception and other return special value in case of failure.Besides this, any Queue will also have all the properties of Collection as Queue interface extends Collection interface
Methods of Queue Interface:
As discussed above, the queue provides 2 methods for each insert, delete and examine operation.These are:
Insert Operation:
add(e) -> returns true when success and throws exception in case of failure.offer(e) -> returns true when success and false in case of failure.
Remove Operation:
remove() -> removes the head element. Returns head element when success and throws exception in case of failure.poll() -> removes the head element. Returns head element when success and returns null in case of failure.
Examine Operation:
element() -> retrieves (but do not remove) the head element. Returns element when true and throws NoSuchElementException in case of failure (i.e. when the queue is empty).peak() -> retrieves (but do not remove) the head element. Returns element when true and null in case of failure (i.e. when the queue is empty)
Code Example:
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main (String[] args) {
Queue que = new LinkedList();
que.add("first");
que.offer("second");
que.offer("third");
System.out.println("Queue Print:: " + que);
String head = que.element();
System.out.println("Head element:: " + head);
String element1 = que.poll();
System.out.println("Removed Element:: " + element1);
System.out.println("Queue Print after poll:: " + que);
String element2 = que.remove();
System.out.println("Removed Element:: " + element2);
System.out.println("Queue Print after remove:: " + que);
}
}
Output:
Queue Print:: [first, second, third]
Head element:: first
Removed Element:: first
Queue Print after poll:: [second, third]
Removed Element:: second
Queue Print after remove:: [third]
?