MiddleCodeCommonNot answered yet
Implement a queue with a fixed-size circular buffer
Implement a fixed-size queue backed by a circular buffer over a contiguous array, with enqueue, dequeue, front, size, empty, and full.
Requirements:
- All operations are O(1); no dynamic allocation after construction.
- Define
emptyandfulldistinctly (e.g. waste one slot, or keep a size counter). dequeue/fronton an empty queue andenqueueon a full queue should signal the error.
#include <vector>
template<typename T>
class CircularQueue {
public:
explicit CircularQueue(size_t capacity);
void enqueue(const T& val);
T dequeue();
const T& front() const;
bool empty() const;
bool full() const;
size_t size() const;
// your code here
};Write the implementation.
A circular buffer queue uses a fixed array with head and tail indices wrapping around modulo capacity. enqueue writes to tail and advances it; dequeue reads from head and advances it. Full condition: (tail + 1) % cap == head. This gives O(1) enqueue/dequeue with no dynamic allocation.
- ✗Confusing full and empty conditions — use (tail + 1) % cap == head for full, head == tail for empty
- ✗Wasting one slot to distinguish full from empty — alternative: use a separate size counter
- ✗Off-by-one in the modulo arithmetic
- →How would you make this queue thread-safe for one producer and one consumer?
- →What is the advantage of a circular buffer over a linked-list-backed queue?
Contents
Task
Implement a fixed-size circular buffer queue with enqueue, dequeue, front, size, empty, full operations.
Key points
- One slot is intentionally wasted to distinguish empty vs full states.
- Alternative: store a separate
size_counter — no slot wasted. - All operations are O(1), no dynamic allocation after construction.
Contents
