Queues

Queue is a linear data structure which follows a particular order in which operations are performed. The order is First In First Out(FIFO). The literal meaning of queue is a waiting line.

A good example of queue is any queue of consumers for a resource where the consumer that came first is served first. Suppose you went to McDonalds and want to have a burger, so whoever came first is served first. It is very close to the real life queue.

The difference between stacks and queues is in removing. In a stack we remove the item the mostly added; in a queue, we remove the item the least recently added.

Operations on the queue

  • Enqueue- Adds an element to the queue and if the queue is full, then it is said to be an Overflow condition.
  • Dequeue- Removes an element from the queue. The items are removed in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
  • Front- Get the front item from the queue.
  • Rear- Get the last element from the queue.
queue-java-data-structures

So, the first element O1 enters from the rear end. Subsequently, all the elements enter from the rear end. Now, if we want the an element to be removed then it is done from the head of the queue. So, if we call remove, then O1 will be removed first.

In queue, we operate on the first element that is added but in stack we operate on the last element that is added.

Properties and Applications of Queue

Properties of Queues:

  • Queues allow duplicate elements to be entered in the collection.
  • Queues donot allow null elements to be entered.
  • Queue supports all methods of Collection interface.
  • All Dequeues are not thread-safe.

Applications of Queues::

Queue is used when things have to be processed in First In First Out Order(FIFO) which is useful in following scenarios.

  • When a resource is shared among multiple consumers like Disk Scheduling, CPU scheduling, etc.
  • When data is transferred asynchronously between two processes like IO Buffers, pipes, file IO, etc.

Methods Queue

In queue, we have two methods to perform one task like

  • Insert: add() and offer()
  • Retrieve: element() and peek()
  • Remove: remove() and poll()

Now, why do we have two methods to do one task? Meaning, why do have add() and offer() to perform an insert operation on a queue?

This is because if any error occurs, then the first method, i.e, add() will throw an exception. Whereas, the second method will return a special value instead of throwing an exception that will tell you whether the operation that you wanted to perform was successful or not.

Queue add() operation:


import java.util.concurrent.*;
public class QueueAddOperation {
   public static void main(String[] args) {
	BlockingQueue<String> queue = new ArrayBlockingQueue<>(2);

	System.out.println(queue.add("one"));
	System.out.println(queue.add("two"));
	System.out.println(queue);
	System.out.println(queue.add("three"));
	System.out.println(queue);
   }
}					

Output:


true
true
[one, two]
Exception in thread "main" java.lang.IllegalStateException: Queue full


import java.util.concurrent.*;
public class QueueOfferOperation {
   public static void main(String[] args) {		
	BlockingQueue<String> queue = new ArrayBlockingQueue<>(2);
	System.out.println(queue.offer("one"));
	System.out.println(queue.offer("two"));
	System.out.println(queue);
	System.out.println(queue.offer("three"));
	System.out.println(queue);
   }
}

Output:


true
true
[one, two]
false
[one, two]					

Queue remove() operation:


import java.util.*;
public class QueueRemoveOperation 
{
   public static void main(String[] args) 
   {		
	Queue<String> queue = new LinkedList<>();
	queue.offer("one");
	queue.offer("two");		
	System.out.println(queue);		
	System.out.println(queue.remove());
	System.out.println(queue.remove());		
	System.out.println(queue.remove());		
   }
}

Output:


[one, two]
one
two
Exception in thread "main" java.util.NoSuchElementException

Example of basic operations:


import java.util.*;
public class QueueExample {
   public static void main(String[] args) {	
	Queue<String> queue = new LinkedList<>();
	queue.add("one");
	queue.add("two");
	queue.add("three");
	queue.add("four");
	System.out.println(queue);
	queue.remove("three");
	System.out.println(queue);
	System.out.println("Queue Size: " + queue.size());
	System.out.println("Queue Contains element 'two' or not? : " + queue.contains("two"));
	// To empty the queue
	queue.clear();
   }
}

Output:


[one, two, three, four]
[one, two, four]
Queue Size: 3
Queue Contains element 'two' or not? : true

Array implementation of the queue:

For implementation of queue, we need to keep track of front and rear indices. We enqueue an element at the rear and dequeue an item from front. If we simply increment front and rear indices, then the front may reach end of the array. So, the solution is to increase front and rear in circular manner. Java Array To Queue


import java.util.*;
public class ArrayToQueue {
    public static void main(String[] args) {	
	String nums[] = {"one","two","three","four","five"};
	Queue<String> queue = new LinkedList<>();
	Collections.addAll(queue, nums);
	System.out.println(queue);
   }
}


