☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Implement Queue using Arrays

Easy TUF ID 387 A2ZSDE

Java source ↗ Edit this article ↗

Problem

Design a queue of integers whose storage is a plain array. A queue is a first in, first out container: elements leave in the same order they arrived. Support these operations:

Constraints: up to 10^5 operations, values fit in a 32-bit int. pop and peek on an empty queue are errors; the code throws NoSuchElementException. A fixed-capacity queue must reject a push when it is full.

Example 1

push(1), push(2), push(3), peek(), pop(), pop(), size(), isEmpty()
output: 1, 1, 2, 1, false          // 1 arrived first, so it leaves first

Example 2 (capacity 2)

push(1), push(2), pop(), push(3), peek(), pop(), pop()
output: 1, 2, 2, 3                 // the slot freed by pop() must be reusable

All three implementations below satisfy this interface so that one test script can drive them:

interface IntQueue {
    void push(int x);
    int pop();
    int peek();
    boolean isEmpty();
    int size();
}

Approach 1: Front fixed at index 0, shift on pop

Intuition. The simplest layout keeps the oldest element at data[0] and the newest at data[count - 1]. Pushing appends at data[count]. Popping removes data[0], but then every other element has to move one slot to the left so that the new oldest element is again at index 0. That shift is the cost of insisting on a fixed front.

Algorithm.

  1. Allocate data = new int[capacity] and set count = 0.
  2. push(x): if count == capacity throw; otherwise data[count++] = x.
  3. pop(): if count == 0 throw; remember data[0], copy data[i] to data[i - 1] for i = 1 .. count - 1, decrement count, return the remembered value.
  4. peek() returns data[0]; isEmpty() is count == 0; size() is count.
static class ShiftingArrayQueue implements IntQueue {
    private final int[] data;
    private int count = 0;                   // elements live in data[0 .. count-1], oldest at 0

    ShiftingArrayQueue(int capacity) {
        data = new int[capacity];
    }

    public void push(int x) {
        if (count == data.length) throw new IllegalStateException("queue overflow");
        data[count++] = x;
    }

    public int pop() {
        if (count == 0) throw new NoSuchElementException("queue underflow");
        int front = data[0];
        for (int i = 1; i < count; i++) data[i - 1] = data[i];   // O(n) shift
        count--;
        return front;
    }

    public int peek() {
        if (count == 0) throw new NoSuchElementException("queue is empty");
        return data[0];
    }

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

    public int size() {
        return count;
    }
}

Complexity. Time O(1) for push, peek, isEmpty, size and O(n) for pop because of the shift. Space O(capacity).

A variant that avoids the shift keeps a front index that only moves right and never wraps. That makes pop O(1) but leaks space: after k pops the first k slots are dead, and once front + count reaches the end the queue is “full” even if it holds a single element. The fix for that leak is the circular buffer.

Approach 2: Circular buffer

Intuition. Treat the array as a ring: the slot after data[capacity - 1] is data[0] again. Keep the index front of the oldest element and the count of stored elements. The rear slot, where the next push goes, is then (front + count) % capacity, so it does not need its own variable, and the question “is the queue full or empty?” is answered by count rather than by comparing two indices that could coincide in both situations. Popping just advances front by one, modulo the capacity. No element ever moves.

Algorithm.

  1. Allocate data = new int[capacity], set front = 0 and count = 0.
  2. push(x): if count == capacity throw; otherwise write x to data[(front + count) % capacity] and increment count.
  3. pop(): if count == 0 throw; remember data[front], set front = (front + 1) % capacity, decrement count, return the value.
  4. peek() returns data[front]; isEmpty() is count == 0; size() is count.
static class CircularArrayQueue implements IntQueue {
    private final int[] data;
    private int front = 0;                   // index of the oldest element
    private int count = 0;                   // how many slots are in use

    CircularArrayQueue(int capacity) {
        data = new int[capacity];
    }

    public void push(int x) {
        if (count == data.length) throw new IllegalStateException("queue overflow");
        data[(front + count) % data.length] = x;   // wraps around to reuse freed slots
        count++;
    }

    public int pop() {
        if (count == 0) throw new NoSuchElementException("queue underflow");
        int x = data[front];
        front = (front + 1) % data.length;
        count--;
        return x;
    }

    public int peek() {
        if (count == 0) throw new NoSuchElementException("queue is empty");
        return data[front];
    }

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

    public int size() {
        return count;
    }
}

Dry run on example 2 with capacity 2:

operation data front count rear = (front+count)%2 returns
push(1) [1, _] 0 1 1  
push(2) [1, 2] 0 2 0  
pop() [1, 2] 1 1 0 1
push(3) [3, 2] 1 2 1  
peek() [3, 2] 1 2   2
pop() [3, 2] 0 1   2
pop() [3, 2] 1 0   3

The push of 3 wrapped around into index 0, the slot that pop had freed. The shifting queue would have reached the same answers by moving 2 to index 0 first.

Complexity. Time O(1) for every operation: constant index arithmetic plus one array access. Space O(capacity).

Approach 3: Growable circular buffer

Intuition. The ring removes the space leak but still has a hard capacity. Doubling the array when it is full gives amortised O(1) pushes, exactly as for a growable stack, with one twist: the elements may be wrapped around, so copying data slot by slot would scramble their order. Instead, copy them in queue order starting at front, so that the oldest lands at index 0 of the new array, and reset front to 0.

Algorithm.

  1. Start with data = new int[2], front = 0, count = 0.
  2. push(x): if count == data.length, call grow(): allocate twice the length, copy element i from data[(front + i) % oldLength] to bigger[i], then replace data and set front = 0. Then push as in approach 2.
  3. All other operations are identical to approach 2.
static class DynamicCircularQueue implements IntQueue {
    private int[] data = new int[2];
    private int front = 0;
    private int count = 0;

    public void push(int x) {
        if (count == data.length) grow();
        data[(front + count) % data.length] = x;
        count++;
    }

    private void grow() {
        int[] bigger = new int[data.length * 2];
        for (int i = 0; i < count; i++) bigger[i] = data[(front + i) % data.length];   // unwrap: oldest lands at 0
        data = bigger;
        front = 0;
    }

    public int pop() {
        if (count == 0) throw new NoSuchElementException("queue underflow");
        int x = data[front];
        front = (front + 1) % data.length;
        count--;
        return x;
    }

    public int peek() {
        if (count == 0) throw new NoSuchElementException("queue is empty");
        return data[front];
    }

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

    public int size() {
        return count;
    }

    int capacity() {
        return data.length;
    }
}

Complexity. Time amortised O(1) per operation; a push that grows the array costs O(n) but happens only after n pushes since the last growth. Space O(n).

Edge cases and pitfalls