278. Implement a Circular Queue

Implement a circular queue with a fixed capacity k. Simulate m operations, each 'ENQUEUE x', 'DEQUEUE', 'FRONT', or 'REAR'. On ENQUEUE, if the queue is already holding k elements, print 'OVERFLOW' instead of enqueuing; otherwise enqueue silently (no output). On DEQUEUE, print the removed value, or 'EMPTY' if the queue is empty. On FRONT/REAR, print the current front/rear value, or 'EMPTY' if the queue is empty. Print one result per line, in the order DEQUEUE/FRONT/REAR/overflowing-ENQUEUE operations occurred.

Input: The first line contains an integer k, the queue's capacity. The second line contains an integer m, the number of operations. Each of the next m lines contains one operation: 'ENQUEUE x', 'DEQUEUE', 'FRONT', or 'REAR'. Output: Print one line per DEQUEUE/FRONT/REAR/overflowing-ENQUEUE operation, in the order they occur - the relevant value, 'EMPTY', or 'OVERFLOW'.

1 <= k <= 10^5, 1 <= m <= 10^5

Without a separate count variable, front == rear is ambiguous - it could mean 'completely empty' OR 'completely full', depending on history; tracking count explicitly removes that ambiguity entirely.

Build a queue with a fixed maximum size that cleverly REUSES freed-up space at the front instead of needing an ever-growing array. Brute force: Use a regular (non-circular) array-backed queue and just shift every remaining element left by one position every time you dequeue - this works but costs O(n) per dequeue, since every remaining element has to physically move. Optimised: By tracking front/rear indices that WRAP AROUND the fixed array (using modulo arithmetic) instead of physically shifting elements, both enqueue and dequeue become O(1) - the array's 'used' region conceptually rotates around the fixed-size buffer instead of ever needing to shift.

Store elements in a plain resizable array/list. ENQUEUE appends to the end (checking the current size against k first and printing OVERFLOW if already full), and DEQUEUE removes the element at index 0, which requires shifting every remaining element one position to the left so the array stays contiguous. FRONT and REAR simply read the first/last element. This is correct and simple, but every DEQUEUE costs O(k) due to the shift, making it inefficient for many operations. Time: O(k) per dequeue, O(1) per other op Space: O(k)

Represent the queue as a doubly linked list with head and tail pointers and a running size counter compared against k. ENQUEUE appends a new node at the tail in O(1), DEQUEUE removes the head node in O(1), and FRONT/REAR just read the head/tail node's value, all without ever shifting existing elements. This removes the O(k) shifting cost of the array approach, at the price of extra per-node pointer memory overhead compared to a plain fixed array. Time: O(1) per operation Space: O(k)

Allocate one fixed array of size k up front, and track a front index, a rear index, and a count of currently stored elements. ENQUEUE writes at (rear + 1) % k and advances rear (mod k) if count < k, else prints OVERFLOW; DEQUEUE reads at front and advances front (mod k) if count > 0. Keeping an explicit count avoids the classic ambiguity of front == rear meaning either empty or full. Every operation is O(1) with no shifting and no pointer overhead beyond three integers, making this the most memory- and cache-efficient implementation. Time: O(1) per operation Space: O(k)

1. Keep a fixed-size backing array, plus a front index, a rear index, and a running count of how many elements are currently stored. 2. ENQUEUE checks if the count already equals the fixed capacity - if so, report OVERFLOW; otherwise place the new value at the rear index and advance the rear index, WRAPPING back to 0 if it goes past the array's end. 3. DEQUEUE checks if the count is 0 - if so, report EMPTY; otherwise remove the value at the front index and advance the front index, also wrapping around if needed. 4. FRONT/REAR just report the current front/rear values without moving anything, or EMPTY if the queue has no elements.

Time: O(1) for every single operation (ENQUEUE, DEQUEUE, FRONT, REAR) - no shifting of elements ever happens, regardless of how full the queue is. Space: O(k), a single fixed-size array sized exactly to the given capacity - no extra space grows or shrinks as operations happen.

k = 1 (capacity of one, so a second ENQUEUE immediately overflows); DEQUEUE/FRONT/REAR called on an empty queue (print 'EMPTY'); ENQUEUE once the queue already holds k elements (print 'OVERFLOW'); m and k both up to 10^5 for performance.

Be ready to explain precisely how wrap-around indexing works (`(index + 1) % capacity`) and why tracking a separate COUNT (not just comparing front and rear indices) is the cleanest way to distinguish a genuinely empty queue from a genuinely full one, since both cases can otherwise make front and rear indices look identical.