Output:
[one, two, three, four, five]
						

Array implementation of the queue


// A class to represent a queue 
class Queue 
{ 
    int front, rear, size; 
    int  capacity; 
    int array[]; 
       
    public Queue(int capacity) { 
         this.capacity = capacity; 
         front = this.size = 0;  
         rear = capacity - 1; 
         array = new int[this.capacity]; 
            
    } 
       
    // Queue is full when size becomes equal to  
    // the capacity  
    boolean isFull(Queue queue) 
    {  return (queue.size == queue.capacity); 
    } 
       
    // Queue is empty when size is 0 
    boolean isEmpty(Queue queue) 
    {  return (queue.size == 0); } 
       
    // Method to add an item to the queue.  
    // It changes rear and size 
    void enqueue( int item) 
    { 
        if (isFull(this)) 
            return; 
        this.rear = (this.rear + 1)%this.capacity; 
        this.array[this.rear] = item; 
        this.size = this.size + 1; 
        System.out.println(item+ " enqueued to queue"); 
    } 
       
    // Method to remove an item from queue.   
    // It changes front and size 
    int dequeue() 
    { 
        if (isEmpty(this)) 
            return Integer.MIN_VALUE; 
           
        int item = this.array[this.front]; 
        this.front = (this.front + 1)%this.capacity; 
        this.size = this.size - 1; 
        return item; 
    } 
       
    // Method to get front of queue 
    int front() 
    { 
        if (isEmpty(this)) 
            return Integer.MIN_VALUE; 
           
        return this.array[this.front]; 
    } 
        
    // Method to get rear of queue 
    int rear() 
    { 
        if (isEmpty(this)) 
            return Integer.MIN_VALUE; 
           
        return this.array[this.rear]; 
    } 
} 
   
    
// Driver class 
public class Test 
{ 
    public static void main(String[] args)  
    { 
        Queue queue = new Queue(1000); 
            
        queue.enqueue(1); 
        queue.enqueue(2); 
        queue.enqueue(3); 
        queue.enqueue(4); 
        
        System.out.println(queue.dequeue() +  " dequeued from queue\n"); 
        System.out.println("Front item is " + queue.front()); 
        System.out.println("Rear item is " +  queue.rear()); 
    } 
} 

Output:


1 enqueued to queue
2 enqueued to queue
3 enqueued to queue
4 enqueued to queue
1 dequeued from queue
Front item is 2
Rear item is 4

Time Complexity: There is no loop in any of the operations. So, the time complexity of all operations like enqueue(), dequeue(), isFull(), isEmpty(), front(), rear() is O(1).

Linked List implementation of the queue:

In queue, front and rear are the two pointers that we maintain. The front points the first item of queue and rear points to last item.

  • enQueue(): It adds a new node after rear and moves rear to the next node.
  • deQueue(): It removes the front node and moves front to the next node.
Example:

// A linked list (LL) node to store a queue entry 
class QNode 
{ 
    int key; 
    QNode next; 
    // constructor to create a new linked list node 
    public QNode(int key) { 
        this.key = key; 
        this.next = null; 
    } 
} 
  
// A class to represent a queue 
//The queue, front stores the front node of LL and rear stores ths 
//last node of LL 
class Queue 
{ 
    QNode front, rear; 
    public Queue() { 
        this.front = this.rear = null; 
    }      
    // Method to add an key to the queue.   
    void enqueue(int key) 
    {     
        // Create a new LL node 
        QNode temp = new QNode(key); 
       
        // If queue is empty, then new node is front and rear both 
        if (this.rear == null) 
        { 
           this.front = this.rear = temp; 
           return; 
        }    
        // Add the new node at the end of queue and change rear 
        this.rear.next = temp; 
        this.rear = temp; 
    } 
    // Method to remove an key from queue.   
    QNode dequeue() 
    { 
        // If queue is empty, return NULL. 
        if (this.front == null) 
           return null; 
       
        // Store previous front and move front one node ahead 
        QNode temp = this.front; 
        this.front = this.front.next; 
       
        // If front becomes NULL, then change rear also as NULL 
        if (this.front == null) 
           this.rear = null; 
        return temp; 
    } 
} 
// Driver class 
public class Test 
{ 
    public static void main(String[] args)  
    { 
        Queue q = new Queue(); 
        q.enqueue(10); 
        q.enqueue(20); 
        q.dequeue(); 
        q.dequeue(); 
        q.enqueue(30); 
        q.enqueue(40); 
        q.enqueue(50); 
        System.out.println("Dequeued item is "+ q.dequeue().key);
	}
}					

