Circular queue: full/empty conditions and index arithmetic

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Why does a linear array queue waste space? from Lesson 3.3.1
• Evaluate the postfix 5 3 4 * + 2 -. from Lesson 3.2.2
• What is -7 % 5 in C, and what is (−7 + 5) % 5? from Lesson 1.1.2

1 · The Hook

🎣

A round table at a wedding seats guests in order; when the last chair is reached, seating continues at chair 0 if it has been freed. Bending the array into a ring lets a queue reuse every slot. The only puzzle left: when front and rear meet, is the ring full or empty?

2 · Predict First

🤔

A circular queue in an array of 5 slots uses the rule “full when (rear + 1) % 5 == front”. How many items can it hold? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

4. One slot is always left empty so that “full” and “empty” look different.

Output

stored 4; 10 20 ; front=2 rear=1; enqueue(80) -> 0

Wrapping indices with %

Move an index forward with i = (i + 1) % N: after N − 1 comes 0. The array is now a ring.

The standard convention (one slot left empty)

front and rear start at 0. rear is the index of the last item; front is the slot just before the first item.

Capacity is N − 1: if the last slot were filled too, front == rear would hold for both full and empty.

#define N 5
int q[N];
int front = 0, rear = 0;   /* front: one slot BEFORE the first item; rear: last item */

int enqueue(int x)
{
    if ((rear + 1) % N == front) return 0;   /* full: N - 1 items */
    rear = (rear + 1) % N;
    q[rear] = x;
    return 1;
}

int dequeue(int *x)
{
    if (front == rear) return 0;             /* empty */
    front = (front + 1) % N;
    *x = q[front];
    return 1;
}

int main(void)
{
    int i, x, ok = 0;
    for (i = 1; i <= 5; i++) ok += enqueue(i * 10);
    printf("stored %d; ", ok);
    dequeue(&x); printf("%d ", x);
    dequeue(&x); printf("%d ", x);
    enqueue(60);
    enqueue(70);
    ok = enqueue(80);
    printf("; front=%d rear=%d; enqueue(80) -> %d\n", front, rear, ok);
    return 0;
}

The counter convention

Another common version keeps front = index of the first item and a separate count. Then full is count == N (all N slots usable), empty is count == 0, and rear = (front + count − 1) % N. Questions state which convention they use; check carefully.

Tracing

Keep a row per operation with front, rear and the ring’s contents. Watch the wrap: with N = 6, rear goes 4 → 5 → 0 → 1.

4 · Visual

N = 5 after: enqueue 10, 20, 30, 40 (the 5th enqueue failed), dequeue 10, 20, enqueue 60, 70. front = 2 (the empty slot before 30), rear = 1. Now (1 + 1) % 5 == 2 == front: full with 4 items.

N = 6, front = rear = 0. Operations: enqueue 1 2 3 4, dequeue, dequeue, enqueue 5 6 7, dequeue

op        front rear   ring [0..5]            note
start       0    0     _ _ _ _ _ _            empty: front == rear
enq 1..4    0    4     _ 1 2 3 4 _
deq, deq    2    4     _ _ _ 3 4 _            removed 1, 2
enq 5       2    5     _ _ _ 3 4 5
enq 6       2    0     6 _ _ 3 4 5            rear wraps 5 -> 0
enq 7       2    1     6 7 _ 3 4 5            now (1+1)%6 == 2 == front: full
deq         3    1     6 7 _ _ 4 5            removed 3; items = (1-3+6)%6 = 4

One row per operation; rear and front wrap with % N.

5 · Worked Examples

Example 1 Easy

N = 8, front = 5, rear = 2 (standard convention). How many items are in the queue? Is it full?

Solution

(2 − 5 + 8) % 8 = 5 items. Full would need (2 + 1) % 8 == 5: no.

Example 2 Medium

Trace the table in the Visual section: N = 6, enqueue 1 2 3 4, dequeue ×2, enqueue 5 6 7, dequeue. Final front and rear?

Solution

front = 3, rear = 1, with 4 items (4, 5, 6, 7).

Example 3 GATE

What does this print?

#define N 5
int q[N];
int front = 0, rear = 0;   /* front: one slot BEFORE the first item; rear: last item */

int enqueue(int x)
{
    if ((rear + 1) % N == front) return 0;   /* full: N - 1 items */
    rear = (rear + 1) % N;
    q[rear] = x;
    return 1;
}

int dequeue(int *x)
{
    if (front == rear) return 0;             /* empty */
    front = (front + 1) % N;
    *x = q[front];
    return 1;
}

int main(void)
{
    int i, x, ok = 0;
    for (i = 1; i <= 5; i++) ok += enqueue(i * 10);
    printf("stored %d; ", ok);
    dequeue(&x); printf("%d ", x);
    dequeue(&x); printf("%d ", x);
    enqueue(60);
    enqueue(70);
    ok = enqueue(80);
    printf("; front=%d rear=%d; enqueue(80) -> %d\n", front, rear, ok);
    return 0;
}

Solution

The 5th enqueue fails (capacity 4). Dequeues give 10 and 20 (front = 2). 60 goes to index 0 and 70 to index 1 (rear wraps). Now (1 + 1) % 5 == 2 == front, so enqueue(80) returns 0.

Output

stored 4; 10 20 ; front=2 rear=1; enqueue(80) -> 0

6 · GATE Traps

⚠️

• With the one-empty-slot convention, capacity is N − 1, not N.
• Empty: front == rear; full: (rear + 1) % N == front — not rear == N − 1.
• Item count: (rear − front + N) % N; add N before % to avoid a negative result in C.
• In this convention front points to the slot before the first item; in others it points to the first item. Read the question.
• Increment with % N on both front and rear.

8 · Memory Hook

🧠

“Leave one chair empty at the round table.” Then the host can tell a full table (rear right behind front) from an empty one (rear standing on front).

9 · Connect the Dots

Lessons 3.3.1–3.3.2 built FIFO queues on arrays. Variations on the theme are common: adding and removing at both ends, serving by priority instead of arrival, and building one structure from another. Next lesson answers: what are deques and priority queues, and how can two stacks behave like a queue?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markFull

In a circular queue of size N (front before first item, rear at last item), the full condition is:

• (A) rear == N − 1
• (B) front == rear
• (C) (front + 1) % N == rear
• (D) (rear + 1) % N == front

Q2NAT1 markCount

N = 10, front = 7, rear = 3 (standard convention). How many items?

Numerical answer: ________

Q3NAT1 markCapacity

An array of 12 slots implements a circular queue with the one-empty-slot rule. How many items can it hold?

Numerical answer: ________

Q4MCQ2 marksTrace

N = 5, front = rear = 0. Enqueue 1..5, dequeue twice, enqueue 6 and 7. What front and rear does the program of Example 3 print?

• (A) front 0, rear 2
• (B) front 2, rear 1
• (C) front 3, rear 1
• (D) front 2, rear 0

Q5MSQ2 marksConventions

Which are true?

• (A) With the one-empty-slot rule, front == rear means empty.
• (B) Indices advance with (i + 1) % N.
• (C) With a separate count, all N slots can be used.
• (D) (rear − front) % N always gives the item count in C.

11 · Rule Card

• Advance: i = (i + 1) % N.
• Standard: front = rear = 0 start; enqueue rear = (rear+1)%N; dequeue front = (front+1)%N.
• Empty: front == rear; full: (rear + 1) % N == front; capacity N − 1.
• Items: (rear − front + N) % N.
• Counter variant: full count == N, empty count == 0.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

circular queuewrap-around index (% N)one-empty-slot conventionfull / empty conditionsitem count formula

13 · Answer Vault