Queue is a data structure which works on FIFO (First In, First Out) policy, i.e., whichever element goes in first will come out first from the queue. It is similar to people standing in queue for check in at airport.
Inserting an element in the queue is called as enqueue whereas taking out an element is called as dequeue.
Let’s create our own queue and implement its operations. We will use an array to mimic a queue. We will create a circular queue where elements will “go around” the array to the beginning. This construct will consist of two variables
- head – Points to the element which is at the beginning of the queue. This is moved to the next element in the queue when dequeue operation is performed. Consider it as the start of the queue.
- tail – Points to the next available space/slot in the queue. An element is stored at this place in enqueue operation. It moves forward when the element is inserted. Consider it as the end of the queue.
Note that when the head and tail are pointing to the same slot in the array, it means that the queue is empty. Also, in this construct, a queue of size n can contain (n – 1) elements only. Let’s understand this using an example in the below image.
In the above figure, tail is pointing to the next available location in the queue but if we place an element there then tail will move forward and become same as the head. This results in the queue empty condition. Hence, to prevent that, tail is always kept one index before the head in a fully occupied queue. At this position, we do not insert any element causing a wastage of storage for one element. Therefore, a queue of size n can contain (n – 1) elements only in this implementation. A better way to implement queue can be using Linked Lists which we will discuss in some other article.
Enqueue
public void enqueue(T item) throws Exception {
if ((tail == (queue.length - 1) && head == 0) || (tail == head - 1)) {
throw new Exception("QueueOverflowException");
}
queue[tail] = item;
tail++;
if (tail == queue.length) {
tail = 0;
}
}In the above method, we are first checking for the overflow condition. There are two cases where overflow can occur.
- When tail is pointing to the last index of the array and head is pointing to the first. In this case, if an element is inserted at tail position, then it has to move forward. As it is a circular queue, tail will “go around” the array and start pointing to the first element. This will create the empty queue situation because both head and tail will be pointing to the same index.
- When tail is just before the head. Here also we cannot insert an element at tail for the same reason that it will force tail to move forward and will result in empty queue scenario.
Now that overflow condition is checked, we will insert the element at tail and move it forward. If tail goes beyond the array indices, we will reset it to the beginning of the array.
Dequeue
public T dequeue() throws Exception {
if (tail == head) {
throw new Exception("QueueUnderflowException");
}
T item = (T) queue[head];
head++;
if (head == queue.length) {
head = 0;
}
return item;
}Here, we first check for the underflow condition i.e., when both tail and head points to the same index. We then return the element at head and move it forward. In this case also, if head goes beyond array indices, we reset it to the beginning of the array.
Complete queue class implementation
Below is a class representing queue in Java.
package com.theaconitedev;
public class Queue<T> {
private Object[] queue;
private int head = 0;
private int tail = 0;
public Queue(int size) {
queue = new Object[size];
}
public void enqueue(T item) throws Exception {
if ((tail == (queue.length - 1) && head == 0) || (tail == head - 1)) {
throw new Exception("QueueOverflowException");
}
queue[tail] = item;
tail++;
if (tail == queue.length) {
tail = 0;
}
}
public T dequeue() throws Exception {
if (tail == head) {
throw new Exception("QueueUnderflowException");
}
T item = (T) queue[head];
head++;
if (head == queue.length) {
head = 0;
}
return item;
}
public void printQueue() {
int i = head;
while (i != tail) {
System.out.println(queue[i]);
i++;
if (i == queue.length) {
i = 0;
}
}
}
public void printQueueDetail() {
for (int i = 0; i < queue.length; i++) {
if (queue[i] == null) {
System.out.print((i + 1) + ". [empty]");
} else {
System.out.print((i + 1) + ". " + queue[i]);
}
if (i == head) {
System.out.print(" <- head");
}
if (i == tail) {
System.out.print(" <- tail");
}
System.out.println();
}
}
}
Trying out our queue class
package com.theaconitedev;
public class QueueImplementation {
public static void main(String[] args) {
System.out.println("=== Exmple 1 ===");
example1();
System.out.println("\n=== Exmple 2 ===");
example2();
}
public static void example1() {
Queue<String> queue = new Queue<>(5);
try {
queue.enqueue("Tony");
queue.enqueue("Natasha");
queue.enqueue("Clint");
queue.enqueue("Steve");
queue.enqueue("Bruce");
queue.enqueue("Thor");
} catch (Exception ex) {
ex.printStackTrace();
}
queue.printQueue();
try {
System.out.println(String.format("%s dequeued", queue.dequeue()));
System.out.println(String.format("%s dequeued", queue.dequeue()));
System.out.println(String.format("%s dequeued", queue.dequeue()));
System.out.println(String.format("%s dequeued", queue.dequeue()));
System.out.println(String.format("%s dequeued", queue.dequeue()));
} catch (Exception ex) {
ex.printStackTrace();
}
}
public static void example2() {
Queue<String> queue = new Queue<>(5);
try {
System.out.println("Enqueing Tony");
queue.enqueue("Tony");
queue.printQueueDetail();
System.out.println("\nEnqueing Steve");
queue.enqueue("Steve");
queue.printQueueDetail();
System.out.println("\nDequeing");
queue.dequeue();
queue.printQueueDetail();
System.out.println("\nEnqueing Natasha");
queue.enqueue("Natasha");
queue.printQueueDetail();
System.out.println("\nEnqueing Bruce");
queue.enqueue("Bruce");
queue.printQueueDetail();
System.out.println("\nDequeing");
queue.dequeue();
queue.printQueueDetail();
System.out.println("\nEnqueing Thor");
queue.enqueue("Thor");
queue.printQueueDetail();
System.out.println("\nQueue:");
queue.printQueue();
} catch (Exception ex) {
ex.printStackTrace();
}
}
}
=== Exmple 1 === java.lang.Exception: QueueOverflowException at com.theaconitedev.Queue.enqueue(Queue.java:14) at com.theaconitedev.QueueImplementation.example1(QueueImplementation.java:21) at com.theaconitedev.QueueImplementation.main(QueueImplementation.java:7) Tony Natasha Clint Steve Tony dequeued Natasha dequeued Clint dequeued Steve dequeued java.lang.Exception: QueueUnderflowException at com.theaconitedev.Queue.dequeue(Queue.java:27) at com.theaconitedev.QueueImplementation.example1(QueueImplementation.java:34) === Exmple 2 === at com.theaconitedev.QueueImplementation.main(QueueImplementation.java:7) Enqueing Tony 1. Tony <- head 2. [empty] <- tail 3. [empty] 4. [empty] 5. [empty] Enqueing Steve 1. Tony <- head 2. Steve 3. [empty] <- tail 4. [empty] 5. [empty] Dequeing 1. Tony 2. Steve <- head 3. [empty] <- tail 4. [empty] 5. [empty] Enqueing Natasha 1. Tony 2. Steve <- head 3. Natasha 4. [empty] <- tail 5. [empty] Enqueing Bruce 1. Tony 2. Steve <- head 3. Natasha 4. Bruce 5. [empty] <- tail Dequeing 1. Tony 2. Steve 3. Natasha <- head 4. Bruce 5. [empty] <- tail Enqueing Thor 1. Tony <- tail 2. Steve 3. Natasha <- head 4. Bruce 5. Thor Queue: Natasha Bruce Thor
In example1 method, we see that we get QueueOverflowException when we are trying to enqueue “Bruce”. Similarly, we get an QueueUnderflowException when we try to dequeue from an empty queue.
example2 demonstrates the state of the queue with every operation. We can see how tail and head are moving as we are inserting and deleting elements from it. In the last, we print the final state of the queue.