We're sorry this tutorial wasn't helpful. Please tell us what we can do better.
Queue Implementation using Array
Last updated:
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;
}
}