We're sorry this tutorial wasn't helpful. Please tell us what we can do better.
Queue Implementation using Array
Last updated:
A queue serves elements in FIFO order (First In, First Out): elements join at the rear (tail) and leave from the front (head).
The simplest way to store a queue is an array with two indexes: front points at the element that will leave next, and rear points at the element that arrived last. This page builds that version in Java.
Operations in Queue
Enqueue: add an element at the rear.
Dequeue: remove the element at the front.
Peek or front: return the front element without removing it.
rear: return the rear element without removing it.
isFull: tell whether no more elements can be added.
isEmpty: tell whether the queue has no elements.
Example: Queue Implementation using Array in Java
How the class works:
The queue starts empty with front = 0 and rear = -1; it is empty whenever front > rear.
enqueue() increments rear and stores the value there.
dequeue() simply increments front. No element is moved, so both operations are O(1).
The limitation of this simple version is that slots before front are never reused: after 100 enqueues the queue reports "full" even if many elements have been dequeued. The circular queue fixes this by wrapping the indexes around the array (see also FAQ Q2).
Class: QueueImplUsingArray
QueueImplUsingArray.java
// A simple (linear) queue of int values stored in an array
class QueueImplUsingArray {
private final int capacity = 100; // maximum number of enqueues
private final int[] queueArray;
private int front; // index of the front element
private int rear; // index of the rear element, front - 1 when empty
QueueImplUsingArray() {
queueArray = new int[capacity];
front = 0;
rear = -1;
}
boolean isEmpty() {
return front > rear;
}
// Adds an element at the rear: O(1)
void enqueue(int data) {
if (rear == capacity - 1) {
System.out.println("Queue is full");
return;
}
queueArray[++rear] = data;
}
// Removes the element at the front: O(1), only front moves
void dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
front++;
}
// Prints the elements from front to rear
void printQueue() {
if (isEmpty()) {
System.out.println("Queue is Empty");
return;
}
for (int i = front; i <= rear; i++) {
System.out.print(queueArray[i] + " ");
}
System.out.println();
}
// Shows the front element without removing it
void front() {
if (isEmpty()) {
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) {
if (size == items.length) {
throw new IllegalStateException("Queue is full");
}
items[(front + size) % items.length] = value;
size++;
}
@SuppressWarnings("unchecked")
public T dequeue() {
if (size == 0) {
throw new IllegalStateException("Queue is empty");
}
T value = (T) items[front];
items[front] = null; // avoid holding a stale reference
front = (front + 1) % items.length;
size--;
return value;
}
}