Circular-queue questions are usually lost on one ambiguity: if front == rear, is the queue empty or full? The answer depends on the implementation convention. Mixing two valid conventions produces an invalid capacity or an off-by-one answer.
The two conventions differ in how they distinguish an empty ring from a full one when pointers wrap. Once the pointers wrap in front of you, the formulas stop feeling arbitrary.
1. Why a circular queue exists
In a simple array implementation of a linear queue, rear moves only towards the last index. Suppose an array has indices 0 through 4. After five enqueues, rear reaches the end. If two elements are then dequeued, indices 0 and 1 are free, but a naive linear queue still cannot enqueue at the end.
Shifting every live element towards index 0 would reclaim the space, but each shift costs time. A circular queue solves the problem without shifting. It treats the position after the last index as index 0, so freed cells can be reused.
The array does not physically become circular. Only the index calculation wraps.
2. The circular idea in one line
For an array of size N, move one position with modulo arithmetic:
next(i) = (i + 1) % N
If N = 5, then the next index after 3 is 4, and the next index after 4 is (4 + 1) % 5 = 0.
On enqueue, rear advances by this rule. On dequeue, front advances by the same rule. The remaining design question is how the code distinguishes a completely empty ring from a completely full one.
3. The two conventions and their formulas
Convention A: sacrifice one slot
Let front point to the next element to remove and rear point to the next slot where an element would be inserted.
Empty condition:
front == rearFull condition:
(rear + 1) % N == frontUsable capacity:
N - 1Number of elements:
(rear - front + N) % N
The unused slot separates the full state from the empty state. That is why a physical array of size N holds at most N - 1 live elements under this convention.
Convention B: keep a count
Store a separate variable count and update it after every successful operation.
Empty condition:
count == 0Full condition:
count == NUsable capacity:
N
Here front == rear can occur in both the empty and full states. The extra count resolves the ambiguity, so no array slot has to be sacrificed.
Both conventions are correct. The mistake is to take the capacity N from Convention B and combine it with the full test from Convention A.
4. Fully worked example: size-5 ring, Convention A
Set N = 5, with indices 0,1,2,3,4. Initially, front = rear = 0.
The queue is empty, and its usable capacity is N - 1 = 4. For an enqueue, first test whether the queue is full. If it is not, write A[rear] = x and then set rear = (rear + 1) % 5. For a dequeue, read A[front] and then advance front.
Operation |
|
| Live count | Result |
|---|---|---|---|---|
Start | 0 | 0 | 0 | Empty |
Enqueue 10 | 0 | 1 | 1 |
|
Enqueue 20 | 0 | 2 | 2 |
|
Enqueue 30 | 0 | 3 | 3 |
|
Dequeue | 1 | 3 | 2 | Returns 10 |
Enqueue 40 | 1 | 4 | 3 |
|
Enqueue 50 | 1 | 0 | 4 |
|
Enqueue 60 | 1 | 0 | 4 | Rejected as full |
Check the wrapped state carefully. After inserting 50, rear = (4 + 1) % 5 = 0.
The live-count formula gives (rear - front + N) % N = (0 - 1 + 5) % 5 = 4.
The full test agrees: (rear + 1) % 5 = (0 + 1) % 5 = 1 = front.
Therefore, enqueueing 60 must be rejected. The logical order is 20,30,40,50, occupying indices 1,2,3,4. Index 0 may still contain the old bits for 10, but 10 was dequeued. That cell is logically free and currently serves as the sacrificed slot.
The operation count also confirms the live-element total. Three successful enqueues occurred before the dequeue, one element left, and two more successful enqueues followed. Thus 3 - 1 + 2 = 4 live elements remain. The pointer formula and the operation count match.
5. The pointer-arithmetic questions
When rear has wrapped and is numerically smaller than front, the plain difference rear - front is negative. Adding N before taking modulo produces the correct circular distance: (rear - front + N) % N.
In the final state above, 0 - 1 = -1, but (-1 + 5) % 5 = 4.
For a question asking where repeated moves land, add the number of moves and reduce modulo N. Starting from index 3 in a size-5 array, four advances land at (3 + 4) % 5 = 7 % 5 = 2.
Be careful about wording. The position of the k-th inserted item can differ by one from the pointer value after k insertions because rear often points to the next free slot, not the last occupied slot.
6. Deque: the double-ended queue
A deque, pronounced "deck", allows both insertion and deletion at both ends:
insertFrontinsertReardeleteFrontdeleteRear
An input-restricted deque permits insertion at only one end but deletion at both ends. An output-restricted deque permits deletion at only one end but insertion at both ends.
Trace a small example:
Start with
[].insertRear(1)gives[1].insertFront(2)gives[2,1].insertRear(3)gives[2,1,3].deleteFront()removes2, leaving[1,3].
A deque describes which ends support operations. A circular queue describes how an array queue reuses positions through wraparound. A deque can itself be implemented with a circular array, but the two terms are not synonyms.
7. How GATE tests this and the traps
Typical questions ask for the correct full condition, the maximum number of elements in a size-N array, the pointer values after a trace, or the type of a restricted deque. The code in the question tells you which convention applies.
Before solving, write three facts at the side: what front points to, what rear points to, and whether the implementation stores a count. Then avoid these traps:
Reporting capacity
Nwhen one slot is sacrificed. The correct capacity isN - 1.Forgetting
+Nin the circular-distance formula.Treating stale array data as a live queue element.
Moving a pointer before reading or writing when the pseudocode moves it afterwards.
Confusing double-ended operations with circular storage.
Confirm the current Algorithms and Data Structures syllabus and paper pattern on the official GATE 2027 portal. About 1,500 Data Structures practice questions cover the wider stack-and-queue area, including these pointer conditions.
8. The short version and your next step
Wrap every move modulo N. With a sacrificed slot, empty means front == rear, full means (rear + 1) % N == front, capacity is N - 1, and the live count is (rear - front + N) % N. With a stored count, capacity is N.
For the broader LIFO/FIFO, implementation and application foundation, revisit stacks and queues explained. For circular-array questions, use the full and empty conventions plus the pointer trace above. For deque questions, classify the permitted ends before applying an operation. Next, solve the Data Structures stacks and queues MCQs. Use GATE Guidance by Sanchit Sir for the surrounding subject and the GATE Test Series for timed traces, all within the GATE category.
