Queues: FIFO and a bounded circular array

Prerequisites and goal

Know integer variables, assignment, comparisons, if, return, function calls, fixed-size arrays and zero-based indices. This lesson introduces the small amount of pointer syntax required for a returned output value. The earlier lesson, Recursion over a bounded array prefix, supplies the bounded-array context. This lesson uses those indexing ideas; recursive code is not needed for these queue operations. A queue has a different removal rule from a call stack. First explain FIFO, then trace a four-slot array through wraparound without confusing physical index order with logical order.

This is a narrow GATE CS foundation lesson. It does not cover linked queues, deques, priority queues, concurrent queues, amortized analysis or a complete data-structures course.

What the abstract queue promises

A queue maintains an ordered sequence. Enqueue adds a value at the rear. Dequeue removes and reports the value at the front. FIFO means first in, first out: among items still present, the earliest enqueued item leaves first. For enqueue(10), enqueue(20), dequeue, the removal is 10 and the remaining sequence is [20]. A stack's last-in-first-out removal would be different.

Think of numbered service tickets handed out in arrival order. The earliest waiting ticket is served next, and a newcomer joins the rear. The analogy models order only; real people may leave or be prioritized, which this queue does not support. A circular array is a storage technique, not a rule that lets a new arrival jump ahead.

Explicit contract and state meaning

The teaching program uses C11 and one fixed array of exactly four int slots. There is no allocation or resizing. Values are ordinary representable int values; the code copies them and never adds them. The demonstration uses 10 through 60. Operations run sequentially, and callers do not edit data, front or size directly.

• CAPACITY is 4, so legal physical indices are 0, 1, 2, 3.
• front is always between 0 and 3. When nonempty it identifies the next value to remove. When empty it is the position where the next enqueue will insert.
• size is a count: 0 <= size <= 4. Empty means size == 0; full means size == 4. All four slots can hold live items.
• The logical item numbered k from the front lives at data[(front + k) % CAPACITY], for 0 <= k < size.
• The insertion index is (front + size) % CAPACITY, but enqueue must check full BEFORE writing there.
• dequeue receives the address of an existing writable int output variable, separate from queue storage and control variables. That variable remains alive during the call. Null, invalid or aliased output pointers are outside the contract; these are not automatically checked.
• Both functions return status: 1 for success, 0 for failure. The removed value travels through the output variable, not through the status. On failure all queue slots and both control variables stay unchanged; an empty dequeue also leaves the output variable unchanged.

With these bounds front + size is at most 7 and front + 1 is at most 4, so index arithmetic fits even the minimum C int range. Modulo by the positive constant 4 gives indices 0 through 3. A general queue with huge sizes would need its own arithmetic analysis.

From rules to a complete C11 program

Enqueue first rejects a full queue, writes the first free logical position and increments size. Dequeue first rejects an empty queue, copies its front value to the output variable, advances front with wraparound and decrements size. It does not shift the other elements or erase the removed slot.

#include <stdio.h>

#define CAPACITY 4

int data[CAPACITY] = {0};
int front = 0;
int size = 0;

int enqueue(int value) {
    if (size == CAPACITY) {
        return 0;
    }
    int insertion = (front + size) % CAPACITY;
    data[insertion] = value;
    size = size + 1;
    return 1;
}

int dequeue(int *out) {
    if (size == 0) {
        return 0;
    }
    *out = data[front];
    front = (front + 1) % CAPACITY;
    size = size - 1;
    return 1;
}

int main(void) {
    int removed = -1;
    enqueue(10);
    enqueue(20);
    enqueue(30);
    dequeue(&removed);
    printf("removed=%d\n", removed);
    enqueue(40);
    enqueue(50);
    int full_status = enqueue(60);
    printf("front=%d size=%d full_enqueue=%d\n", front, size, full_status);
    while (dequeue(&removed)) {
        printf("%d ", removed);
    }
    printf("\nfront=%d size=%d\n", front, size);
    return 0;
}

The output is:

removed=10
front=1 size=4 full_enqueue=0
20 30 40 50 
front=1 size=0

The demonstration fills the queue before enqueue(60). Its returned status is stored in full_status before printing. Keeping a state-changing call in a separate statement avoids depending on the unspecified evaluation order of different printf arguments.

New syntax, read slowly

#include <stdio.h> makes the declarations of printf available. #define CAPACITY 4 gives the token CAPACITY a fixed replacement of 4. The three declarations outside functions are shared global state for this single-queue teaching example; production programs often package state differently. int data[CAPACITY] = {0} initializes all four slots to zero, but zeros are not an empty marker: size decides membership.

% is integer remainder. Here (3 + 1) % 4 is 0, so the next physical index after 3 is 0. == tests equality; = assigns. size = size + 1 stores a count one larger; size = size - 1 stores one smaller. Braces group statements. int insertion declares a local integer for that one enqueue call.

In int dequeue(int *out), the star declares out as a pointer to int, an address of an integer object. &removed supplies the address of main's variable. In *out = data[front], the star accesses that addressed variable and writes the removed value into it. C copies the address argument; following that address lets the helper modify the caller's variable. This is not an array copy. No pointer arithmetic is used.

