Queue implementation using an Array

Q: How do you implement a queue using an array?

Keep an array plus two indexes: front for the next element to remove, and rear for the next free slot. Enqueue writes at rear, dequeue reads at front, and both indexes move forward (wrapping around in a circular version).

Q: Write a queue using an array in Java.

Java example: public class ArrayQueue { private final int[] items; private int front = 0, rear = 0, size = 0; public ArrayQueue(int capacity) { items = new int[capacity]; } public void enqueue(int value) { if (size == items.length) { throw new IllegalStateException("Queue is full"); } items[rear] = value; rear = (rear + 1) % items.length; size++; } public int dequeue() { if (size == 0) { throw new IllegalStateException("Queue is empty"); } int value = items[front]; front = (front + 1) % items.length; size--; return value; } public int peek() { if (size == 0) { throw new IllegalStateException("

Q: What happens when the array is full?

A fixed-size queue must reject the new element (return false or throw an exception), which is called overflow. A dynamic version instead creates a larger array, typically twice the size, and copies the elements in order from front.

Q: Write a resize method for an array queue.

Doubling keeps enqueue at O(1) amortized, as in ArrayList and ArrayDeque.

Q: Why use modulo when moving the indexes?

(index + 1) % capacity turns the array into a ring: after the last index it returns to 0. Without it, the indexes would run past the end and freed slots at the start would never be reused.

Q: What is queue underflow, and how should it be handled?

Underflow is trying to dequeue or peek from an empty queue. Handle it by checking the size first and either throwing an exception or returning a special value, as Java's poll() returns null.

Q: What are the pros and cons of an array queue compared with a linked-list queue?

Array: less memory per element, better cache performance; fixed capacity or occasional resizing. Linked list: grows one node at a time with no resizing; extra memory for each node and slower traversal.

Q: How do you print all elements of an array queue in order?

Java example: static void print(int[] items, int front, int size) { for (int i = 0; i < size; i++) { System.out.print(items[(front + i) % items.length] + " "); } System.out.println(); }

Q: Can an array queue store objects instead of int values?

Yes. Use a generic class with an Object[] array cast to T[], and set dequeued slots to null so the garbage collector can reclaim the objects:

Queue Implementation using Array

A Queue is a linear data structure to store and manipulate the data elements. A queue follows the concept of "First in, First out" (FIFO), where the first element inserted into the queue is the first one to be deleted from the queue.

A queue is open at both ends which enables insert operations to be performed at one end called REAR or TAIL and delete operations to be performed at another end called FRONT or HEAD.

Operations in Queue

Enqueue: Add a new element to the end of the queue.
Dequeue: Remove an element from the front of the queue.
Peek or front: Retrieve the frontmost element in the queue without deleting it.
rear: Returns the element at the end in the queue without deleting it.
isFull: Checks if the queue is full.
isEmpty: Checks if the queue is empty.

Example: Queue Implementation using Array in Java

Class: QueueImplUsingArray

QueueImplUsingArray.java

class QueueImplUsingArray {
  int front, rear, array_size = 100;
  int[] queueArray;

  // Constructor to initialize the queue
  QueueImplUsingArray() {
    front = 0;
    rear = -1;
    queueArray = new int[array_size];
  }

  // Function to insert an element at the rear of the queue
  void enqueue(int data) {
    // Check if the queue is full
    if (rear == array_size - 1) {
      System.out.println("Queue is full");
      return;
    }

    // Insert element at the rear
    queueArray[++rear] = data;
  }

  // Function to delete an element from the front of the queue
  void dequeue() {
    // If the queue is empty
    if (front > rear) {
      System.out.println("Queue is empty");
      return;
    }

    // Shift all elements from index 1 till rear to the left by one
    for (int i = 0; i < rear; i++) {
      queueArray[i] = queueArray[i + 1];
    }

    // Decrement rear by 1
    rear--;
  }

  // Function to print all elements of queue
  void printQueue() {
    if (front > rear) {
      System.out.println("Queue is Empty");
      return;
    }

    // Traverse front to rear and print elements
    for (int i = front; i <= rear; i++) {
      System.out.print(queueArray[i] + "  ");
    }
    System.out.println(); // Line break
  }

  // Function to print the front of the queue
  void front() {
    if (rear == -1) {
      System.out.println("Queue is Empty");
      return;
    }
    System.out.println("Queue Front Element is: " + queueArray[front]);
  }

  public static void main(String[] args) {
    QueueImplUsingArray queue = new QueueImplUsingArray();

    // Print queue elements
    queue.printQueue();

    // Insert elements in the queue
    queue.enqueue(20);
    queue.enqueue(30);
    queue.enqueue(40);
    queue.enqueue(50);

    // Print queue elements
    queue.printQueue();

    // Insert element in the queue
    queue.enqueue(60);

    // Print queue elements
    queue.printQueue();

    // Dequeue elements
    queue.dequeue();
    queue.dequeue();

    System.out.print("Queue elements after two node deletions: ");

    // Print queue elements
    queue.printQueue();

    System.out.print("Queue elements after one insertion: ");
    queue.enqueue(60);

    // Print queue elements
    queue.printQueue();

    // Print front of the queue
    queue.front();
  }
}

Output

Queue is Empty
20  30  40  50
20  30  40  50  60
Queue elements after two node deletions: 40  50  60
Queue elements after one insertion: 40  50  60  60
Queue Front Element is: 40

Frequently Asked Questions (FAQ)

Q1. How do you implement a queue using an array?

Keep an array plus two indexes: front for the next element to remove, and rear for the next free slot. Enqueue writes at rear, dequeue reads at front, and both indexes move forward (wrapping around in a circular version).

Q2. Write a queue using an array in Java.

ArrayQueue.java

public class ArrayQueue {
    private final int[] items;
    private int front = 0, rear = 0, size = 0;

    public ArrayQueue(int capacity) {
        items = new int[capacity];
    }

    public void enqueue(int value) {
        if (size == items.length) {
            throw new IllegalStateException("Queue is full");
        }
        items[rear] = value;
        rear = (rear + 1) % items.length;
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        int value = items[front];
        front = (front + 1) % items.length;
        size--;
        return value;
    }

    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        return items[front];
    }

    public static void main(String[] args) {
        ArrayQueue q = new ArrayQueue(3);
        q.enqueue(10);
        q.enqueue(20);
        System.out.println(q.dequeue());   // 10
        System.out.println(q.peek());      // 20
    }
}

Q3. What is the time complexity of an array-based queue?

With moving indexes (and wrap-around), enqueue, dequeue and peek are all O(1). If dequeue shifted all elements left instead, it would become O(n).

Q4. What happens when the array is full?

A fixed-size queue must reject the new element (return false or throw an exception), which is called overflow. A dynamic version instead creates a larger array, typically twice the size, and copies the elements in order from front.

Q5. Write a resize method for an array queue.

ResizeQueue.java

static int[] items = new int[4];
static int front = 0, rear = 0, size = 0;

static void resize() {
    int[] bigger = new int[items.length * 2];
    for (int i = 0; i < size; i++) {
        bigger[i] = items[(front + i) % items.length];   // copy in queue order
    }
    items = bigger;
    front = 0;
    rear = size;
}

Doubling keeps enqueue at O(1) amortized, as in ArrayList and ArrayDeque.

Q6. Why use modulo when moving the indexes?

(index + 1) % capacity turns the array into a ring: after the last index it returns to 0. Without it, the indexes would run past the end and freed slots at the start would never be reused.

Q7. What is queue underflow, and how should it be handled?

Underflow is trying to dequeue or peek from an empty queue. Handle it by checking the size first and either throwing an exception or returning a special value, as Java's poll() returns null.

Q8. What are the pros and cons of an array queue compared with a linked-list queue?

Array: less memory per element, better cache performance; fixed capacity or occasional resizing.
Linked list: grows one node at a time with no resizing; extra memory for each node and slower traversal.

Q9. How do you print all elements of an array queue in order?

PrintQueue.java

static void print(int[] items, int front, int size) {
    for (int i = 0; i < size; i++) {
        System.out.print(items[(front + i) % items.length] + " ");
    }
    System.out.println();
}

Q10. Can an array queue store objects instead of int values?

Yes. Use a generic class with an Object[] array cast to T[], and set dequeued slots to null so the garbage collector can reclaim the objects:

GenericQueue.java

public class GenericQueue<T> {
    private final Object[] items;
    private int front = 0, size = 0;

    public GenericQueue(int capacity) {
        items = new Object[capacity];
    }

    public void enqueue(T value) {
        items[(front + size) % items.length] = value;
        size++;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        T value = (T) items[front];
        items[front] = null;                  // avoid holding a stale reference
        front = (front + 1) % items.length;
        size--;
        return value;
    }
}

Was this tutorial helpful?

Help Us Improve

Queue Implementation using Array

Operations in Queue

Example: Queue Implementation using Array in Java

Frequently Asked Questions (FAQ)