Data Structures in Java — Queue

We’ve seen about Data Structures and Arrays already. In this article, let’s see about a new Data Structure called Queue.

Have you heard about the Queue, in real life? What do you know about it?

Queue is a line or sequence of people or vehicles awaiting their turn to be attended to or to proceed.

Look at this queue.

A queue

There are a number of people waiting for a service. You have seen a queue or the most probably been in the queue. What is the significant scenario you have seen there? Ignore the scenarios where people use influences to get the services by breaking the queue, WE DON’T DO THAT HERE.

A proper queue always performs First Come First Serve (FCFS) policy (or FIFO- First In, First Out).

Look at this queue.

A queue

What is/are the difference(s) between the two pictures above? Both of them are describing a queue structure, of course yes. A queue! But wait a minute, are you confident that you’ve no concerns? In the 2nd queue, you can see there are two people together (4th position from your left). That means, a same location in a queue is being shared by 2 people. In other words, two people share equal chances of getting a service which is TOTALLY UNACCEPTABLE IN THE QUEUE IN DATA STRUCTURES.

So I hope now you understood the mechanism of the queue in Computer Science. Lets go deeper into this.

So now, lets think about the very basic operations associated with a queue, means, lets see what are the functions we have to do to utilize this data structure.

From the understanding of the mechanism of a queue, we know that we can have a limited number of people at a queue for a service (ignore the bad use of queue). Let’s see how the Queue Data Structure works in Computer Science.

Before the implementation of Queue, lets see the operations performed in it. Generally speaking, to a queue of customers, what operations can be done?

1. A new customer can join the queue (At the rear part of the queue). To do this we have to check the queue whether it has space for a new queue member or not.
2. The person in front can be served, simply can exit the queue. To do this, we have to check the queue whether it has customer or not (an empty queue can’t be served).
3. We can check who is next (in front) and who is the last (at rear) to be served.

Similarly, we can implement all of these to the Queue Data Structure too. Lets’s see how can we implement these in Java.

First we have to define as class that represents the Queue. We know what are the functionalities that a Queue must have, so, we have to include them in our Queue class.

First, we have to define the important aspects/ the instance variables of the Queue Class.

int front, rear, size; 
int capacity; 
int array[];

We have to define the constructor for the Queue Class like this.

public Queue(int capacity) 
{ 
        this.capacity = capacity; 
        front = this.size = 0; 
        rear = capacity - 1; 
        array = new int[this.capacity]; 
}

Now we have to write the methods for this class. We’ve already seen what are the expected functionalities that this Class has to do.

To check whether the Queue has space to add a new Queue member, we’ve to check whether the size of the Queue is equal to the Queue capacity or not. The method can be written as;

boolean isFull(Queue queue) 
{ 
        return (queue.size == queue.capacity); 
}

This will return true if the Queue is full and false if the Queue is not full.

To check whether the Queue has a member to be served. To check this, we have to check the size of the Queue. If it is 0, then the Queue has no members. The method can be written as;

boolean isEmpty(Queue queue) 
{ 
        return (queue.size == 0); 
}

This will return true if the Queue is empty and false if the Queue is not empty.

How to add a new member to the Queue? Well, it has to be done at the rear side of the Queue and the method shall be implemented like this.

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"); 
}

First, it checks whether the Queue is full or not and if it full, the insertion won‘t be happen. Then it updates the rear, Queue (array) and the size. For better user interaction we can have an optional print option to show which element has been added to the Queue.

Similarly, to serve a member (to remove a member at front) the method can be written like this.

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; 
}

We have to look what is next to be served and last to be served. This can be easily accessed using the following methods.

int front() 
{ 
        if (isEmpty(this)) 
            return Integer.MIN_VALUE; 
  
        return this.array[this.front]; 
} 
  
int rear() 
{ 
        if (isEmpty(this)) 
            return Integer.MIN_VALUE; 
  
        return this.array[this.rear]; 
}

In both cases we are checking whether the Queue is empty of not because, if it is empty, we can’t look into the 1st and the last member of the Queue.

Well, we’ve created a Queue class and now we have to write a Driver Class to use this Queue Class.

Queue queue = new Queue(10);
queue.enqueue(10); 
queue.enqueue(20); 
queue.enqueue(30); 
queue.enqueue(40); 
  
System.out.println(queue.dequeue() + " dequeued from queue"); 
  
System.out.println("Front item is " + queue.front()); 
  
System.out.println("Rear item is " + queue.rear());

Queue is being used in many places due to its FCFS feature.

1. Waiting lists for a single shared resources (printer, disk, CPU).
2. Buffers in most of the applications (MP3 media player, CD player, etc.).
3. Operating systems for handling interrupts.

Circular Queues are used in some cases where the queue has a large number of enqueue and dequeue operations. Because at some point we may not we able to insert elements in the queue even if the queue is empty.

Start practicing implementing this easiest Data Structure and have fun with programming.