Java Queue Implementation using Array

In this post, we will show you how to implement Java Queue using Array with an example.

A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at another end (front). The first element to be inserted is the first one to be deleted. Hence, it is called the First in First out (FIFO) or Last in Last out (LILO) list.

Queue Concepts

• When an element is inserted in a queue, the concept is called EnQueue.
• When an element is removed from the queue, the concept is called DeQueue.
• DeQueueing an empty queue is called underflow (treat as Exception).
• EnQueuing an element in a full queue is called overflow (treat as Exception).

Queue Operations

Let's list out basic operations associated with queues −

• enqueue() − add (store) an item to the queue.
• dequeue() − remove (access) an item from the queue.

Few more functions are required to make the above-mentioned queue operation efficient. These are −

• peek() − Gets the element at the front of the queue without removing it.
• isFull() − Checks if the queue is full.
• isEmpty() − Checks if the queue is empty.

Java Queue Implementation using Array

Let's create MyQueue generic class and the following content to it:

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.EmptyStackException;

public final class MyQueue {

    private static final int DEFAULT_CAPACITY = 10;

    private int front;    // elements are removed or peeked from the front
    private int rear;     // elements are added in the rear
    private int count;    // size of the queue
    private int capacity; // capacity of the queue (this is doubled when is exceeded)

    private E[] queue;    // the array that sits behind the queue

    // constructor to initialize the queue
    MyQueue() {
        // we use Java Reflection since Java doesn't allow us to instantiate a generic array
        queue = (E[]) Array.newInstance(
                Object[].class.getComponentType(), DEFAULT_CAPACITY);

        count = 0; // initially, the size of the queue is 0
        front = 0; // the index of the first element is 0
        rear = -1; // initially, there is no element in the queue

        capacity = DEFAULT_CAPACITY; // initially, the capacity is of 10 elements
    }

    // add an element 'e' in the queue
    public void enqueue(E e) {

        // if the queue is full, we double its capacity
        if (isFull()) {
            ensureCapacity();
        }

        // adding the element in the rear of the queue
        rear = (rear + 1) % capacity;       
        queue[rear] = e;
        
        // update the size of the queue
        count++;
    }

    // remove and return the front element from the queue
    public E dequeue() {

        // if the queue is empty we just throw a meaningful exception
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        // extract the element from the front
        E e = queue[front];    
        queue[front] = null;        
        
        // set the new front
        front = (front + 1) % capacity;      
        
        // decrease the size of the queue
        count--;
       
        return e;
    }

    // return but not remove the front element in the queue
    public E peek() {
        
        // if the queue is empty we just throw a meaningful exception
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        
            return queue[front];        
    }

    // size of the queue
    public int size() {
        return count;
    }

    // check if the queue is empty or not
    public boolean isEmpty() {
        return size() == 0;
    }

    // check if the queue is full or not
    public boolean isFull() {
        return size() == capacity;
    }

    // used internally for doubling the queue capacity
    private void ensureCapacity() {       
        int newSize = queue.length * 2;
        queue = Arrays.copyOf(queue, newSize);
        
        // setting the new capacity
        capacity = newSize;
    }
}

Let's create Main class to test above Queue implementation logic:

public class Main {

    public static void main(String[] args) {

        MyQueue stack = new MyQueue();

        stack.enqueue(25);
        stack.enqueue(35);
        stack.enqueue(15);

        System.out.println("Size: " + stack.size());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.dequeue());
        System.out.println("Size: " + stack.size());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());
        System.out.println("Push 17");
        stack.enqueue(17);
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.dequeue());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.dequeue());
        System.out.println("Size: " + stack.size());
        System.out.println("Push 55");
        stack.enqueue(55);
        System.out.println("Size: " + stack.size());
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.dequeue());
        System.out.println("Size: " + stack.size());
        System.out.println("Pop: " + stack.dequeue());
        System.out.println("Size: " + stack.size());
        System.out.println("Is empty? " + stack.isEmpty());
    }

}

Output:

Size: 3
Peek: 25
Size: 3
Pop: 25
Size: 2
Peek: 35
Size: 2
Push 17
Peek: 35
Size: 3
Pop: 35
Size: 2
Pop: 15
Size: 1
Push 55
Size: 2
Peek: 17
Size: 2
Pop: 17
Size: 1
Pop: 55
Size: 0
Is empty? true