Queue

Circular Queue

constexpr int MAX_QUEUE = 1'000'000;
template<typename T>
struct Queue {
    T q[MAX_QUEUE];
    int qf, qr; // queue front, rear
    void init() {
        qf = qr = 0;
    }
    bool isEmpty() {
        return qf == qr;
    }
    void insert(T v) {
        q[qr++] = v;
        qr %= MAX_QUEUE;
    }
    T pop() {
        T res = q[qf++];
        qf %= MAX_QUEUE;
        return res;
    }
};

Time Complexity

• Insert: $O(1)$
• Pop: $O(1)$