The Queue Interface

  • A Queue is a collection for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, removal, and inspection operations.


  • Each Queue method exists in two forms: (1) one throws an exception if the operation fails, and (2) the other returns a special value if the operation fails (either null or false, depending on the operation).


  • The regular structure of the interface is illustrated in the following table.


  • Queue Interface Structure
    Type of Operation Throws exception Returns special value
    Insert add(e) offer(e)
    Remove remove() poll()
    Examine element() peek()


  • Queues typically, but not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to their values).


  • Whatever ordering is used, the head of the queue is the element that would be removed by a call to remove or poll.


  • In a FIFO queue, all new elements are inserted at the tail of the queue.


  • Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties.


  • It is possible for a Queue implementation to restrict the number of elements that it holds; such queues are known as bounded. Some Queue implementations in java.util.concurrent are bounded, but the implementations in java.util are not.


  • The add method, which Queue inherits from Collection, inserts an element unless it would violate the queue's capacity restrictions, in which case it throws IllegalStateException.


  • The offer method, which is intended solely for use on bounded queues, differs from add only in that it indicates failure to insert an element by returning false.


  • The remove and poll methods both remove and return the head of the queue.


  • Exactly which element gets removed is a function of the queue's ordering policy.


  • The remove and poll methods differ in their behavior only when the queue is empty. Under these circumstances, remove throws NoSuchElementException, while poll returns null.


  • The element and peek methods return, but do not remove, the head of the queue. They differ from one another in precisely the same fashion as remove and poll: If the queue is empty, element throws NoSuchElementException, while peek returns null.


  • Queue implementations generally do not allow insertion of null elements. The LinkedList implementation, which was retrofitted to implement Queue, is an exception.


  • For historical reasons, it permits null elements, but you should refrain from taking advantage of this, because null is used as a special return value by the poll and peek methods.


  • Queue implementations generally do not define element-based versions of the equals and hashCode methods but instead inherit the identity-based versions from Object. 


    •  
import java.util.LinkedList; 
import java.util.Queue; 
  
public class QueueExample 
{ 
  public static void main(String[] args) 
  { 
    Queue q = new LinkedList<>(); 
  
  
    for (int i=0; i<5; i++) 
     q.add(i); 
  
 
    System.out.println("Elements of queue-"+q); 
  
  
    int removedele = q.remove(); 
    System.out.println("removed element-" + removedele); 
  
    System.out.println(q); 
  
  
    int head = q.peek(); 
    System.out.println("head of queue-" + head); 
  
   
    int size = q.size(); 
    System.out.println("Size of queue-" + size); 
  } 
} 


Output:
Elements of queue-[0, 1, 2, 3, 4]
removed element-0
[1, 2, 3, 4]
head of queue-1
Size of queue-4


     
import java.util.LinkedList; 
import java.util.Queue; 
  
public class QueueExample 
{ 
  public static void main(String[] args) 
  { 
    Queue q = new LinkedList<>(); 
  
    // Adds elements {0, 1, 2, 3, 4} to queue 
    for (int i=0; i<5; i++) 
     q.add(i); 
  
    int queue_poll = q.poll(); 
    System.out.println("Polling queue-" + queue_poll); 
    
  } 
} 

Output:
Polling queue-0

The Deque Interface

  • Usually pronounced as deck, a deque is a double-ended-queue. A double-ended-queue is a linear collection of elements that supports the insertion and removal of elements at both end points.


  • The Deque interface is a richer abstract data type than both Stack and Queue because it implements both stacks and queues at the same time.


  • The Deque interface, defines methods to access the elements at both ends of the Deque instance.


  • Methods are provided to insert, remove, and examine the elements. Predefined classes like ArrayDeque and LinkedList implement the Deque interface.


  • Note that the Deque interface can be used both as last-in-first-out stacks and first-in-first-out queues. The methods given in the Deque interface are divided into three parts:


  • Insert The addfirst and offerFirst methods insert elements at the beginning of the Deque instance. The methods addLast and offerLast insert elements at the end of the Deque instance. When the capacity of the Deque instance is restricted, the preferred methods are offerFirst and offerLast because addFirst might fail to throw an exception if it is full.


  • Remove The removeFirst and pollFirst methods remove elements from the beginning of the Deque instance. The removeLast and pollLast methods remove elements from the end. The methods pollFirst and pollLast return null if the Deque is empty whereas the methods removeFirst and removeLast throw an exception if the Deque instance is empty.


  • Retrieve The methods getFirst and peekFirst retrieve the first element of the Deque instance. These methods dont remove the value from the Deque instance.


  • Similarly, the methods getLast and peekLast retrieve the last element. The methods getFirst and getLast throw an exception if the deque instance is empty whereas the methods peekFirst and peekLast return NULL.


    • Deque Methods
    Type of Operation First Element (Beginning of the Deque instance) Last Element (End of the Deque instance)
    Insert addFirst(e)
    offerFirst(e)    		 addLast(e)
    offerLast(e)
    Remove removeFirst()
    pollFirst()    		 removeLast()
    pollLast()
    Examine getFirst()
    peekFirst()    		 getLast()
    peekLast()

  • In addition to these basic methods to insert,remove and examine a Deque instance, the Deque interface also has some more predefined methods.


  • One of these is removeFirstOccurence, this method removes the first occurence of the specified element if it exists in the Deque instance.


  • If the element does not exist then the Deque instance remains unchanged. Another similar method is removeLastOccurence; this method removes the last occurence of the specified element in the Deque instance.


  • The return type of these methods is boolean, and they return true if the element exists in the Deque instance. 


    •  
import java.util.*;
  
public class Sample 
{ 
  public static void main(String[] args) 
  { 
    Deque dq = new LinkedList<>(); 
  
    // Adds elements {0, 1, 2, 3, 4} to queue 
    for (int i=0; i<5; i++) 
     dq.add(i); 
  
    System.out.println("See deque elements "+dq);
    
    dq.addFirst(500);
    System.out.println("See first - " + dq.getFirst()); 
  
    System.out.println("Add first using offer - " + dq.offerFirst(123)); 
    System.out.println("See first - " + dq.getFirst()); 
    
    dq.addLast(456);
    System.out.println("See Last - " + dq.getLast()); 
   
    System.out.println("Add Last using offer - " + dq.offerLast(789)); 
    System.out.println("See Last - " + dq.getLast()); 
    
  } 
}

Output
See deque elements [0, 1, 2, 3, 4]
See first - 500
Add first using offer - true
See first - 123
See Last - 456
Add Last using offer - true
See Last - 789