Implementing Queues: Circular Arrays & Linked Lists

1. The Problem with a Simple Array

The most intuitive way to build a queue is with a standard array. We can use two pointers, front and rear, to keep track of the start and end of the queue.

• enqueue(value): Add the element at the rear index and increment rear. This is an efficient O(1) operation.
• dequeue(): Remove the element from the front index.

Here's the catch: after removing the element at front, that space is now empty. To maintain a contiguous block of elements, we would have to shift all subsequent elements one position to the left. This shifting makes the dequeue operation O(N), which is highly inefficient and defeats the purpose of having a fast queue.

To see a walkthrough of this naive implementation and its performance bottleneck, let's watch a short segment of the following video.

This inefficiency is precisely why we need better implementations.

2. Implementation 1: The Circular Array

To avoid the O(N) dequeue operation, we can treat the array as circular. When the front or rear pointers reach the end of the array, they "wrap around" to the beginning. This way, we never need to shift elements. The key to this behavior is the modulo operator (%).

Core Concepts

We maintain an array and two pointers, front and rear.

• Pointers and Indices:
  • front: Index of the first element.
  • rear: Index of the next available slot where a new element will be inserted.
  • size: The current number of elements in the queue.
• enqueue(value):
  1. Check if the queue is full (size == capacity).
  2. Add the new element at arr[rear].
  3. Update the rear pointer: rear = (rear + 1) % capacity.
  4. Increment size.
• dequeue():
  1. Check if the queue is empty (size == 0).
  2. Retrieve the element from arr[front].
  3. Update the front pointer: front = (front + 1) % capacity.
  4. Decrement size.

Both enqueue and dequeue are now O(1) operations.

To get a detailed visual explanation of how the pointers move and wrap around, the following video provides a very clear walkthrough.

Java Implementation (Circular Array)

This implementation uses front, size, and capacity to manage the queue state, which is a common and robust approach. The rear index is calculated on the fly when needed.

Here's the code, adapted from the article, for your reference.

class CircularQueue {
    private int[] arr;
    private int front;
    private int size;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.arr = new int[capacity];
        this.front = 0;
        this.size = 0;
    }

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

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

    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue is full. Cannot enqueue " + value);
            return;
        }
        // Calculate rear index before insertion
        int rear = (front + size) % capacity;
        arr[rear] = value;
        size++;
        System.out.println("Enqueued: " + value);
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return -1; // Or throw an exception
        }
        int removedValue = arr[front];
        front = (front + 1) % capacity;
        size--;
        System.out.println("Dequeued: " + removedValue);
        return removedValue;
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return -1;
        }
        return arr[front];
    }
}

3. Implementation 2: The Linked List

A circular array solves the efficiency problem, but it still has a fixed capacity. If you need a queue that can grow and shrink dynamically, a linked list is the perfect choice.

Core Concepts

We use a singly linked list and maintain two pointers: front (or head) and rear (or tail).

• front: Points to the first node in the list.
• rear: Points to the last node in the list.
• enqueue(value):
  1. Create a new node with the given value.
  2. If the queue is empty, set both front and rear to the new node.
  3. Otherwise, set rear.next to the new node and update rear to point to the new node.
• dequeue():
  1. Check if the queue is empty (front == null).
  2. Store the data from the front node.
  3. Move front to front.next.
  4. If front becomes null (meaning the last element was just removed), also set rear to null.

Again, both operations are a clean and efficient O(1).

You can see this implementation animated in the final section of the "Apna College" video.

Java Implementation (Linked List)

Here is a standard Java implementation for a queue using a linked list.

This implementation clearly shows the role of the front and rear pointers.

// Node class for the linked list
class Node {
    int data;
    Node next;

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

// Queue class using a linked list
class LinkedListQueue {
    private Node front, rear;

    public LinkedListQueue() {
        this.front = this.rear = null;
    }

    public boolean isEmpty() {
        return this.front == null;
    }

    // Add an element to the rear of the queue
    public void enqueue(int value) {
        Node newNode = new Node(value);
        System.out.println("Enqueued: " + value);

        // If queue is empty, new node is both front and rear
        if (this.isEmpty()) {
            this.front = this.rear = newNode;
            return;
        }

        // Add the new node at the end and update rear
        this.rear.next = newNode;
        this.rear = newNode;
    }

    // Remove an element from the front of the queue
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return -1; // Or throw an exception
        }

        int removedValue = this.front.data;
        this.front = this.front.next;

        // If front becomes null, then change rear to null as well
        if (this.front == null) {
            this.rear = null;
        }
        
        System.out.println("Dequeued: " + removedValue);
        return removedValue;
    }
}

4. Comparison: Circular Array vs. Linked List

This is a classic technical interview question. Knowing the trade-offs is crucial.

When to use which?

• Use a circular array when you have a good estimate of the maximum number of elements the queue will hold and performance is critical (cache locality can matter).
• Use a linked list when the number of elements is unpredictable or when simplicity of implementation is valued.

Conclusion

Great job! You've now learned how to implement one of the most fundamental data structures, the queue, in two standard and efficient ways.

Key Takeaways:

• A queue operates on a First-In, First-Out (FIFO) basis.
• A naive array implementation is inefficient for dequeue (O(N)).
• A circular array uses the modulo operator to achieve O(1) enqueue and dequeue with a fixed capacity.
• A linked list provides a dynamically-sized queue with O(1) enqueue and dequeue by managing front and rear pointers.
• The choice between a circular array and a linked list involves a trade-off between memory management (static vs. dynamic) and performance characteristics (cache locality).

Preview of the next lesson:
Now that you understand both stacks and queues, get ready for an interesting interview puzzle. In the next lesson, we will explore how to implement a queue using two stacks. This will test your understanding of both data structures and their operational constraints.