How to Implement a Queue in Java: Arrays vs Linked Lists

Understanding Queue Fundamentals

Queues operate on the First-In-First-Out (FIFO) principle, identical to real-world waiting lines. When implementing queues in Java, you'll typically handle three core operations: enqueue (add), dequeue (remove), and peek (inspect). After analyzing this video, I've observed that queues are among the most frequently tested data structures in coding interviews at companies like Amazon and Google, making mastery essential for placement success.

The video demonstrates two critical implementation approaches: array-based (with circular buffering) and linked list-based. Each has distinct performance characteristics:

• Array implementations offer O(1) time complexity for all operations but have fixed size
• Linked lists provide dynamic resizing but slightly higher memory overhead

Key Queue Operations Explained

1. Enqueue: Adds elements at the rear position
2. Dequeue: Removes elements from the front position
3. Peek: Inspects the front element without removal
4. isEmpty: Checks if the queue contains elements
5. isFull (array-only): Determines if capacity is reached

Array-Based Implementation: Circular Queues

Core Structure and Initialization

public class ArrayQueue {
    private int[] arr;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
        front = rear = -1; // Initial empty state
        size = 0;
    }
}

The circular queue optimization solves the "wasted space" problem in linear implementations. When the rear pointer reaches the array's end, it wraps around to index 0 if space is available. This approach significantly improves memory utilization efficiency.

Handling Critical Edge Cases

public void enqueue(int data) {
    if (isFull()) {
        throw new IllegalStateException("Queue overflow");
    }
    if (isEmpty()) {
        front = 0;
    }
    rear = (rear + 1) % capacity; // Circular wrap
    arr[rear] = data;
    size++;
}

public int dequeue() {
    if (isEmpty()) {
        throw new NoSuchElementException("Queue underflow");
    }
    int data = arr[front];
    if (front == rear) {
        front = rear = -1; // Reset on last element
    } else {
        front = (front + 1) % capacity; // Circular advancement
    }
    size--;
    return data;
}

Common pitfalls in circular queue implementation include mishandling the front/rear reset conditions and incorrect modulus calculations. Practice shows that the single-element removal case (front == rear) requires special handling to avoid pointer corruption.

Linked List Implementation

Node Structure and Initialization

class QueueNode {
    int data;
    QueueNode next;
    
    public QueueNode(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListQueue {
    private QueueNode front;
    private QueueNode rear;
    
    public LinkedListQueue() {
        front = rear = null;
    }
}

Linked lists naturally support dynamic sizing and avoid the fixed-capacity limitations of arrays. The video correctly emphasizes that this implementation shines when handling unpredictable data volumes.

Pointer Management in Operations

public void enqueue(int data) {
    QueueNode newNode = new QueueNode(data);
    if (rear == null) {
        front = rear = newNode; // First element
        return;
    }
    rear.next = newNode;
    rear = newNode; // Update rear pointer
}

public int dequeue() {
    if (front == null) {
        throw new NoSuchElementException("Queue empty");
    }
    int data = front.data;
    front = front.next;
    if (front == null) {
        rear = null; // Reset on last element
    }
    return data;
}

Critical insight: Always update the rear pointer during enqueue operations and handle the last-element removal by resetting both pointers. This prevents dangling references and memory leaks.

Java's Built-in Queue Implementations

LinkedList vs ArrayDeque

// Using LinkedList implementation
Queue<Integer> queue = new LinkedList<>();
queue.add(10);
queue.remove();

// Using ArrayDeque implementation
Queue<Integer> dequeQueue = new ArrayDeque<>();
dequeQueue.offer(20);
dequeQueue.poll();

The video references Java's Queue interface but doesn't fully explore the performance nuances. Based on Java documentation:

• LinkedList: Better for frequent insertions/deletions
• ArrayDeque: Superior memory locality for iteration
• PriorityQueue: Not FIFO - uses natural ordering

Method Comparison Table

Operation	Throw Exception	Return Special Value
Insert	add()	offer()
Remove	remove()	poll()
Examine	element()	peek()

Performance Analysis and Interview Strategy

Time Complexity Comparison

Operation	Array (Circular)	Linked List
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
Peek	O(1)	O(1)
Space	Fixed	Dynamic

Common Interview Questions

1. Implement stack using queues
2. Reverse first k queue elements
3. Generate binary numbers using queues
4. Circular tour problem (petrol pumps)
5. Sliding window maximum

Pro tip: When asked to implement queues during interviews, always:

1. Clarify expected operations upfront
2. Discuss size constraints
3. Propose both array and linked list approaches
4. Justify your chosen implementation

Practical Implementation Cheat Sheet

// Essential helper methods
public boolean isEmpty() {
    return size == 0; // Array implementation
    return front == null; // Linked list
}

public boolean isFull() { // Array only
    return size == capacity;
}

public int peek() {
    if (isEmpty()) throw new NoSuchElementException();
    return arr[front]; // Array
    return front.data; // Linked list
}

Advanced Resource Recommendations

1. Book: "Algorithms" by Robert Sedgewick (excellent queue use cases)
2. Course: Princeton's Algorithms Course (Coursera)
3. Tool: Visualgo.net (visualize queue operations)
4. Practice: Leetcode Queue Tag (150+ problems)
5. Community: Stack Overflow Java Queue Tag (real-world problem solving)

Which queue implementation challenge have you struggled with most? Share your experience in the comments below.