Queue Using Array
Implementing a queue using an array is common. We maintain two indices: `front` (index of first element) and `rear` (index of last element). However, a simple array implementation suffers from wasted space after dequeue. A more efficient approach uses a circular array.
Simple array-based queue
public class ArrayQueue<T> {
private Object[] arr;
private int front, rear, size, capacity;
public ArrayQueue(int capacity) {
this.capacity = capacity;
arr = new Object[capacity];
front = 0;
rear = -1;
size = 0;
}
public void enqueue(T item) {
if (size == capacity) throw new RuntimeException("Queue overflow");
rear = (rear + 1) % capacity;
arr[rear] = item;
size++;
}
public T dequeue() {
if (isEmpty()) throw new RuntimeException("Queue underflow");
T item = (T) arr[front];
front = (front + 1) % capacity;
size--;
return item;
}
public T front() {
if (isEmpty()) throw new RuntimeException("Queue empty");
return (T) arr[front];
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
}
Two Minute Drill
- Array-based queue uses circular array to reuse space.
- Enqueue: O(1), dequeue: O(1), front: O(1).
- Maintain front, rear, and size (or use modulo logic).
- Overflow when size == capacity.
Need more clarification?
Drop us an email at career@quipoinfotech.com