Jaspreet singh

Posted on Jun 24

Implement Queue Using Array

#computerscience #algorithms #beginners #java

Problem Statement

Implement a Queue using an array supporting:

enqueue(x)
dequeue()
getFront()
getRear()

Following FIFO:

First In First Out

Brute Force Intuition

Use:

ArrayList

Insert at end.

Remove from front.

But removing from front causes shifting.

Moving Towards the Array Approach

Maintain:

size

Insert:

arr[size++] = x;

Delete:

Shift all elements left.

Pattern Recognition

Queue

=> Array + Front Removal

Optimal Java Solution

class myQueue {

    int[] arr;
    int size;

    public myQueue(int n) {

        arr = new int[n];
        size = 0;
    }

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

    public boolean isFull() {
        return size == arr.length;
    }

    public void enqueue(int x) {

        if (!isFull()) {
            arr[size++] = x;
        }
    }

    public void dequeue() {

        if (!isEmpty()) {

            for (int i = 0; i < size - 1; i++) {
                arr[i] = arr[i + 1];
            }

            size--;
        }
    }

    public int getFront() {
        return isEmpty() ? -1 : arr[0];
    }

    public int getRear() {
        return isEmpty() ? -1 : arr[size - 1];
    }
}

Dry Run

enqueue(10)

enqueue(20)

enqueue(30)

Queue:

10 20 30

dequeue()

Queue:

20 30

Front:

Rear:

Complexity Analysis

Operation	Complexity
Enqueue	O(1)
Dequeue	O(N)
Front	O(1)
Rear	O(1)

Interview One-Liner

Insert at rear and shift elements during deletion to maintain FIFO ordering.

DEV Community