Queue

Queue 

The queue is also an abstract data type or a linear data structure, just like stack data structure. The queue implements FIFO i.e. First In First Out. This means that the elements entered first are the ones that are deleted first. 

Applications of Queue 

• Serving requests on a single shared resource, like a printer, CPU task scheduling, etc.

• In real life scenario, Call Center phone systems use Queues to hold people calling them in order, until a service representative is free.

• Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e. First come first served.

• A single-lane one-way road, where the vehicle enters first, exits first. 

• Queues at the ticket windows and bus stops.

• CPU task scheduling.

Queue Implementation in Java

In Java, Queue is an interface that is a part of java.util package. The queue interface extends the Java Collection interface. 

public interface Queue<E> extends Collection<E>

As the Queue is an interface, it cannot be instantiated. We need some concrete classes to implement the functionality of the Queue interface. Two classes implement the Queue interface i.e. LinkedList and PriorityQueue. 

Queue Methods

• add - Adds element e to the queue at the end (tail) of the queue without violating the restrictions on the capacity. Returns true if success or IllegalStateException if the capacity is exhausted.

• peek - Returns the head (front) of the queue without removing it.

• element - Performs the same operation as the peek () method. Throws NoSuchElementException when the queue is empty.

• remove - Removes the head of the queue and returns it. Throws NoSuchElementException if the queue is empty.

• poll - Removes the head of the queue and returns it. If the queue is empty, it returns null.

• Offer - Insert the new element e into the queue without violating capacity restrictions.

• size - Returns the size or number of elements in the queue.

To use a queue in Java, we must first import the queue interface as follows:

import java.util.queue;

Example: QueueExample

import java.util.LinkedList;

import java.util.Queue;

public class QueueExample {

   public static void main(String[] args) {

    //declare a Queue   

    Queue<String> str_queue = new LinkedList<>();

    //initialize the queue with values

    str_queue.add("one");

    str_queue.add("two");

    str_queue.add("three");

    str_queue.add("four");

    //print the Queue

    System.out.println("The Queue contents:" + str_queue);

    }

}

The output will be:

The Queue contents:[one, two, three, four]

Traversing Queue

We can traverse the queue elements either using the for loop or using an iterator.  

Example: TraverseQueue

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Queue;

public class TraverseQueue{

  public static void main(String[] args) {

    //declare a Queue  

  Queue<String> LL_queue = new LinkedList<>();

    //initialize the Queue

    LL_queue.add("One");

    LL_queue.add("Two");

    LL_queue.add("Three");

    LL_queue.add("Four");

    //traverse the Queue using Iterator

    System.out.println("The Queue elements through iterator:");

    Iterator iterator = LL_queue.iterator();

    while(iterator.hasNext()){

        String element = (String) iterator.next();

        System.out.print(element + " ");

    }

    //use new for loop to traverse the Queue

    System.out.println("\n\nThe Queue elements using for loop:");

    for(Object object : LL_queue) {

        String element = (String) object;

        System.out.print(element + " ");

    }

}

}

The output will be:

The Queue elements through iterator:

One Two Three Four 

The Queue elements using for loop:

One Two Three Four 

Example: QueueExample2

The following program demonstrate some of the methods in Queue.

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Queue;

public class QueueExample2 {

    public static void main(String[] args) {

        Queue<Integer> q1 = new LinkedList<Integer>();

        //Add elements to the Queue

        q1.add(10);

        q1.add(20);

        q1.add(30);

        q1.add(40);

        q1.add(50);

        System.out.println("Elements in Queue:"+q1);

        //remove () method =>removes first element from the queue

        System.out.println("Element removed from the queue: "+q1.remove());

        //element() => returns head of the queue

        System.out.println("Head of the queue: "+q1.element());

        //poll () => removes and returns the head

        System.out.println("Poll():Returned Head of the queue: "+q1.poll());

        //returns head of the queue

        System.out.println("peek():Head of the queue: "+q1.peek());

        //print the contents of the Queue

        System.out.println("Final Queue:"+q1);

    }

}

The output will be:

Elements in Queue:[10, 20, 30, 40, 50]

Element removed from the queue: 10

Head of the queue: 20

Poll():Returned Head of the queue: 20

peek():Head of the queue: 30

Final Queue:[30, 40, 50]

Queue Implementation Using Arrays

To implement queue using Arrays, we first declare an array that will hold n number of queue elements. 

The operations in Queue are:

#1) Enqueue: An operation to insert an element in the queue is Enqueue (function queueEnqueue in the program). For inserting an element at the rear end, we need to first check if the queue is full. If it is full, then we cannot insert the element. If rear < n, then we insert the element in the queue.

#2) Dequeue: The operation to delete an element from the queue is Dequeue (function queueDequeue in the program). First, we check whether the queue is empty. For dequeue operation to work, there has to be at least one element in the queue.

#3) Front: This method returns the front of the queue.

#4) Display: This method traverses the queue and displays the elements of the queue.

Example: QueueArray

The following program shows how to implement queue using arrays.

class Queue { 

    private static int front, rear, capacity; 

    private static int queue[]; 