int main(void) is the program entry function with no parameters. printf's %d formats an int; \n is a newline. while (dequeue(&removed)) calls dequeue for each test: status 1 runs the body, status 0 stops it. The final failed test does not print a stale output value. return 0 in main denotes normal program completion; it has a different role from the queue helpers' failure status. The early return ends its function immediately.

The downloadable queue.c has #ifndef QUEUE_TEST and #endif around main, solely so queue_test.c can define QUEUE_TEST and reuse the same implementation with a test main. The displayed complete program above does not need that test-only conditional.

Worked trace: indices wrap, FIFO does not

Each row shows state AFTER the operation. A dash denotes a slot not currently in the queue, even if an old integer remains physically stored.

For enqueue 50, (front + size) % 4 = (1 + 3) % 4 = 0 using the state BEFORE insertion. Slot 0 is reused but 50 is newest. On the next full enqueue, the candidate index would be (1 + 4) % 4 = 1, the occupied front slot. The guard prevents overwriting 20.

Drain the full state: dequeue returns outputs 20, 30, 40, 50, and (front,size) becomes (2,3), (3,2), (0,1), (1,0). Then an empty dequeue returns status 0 and preserves the last output 50. Enqueue 70 into this empty state writes slot (1+0)%4 = 1 and produces (1,1). There is no requirement to reset front to 0 when the queue becomes empty.

Why it works and what costs a step

Before a nonfull enqueue, the live logical offsets are 0 through size-1. Offset size names the next free slot because fewer than four consecutive circular positions are occupied. Writing there appends without disturbing existing order. Incrementing size adds exactly that item. Before a nonempty dequeue, offset 0 is valid. Advancing front maps every surviving item's old offset k to new offset k-1; decrementing size removes exactly the oldest item. Guards precede all potentially invalid membership reads or overwriting writes.

At most a fixed number of tests, assignments and arithmetic operations occur in either helper, so each enqueue/dequeue is O(1) under ordinary constant-cost int operations. Here O(1) describes a bounded amount of work independent of the item count; O(C) and O(n) describe growth proportional to capacity C and processed item count n, respectively. These are introductory growth descriptions, not a formal asymptotic-analysis proof. No shift loop is hidden. The backing storage is four slots here; in a capacity-C version it is O(C). Printing or draining n items takes O(n) operations, even though one dequeue is O(1).

Three representations: keep their conventions separate

1. Our count-based circular array: front is next removal, size is count, insertion is (front+size)%4. Empty size=0; full size=4; usable capacity four. Insertion coincides with front in both empty and full states; size distinguishes them.
2. A naive nonwrapping linear queue: keep a next-insertion index that only increases. If four slots are initially filled, then two dequeues free slots 0 and 1, but insertion still points at 4. A version that never shifts, resets or wraps cannot reuse those slots and must reject insertion at the array end. This is a limitation of that particular implementation, not the FIFO abstraction or every linear-array implementation.
3. One alternative circular convention reserves one slot: front is next removal, rear is next insertion, empty means front==rear, and full means (rear+1)%4==front. It stores at most three items in four physical slots. This convention has no size counter here. Do not copy its full test into our count-based code: you would sacrifice a slot or misinterpret rear. Other rear definitions exist; always define the state first.

Key box

• FIFO concerns arrival and removal order, not increasing physical indices.
• Check size==4 before enqueue; check size==0 before dequeue.
• Insertion uses the old front and old size; then increment size.
• Successful dequeue advances front modulo four and decreases size.
• Stale array cells are not queue members. Stored zero is a valid item.
• Status and removed value are separate. Failed operations change neither queue state nor output.
• Our full/empty rules use a count. A reserved-slot convention has different usable capacity and tests.

Before moving on

If your answer removes the newest item, revisit FIFO. If you overwrite the front when full, move the full guard before insertion. If you read physical slots 0,1,2,3 as the logical order after wraparound, start at front and use the count. Trace empty, one item, full, failed operations, partial drain/refill and complete drain/refill before trusting an implementation.

Source and scope

This offline lesson continues the locally reviewed GATE CS programming and data-structures foundation context. It does not claim a new syllabus verification, an official previous-year question, a mock examination or full-course coverage. C11 is our teaching choice, not an assertion about an exam language version. Explanations and all six questions are original. No course year or CMS publication is assigned.

Try it first: two short exercises

Exercise 1: payload and failure are different

An empty count-based queue has front=2, size=0. Let out=99. Perform enqueue(-1), dequeue(&out), dequeue(&out). Before reading the answer, write each status, the output variable after each operation and the final (front,size).

Worked answer: enqueue succeeds with status 1 and writes -1 at (2+0)%4=2; out remains 99 and state becomes (2,1). First dequeue returns status 1 and writes -1 into out, giving (3,0). Second dequeue returns status 0; out stays -1 and state stays (3,0). Negative payload -1 is not a failure signal.