Output:


Dequed item is 30			

Time Complexity: There is no loop in any of the operations. The time complexity of both operations enqueue() and dequeue() is O(1) as we only changed few pointers in both the operations.

Circular Queue

Circular queue also known as Ring Buffer, is a linear data structure in which operations are performed based on First In First Out(FIFO) principle. The last position is connected back to the first position to form a circle. circular-queue-java-data-structures In normal queue, we can not insert the next element once queue becomes full even if there is a space in front of the queue.

Operations on circular queue:

  • Front: Get the front element from queue.
  • Rear: Get the last element from queue.
  • enQueue(value): Inserts an element into the circular queue. In a circular queue, the new element is always inserted at rear position. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)). If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear = 0 and insert element.
  • deQueue(): Deletes an element from the circular queue. The element is always deleted from the from position. Check whether queue is Empty means check (front==-1). If queue is not empty, check if(front==rear), if it is true then set front=rear=-1, else check if(front==size-1), if it is true then set front=0 and return the element.
Example:

import java.util.Arrays;

public class CircularQueueImplementation {

    public static void main(String[] args) {

        CircularQueue<Integer> circularQueue = new CircularQueue(8);

        circularQueue.enqueue(15);
        circularQueue.enqueue(16);
        circularQueue.enqueue(17);
        circularQueue.enqueue(18);
        circularQueue.enqueue(19);
        circularQueue.enqueue(20);
        circularQueue.enqueue(21);
        circularQueue.enqueue(22);

        System.out.println("Full Circular Queue" + circularQueue);

        System.out.print("Dequeued following element from circular Queue ");
        System.out.println(circularQueue.dequeue() + " ");
        circularQueue.enqueue(23);
        System.out.println("After enqueueing circular queue with element having value 23");
        System.out.println(circularQueue);
    }

}

//implementation of Circular Queue using Generics
class CircularQueue<E> {

    private int currentSize; //Current Circular Queue Size
    private E[] circularQueueElements;
    private int maxSize; //Circular Queue maximum size

    private int rear;//rear position of Circular queue(new element enqueued at rear).
    private int front; //front position of Circular queue(element will be dequeued from front).      

    public CircularQueue(int maxSize) {
        this.maxSize = maxSize;
        circularQueueElements = (E[]) new Object[this.maxSize];
        currentSize = 0;
        front = -1;
        rear = -1;
    }

    /**
     * Enqueue elements to rear.
     */
    public void enqueue(E item) throws QueueFullException {
        if (isFull()) {
            throw new QueueFullException("Circular Queue is full.
			Element cannot be added");
        }
        else {
            rear = (rear + 1) % circularQueueElements.length;
            circularQueueElements[rear] = item;
            currentSize++;
            
            if (front == -1) {
				front = rear;
			}
        }
    }

    /**
     * Dequeue element from Front.
     */
    public E dequeue() throws QueueEmptyException {
        E deQueuedElement;
        if (isEmpty()) {
            throw new QueueEmptyException("Circular Queue is empty. Element cannot be retrieved");
        }
        else {
            deQueuedElement = circularQueueElements[front];
            circularQueueElements[front] = null;
            front = (front + 1) % circularQueueElements.length;
            currentSize--;
        }
        return deQueuedElement;
    }

    /**
     * Check if queue is full.
     */
    public boolean isFull() {
        return (currentSize == circularQueueElements.length);
    }

    /**
     * Check if Queue is empty.
     */
    public boolean isEmpty() {
        return (currentSize == 0);
    }

    @Override
    public String toString() {
        return "CircularQueue [" + Arrays.toString(circularQueueElements) + "]";
    }

}

class QueueFullException extends RuntimeException {

    private static final long serialVersionUID = 1L;

    public QueueFullException() {
        super();
    }

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

}

class QueueEmptyException extends RuntimeException {

    private static final long serialVersionUID = 1L;

    public QueueEmptyException() {
        super();
    }

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

}						

Output:


Full Circular QueueCircularQueue [[15, 16, 17, 18, 19, 20, 21, 22]]
Dequeued following element from circular Queue 15 
After enqueueing circular queue with element having value 23
CircularQueue [[23, 16, 17, 18, 19, 20, 21, 22]]

Time Complexity: There is no loop in any of the operation. So, the Time complexity of enQueue(), deQueue() operation is O(1).

About Author

Myself KarthiQ, I am the author of this blog, I know ways to write a good article but some how I donot have the skills to make it to reach people, would you like help me to reach more people By sharing this Article in the social media.

Share this Article Facebook
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group