    Queue(int size) { 

        front = rear = 0; 

        capacity = size; 

        queue = new int[capacity]; 

    } 

    // insert an element into the queue

    static void queueEnqueue(int item)  { 

        // check if the queue is full

        if (capacity == rear) { 

            System.out.printf("\nQueue is full\n"); 

            return; 

        } 

        // insert element at the rear 

        else { 

            queue[rear] = item; 

            rear++; 

        } 

        return; 

    } 

    //remove an element from the queue

    static void queueDequeue()  { 

        // check if queue is empty 

        if (front == rear) { 

            System.out.printf("\nQueue is empty\n"); 

            return; 

        } 

        // shift elements to the right by one place uptil rear 

        else { 

            for (int i = 0; i < rear - 1; i++) { 

                queue[i] = queue[i + 1]; 

            } 

       // set queue[rear] to 0

            if (rear < capacity) 

                queue[rear] = 0; 

            // decrement rear 

            rear--; 

        } 

        return; 

    } 

    // print queue elements 

    static void queueDisplay() 

    { 

        int i; 

        if (front == rear) { 

            System.out.printf("Queue is Empty\n"); 

            return; 

        } 

        // traverse front to rear and print elements 

        for (i = front; i < rear; i++) { 

            System.out.printf(" %d = ", queue[i]); 

        } 

        return; 

    } 

    // print front of queue 

    static void queueFront() { 

        if (front == rear) { 

            System.out.printf("Queue is Empty\n"); 

            return; 

        } 

        System.out.printf("\nFront Element of the queue: %d", queue[front]); 

        return; 

    } 

} 

public class QueueArray {

    public static void main(String[] args) { 

        // Create a queue of capacity 4 

        Queue q = new Queue(4); 

        System.out.println("Initial Queue:");

       // print Queue elements 

        q.queueDisplay(); 

        // inserting elements in the queue 

        q.queueEnqueue(10); 

        q.queueEnqueue(30); 

        q.queueEnqueue(50); 

        q.queueEnqueue(70); 

        // print Queue elements 

        System.out.println("Queue after Enqueue Operation:");

        q.queueDisplay(); 

        // print front of the queue 

        q.queueFront(); 

        // insert element in the queue 

        q.queueEnqueue(90); 

        // print Queue elements 

        q.queueDisplay(); 

        q.queueDequeue(); 

        q.queueDequeue(); 

        System.out.printf("\nQueue after two dequeue operations:"); 

        // print Queue elements 

        q.queueDisplay(); 

        // print front of the queue 

        q.queueFront(); 

    } 

}

The output will be:

Initial Queue:

Queue is Empty

Queue after Enqueue Operation:

 10 =  30 =  50 =  70 = 

Front Element of the queue: 10

Queue is full

 10 =  30 =  50 =  70 = 

Queue after two dequeue operations: 50 =  70 = 

Front Element of the queue: 50

Queue Implementation Using Linked List

Example:

LinkedListQueue.java

class LinkedListQueue {

private Node front, rear; 

private int queueSize; // queue size 

  //linked list node

  private class Node { 

  int data;

  Node next;

  }

  //default constructor- initially front & rear are null; size=0; queue is empty

  public LinkedListQueue(){

  front = null;

  rear = null;

  queueSize = 0;

  }

  //check if the queue is empty

  public boolean isEmpty(){

  return (queueSize == 0);

  }

  //Remove item from the front of the queue.

  public int dequeue(){

  int data = front.data;

  front = front.next;

  if (isEmpty()) {

  rear = null;

  }

  queueSize--;

  System.out.println("Element " + data+ " removed from the queue");

  return data;

  }

  //Add data at the rear of the queue.

  public void enqueue(int data){

  Node oldRear = rear;

  rear = new Node();

  rear.data = data;

  rear.next = null;

  if (isEmpty()) {

  front = rear;

  }

  else  {

  oldRear.next = rear;

  }

  queueSize++;

  System.out.println("Element " + data+ " added to the queue");

  }

  //print front and rear of the queue

  public void print_frontRear() {

  System.out.println("Front of the queue:" + front.data 

  + " Rear of the queue:" + rear.data);

  }

}

QueueExample3.java

public class QueueExample3{

public static void main(String a[]){

LinkedListQueue queue = new LinkedListQueue();

queue.enqueue(6);

queue.enqueue(3);

queue.print_frontRear();

queue.enqueue(12);

queue.enqueue(24);

queue.dequeue();

queue.dequeue();

queue.enqueue(9);

queue.print_frontRear();

}

}

The output will be:

Element 6 added to the queue

Element 3 added to the queue

Front of the queue:6 Rear of the queue:3

Element 12 added to the queue

Element 24 added to the queue

Element 6 removed from the queue

Element 3 removed from the queue

Element 9 added to the queue

Front of the queue:12 Rear of the queue:9

Example: Stack & Queue

Given the following algorithm:

1.     For each test case, read a line of input and do the following:

a.      if it is a letter, push onto a stack

b.     if it is an asterisk

if there is item in the stack

pop, then enqueue to a queue

2.     Output content of the stack and queue as shown in the sample output