Exercise 2: reuse a slot without reordering

Our queue has front=3, size=3 and logical contents [11,22,33]. Write the occupied physical indices. Then trace dequeue, enqueue(44), enqueue(55), enqueue(66). Predict statuses, removed output, final front/size and logical order.

Worked answer: initially indices 3,0,1 hold 11,22,33. Dequeue returns status 1 and output 11, giving front=0,size=2. Enqueue 44 writes index 2, giving size=3; enqueue 55 writes index 3, giving size=4. Their statuses are 1 and 1. Enqueue 66 returns 0 without change. Final (front,size)=(0,4), logical order [22,33,44,55]. Slot 3 now holds the newest member 55, not the removed oldest 11.

Six original single-choice questions

Choose exactly one option in each question. Use only the stated convention.

1

An initially empty queue performs enqueue(8), enqueue(3), dequeue, enqueue(5), dequeue. What are the two removed values, in order?

A. 3, 5 B. 8, 3 C. 8, 5 D. 3, 8

2

In our capacity-4 count-based queue, front=3, size=2 and logical contents are [7,9]. A successful enqueue(6) writes which index and leaves which (front,size)?

A. Index 1; (3,3) B. Index 2; (3,3) C. Index 1; (0,3) D. Index 3; (3,3)

3

Our queue has front=2, size=4. What must enqueue(99) do?

A. Overwrite data[2] and return 1. B. Return 0 and set size to 0. C. Return 1 because index 0 can always be reused. D. Return 0 without changing any slot, front or size.

4

Our queue has front=3, size=1 and data[3]=0. out starts at 77. Call dequeue(&out) twice, recording each status. What is (first status, second status, final out, final front, final size)?

A. (0,0,77,3,1) B. (1,0,77,0,0) C. (1,0,0,0,0) D. (1,1,0,1,-1)

5

Two queues each use four physical array slots. One is our front+size version. The other reserves one slot with front=next removal, rear=next insertion, empty front==rear and full (rear+1)%4==front. Their maximum live item counts are, respectively:

A. 4 and 4 B. 4 and 3 C. 3 and 4 D. 3 and 3

6

A naive nonwrapping four-slot linear queue fills indices 0 through 3. Two dequeues follow, leaving indices 0 and 1 free and next-insertion index 4. This version never shifts, resets or wraps. Which statement is correct?

A. It must reject enqueue at the array end despite the two freed slots. B. It can write data[4] because there are two free slots elsewhere. C. Every FIFO queue must now be full. D. A circular implementation would remove the newest item first to reuse space.

Answers and worked option feedback

1: B

A is incorrect. Removing 3 and then 5 follows the most recent arrival, a stack-like rule.

B is correct. States are [8], [8,3], [3], [3,5], [5]. The removals are 8 then 3.

C is incorrect. After removing 8, the older waiting 3 stays ahead of the newly added 5.

D is incorrect. The first removal cannot be 3 while the earlier 8 is still waiting.

2: A

A is correct. Items 7 and 9 occupy indices 3 and 0. (3+2)%4=1 is free. Enqueue increments size only, giving (3,3).

B is incorrect. Index 2 skips the required next logical slot 1; size alone is not the insertion index after wraparound.

C is incorrect. Enqueue does not advance front; that would discard the oldest item from the logical sequence.

D is incorrect. Index 3 holds the front value 7. Overwriting it would lose an existing item.

3: D

A is incorrect. (2+4)%4=2 is occupied by the oldest item; the full guard must prevent that write.

B is incorrect. Failure does not empty the queue; all four current members remain.

C is incorrect. Wrapping reuses only free slots, and size=4 means none is free.

D is correct. The first guard sees size==CAPACITY and returns 0 before any write or counter update.

4: C

A is incorrect. A stored zero is a valid item; size=1 means the first dequeue succeeds.

B is incorrect. The successful first call writes 0 into out. Failure of the second call preserves this 0, not the original 77.

C is correct. First call returns status 1, writes value 0, wraps front from 3 to 0 and makes size 0. Second call returns 0 without changes.

D is incorrect. The empty guard prevents a second successful removal, another front advance and negative size.

5: B

A is incorrect. The reserved-slot version must leave one of its four slots unused to distinguish full from empty using only those indices.

B is correct. The count separates size=0 from size=4, so all four slots work. The alternative deliberately leaves one slot unused and holds three.

C is incorrect. It reverses the capacities; it is the reserved-slot convention that sacrifices a slot.

D is incorrect. Our explicit size count does not require sacrificing a slot.

6: A

A is correct. Its next write position is beyond index 3 and its specified rules cannot reclaim earlier slots. A circular implementation could reuse a freed slot while preserving FIFO.

B is incorrect. data[4] is outside a four-slot array. Free cells elsewhere do not make this index valid.

C is incorrect. Only two items remain. This particular storage policy cannot reuse space; the queue abstraction does not require that limitation.

D is incorrect. Circular storage preserves oldest-first removal. Wraparound changes indices, not the FIFO rule.