Array based Queue

Linked lists offer flexibility but poor cache locality and frequent heap allocations. To optimize performance, we can use a circular buffer backed by a fixed-size array to implement queues.

Advantages of Array-Based Queues

• Contiguous memory → better CPU cache locality
• No dynamic allocation → avoids malloc/free overhead
• Constant-time push, pop, and front

This implementation:

• Wraps around when it reaches the end of the array
• Maintains a head and tail index
• Detects full and empty states by tracking size or offset

Your Task

Implement a fixed-size circular queue with the following operations:

• push(val) -- adds to the tail
• pop() -- removes from the head
• front() -- returns the front element
• empty() -- returns true if empty

You don't need to implement resizing (yet).

Bonus

• Take the size of the queue as a template parameter
• Since multiplication/division for general integers is slow, restrict the size of the queue to a power of 2 and use bitwise operations to calculate the index of the head and tail.

Implement a basic queue using a circular array in C++.

#include <vector>

template <typename T>
class ArrayQueue {
private:
    // data structures here
    int capacity = 1000;  // default capacity

public:
    ArrayQueue() {
        // TODO: Initialize data structures
    }

    void push(const T& val) {
        // TODO: Insert at tail
    }

    void pop() {
        // TODO: Remove from head
    }

    T& front() {
        // TODO: Return the front element
        return;
    }

    bool empty() const {
        return;
    }
};