Implement a Queue using a Circular Array

To implement a circular queue with a fixed-size array, I would start by defining three key instance variables: an array to store elements, an integer for the head index, and another for the tail index. Crucially, I would also maintain a 'size' variable to track the current number of elements. This approach prevents ambiguity between an empty and full state, which often occurs if we rely solely on head and tail positions. For the enqueue operation, I will first check if the queue is full by comparing the size against the capacity. If it is full, I might throw an exception or return false, depending on the contract. Otherwise, I place the new element at the tail position and increment the tail index using modulo arithmetic: tail = (tail + 1) % capacity. This ensures that when the tail reaches the end of the array, it seamlessly wraps around to index zero. Similarly, for dequeue, I check if the queue is empty. If not, I retrieve the element at the head, set it to null to help garbage collection, and update the head index using the same modulo logic. By maintaining the size counter, both operations run in constant time O(1) regardless of the array size. This solution aligns well with Microsoft's focus on efficient resource utilization in backend services, ensuring no unnecessary memory allocation occurs during runtime while handling high-throughput data streams.