The queue data structure is the data structure that offers First in First out (FIFO) behaviour and also the insertion, deletion and reading of the element at a constant time(O(1)). We can implement the queue data structure using a circular array, LinkedList. Here in this post, we will implement with the help of a circular array.

Circular array: It's the normal array of fixed size where the data will be inserted circularly means if the array is full then the data will be again inserted (element will be overridden with new value) at the 0th index.

To implement the queue we need to design some parameters to do the followings

1. Check if the queue is empty

2. Check if the queue is full

3. Insert in the queue(O(1) time complexity)

4. Remove the element from the queue (O(1))

5. Get the first element (O(1))

The params we would be taking are

public class MyQueue {
    int arr[];
    int currentSize;
    int maxSize;
    int front;
    int rear;

    public MyQueue(int size){
        arr = new int[size];
        currentSize = 0;
        maxSize = size;
        front = 0;
        rear = maxSize -1;
    }
}

Now we need write the functions. I will elaborate push and pop functions as other functions can be understood easily from the code.

push() - The push will always happen at rear index, initially its pointing to the last index. As we are using circular array we need to use the mod of maxSize so that the index does not go out side the size limit of the array.

public void push(int value){
    if(!isFull()){
        rear = (rear +1)%maxSize;
        arr[rear] = value;
        currentSize++;
    }
}

pop() - Here we in this function we are not going to remove or shift any elements as it would take O(n) time to do that, instead we just move our front index one step ahead, so when ever the pop function is called the front will move to next index.

public void pop(){
        if(!isEmpty()){
            front = (front +1)%maxSize;
            currentSize--;
        }
  }

By following above techniques we can insert and remove the elements in O(1) time

push - O(1)

pop - O(1)

getFront - O(1)

The final code

public class MyQueue {

    int arr[];
    int currentSize;
    int maxSize;
    int front;
    int rear;

    public MyQueue(int size){
        arr = new int[size];
        currentSize = 0;
        maxSize = size;
        front = 0;
        rear = maxSize -1;
    }


    public boolean isFull(){
        return currentSize == maxSize;
    }

    public boolean isEmpty(){
        return currentSize == 0;
    }

    public void push(int value){
        if(!isFull()){
            rear = (rear +1)%maxSize;
            arr[rear] = value;
            currentSize++;
        }
    }

    public void pop(){
        if(!isEmpty()){
            front = (front +1)%maxSize;
            currentSize--;
        }
    }

    public int getFront(){
        return arr[front];
    }

    public static void main(String[] args) {
        MyQueue queue = new MyQueue(5);
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        while(!queue.isEmpty()){
            System.out.println(queue.getFront());
            queue.pop();
        }
    }
}

Follow me for more tech content related to DSA, System Design and Java