Unit 1 · Lesson 816 minAcademic review pending

Why fairness needs a queue, not a stack

Simulating round-robin service shows FIFO order in action — and shows why LIFO order would make it unfair.

Choose explanation

After this lesson

You should be able to

Simulate a service queue using enqueue and dequeue.
Re-enqueue a partially served item to model round-robin service.
Explain why a queue, not a stack, keeps the service order fair.

Try it before you read

Try it live

queue.cfront=— rear=—

Queue is empty.

Round-robin: everyone gets a turn, in order

A counter serves customers one time unit at a time. If a customer needs more time, they go to the back of the line rather than keep the counter to themselves — everyone waiting gets a fair turn before anyone is served twice.

This is exactly enqueue and dequeue: dequeue the front customer, serve one unit, and if they are not done, enqueue them again at the back before moving to whoever is now at the front.

Why a stack would make this unfair

Swap the queue for a stack and re-serving the same customer would push them right back onto the top — they would be served again immediately, forever, while everyone else waited. LIFO order is exactly wrong for fairness, which is a useful way to see why the structure you choose is not a neutral decision.

This is the same lesson as Lesson 6's bracket checker, from the other direction: there, LIFO order was exactly right because nesting order mattered. Here, FIFO order is exactly right because arrival order mattered. The structure must match what the problem actually needs.

Not done? Back of the line. Done? Stay out.

void serve_round_robin(int customer[], int remaining[], int n)
{
    int data[100], front = 0, rear = -1, count = 0;

    for (int i = 0; i < n; i++) { rear = (rear + 1) % 100; data[rear] = i; count++; }

    while (count > 0) {
        int i = data[front];
        front = (front + 1) % 100; count--;

        remaining[i]--;
        printf("Serving customer %d, %d unit(s) left\n", customer[i], remaining[i]);

        if (remaining[i] > 0) {
            rear = (rear + 1) % 100; data[rear] = i; count++;   /* back of the line */
        } else {
            printf("Customer %d done\n", customer[i]);
        }
    }
}

Try it yourself

Simulate round-robin service for four customers needing 3, 1, 4, 2 time units respectively, and print the order in which they finish.

Need a hint?

Track a separate remaining[] array alongside the queue of customer indices, and decrement it each time that customer is served one unit.

Check the worked solution

Customer 2, who only needs 1 unit, finishes first even though customer 3 arrived after them and needs the most time overall — that is round-robin fairness working exactly as intended, and it is a direct consequence of FIFO order rather than something coded in specially.

#include <stdio.h>
#define N 4
#define CAPACITY 100

int main(void)
{
    int customer[N]  = {1, 2, 3, 4};
    int remaining[N] = {3, 1, 4, 2};

    int data[CAPACITY], front = 0, rear = -1, count = 0;

    for (int i = 0; i < N; i++) {
        rear = (rear + 1) % CAPACITY;
        data[rear] = i;
        count++;
    }

    while (count > 0) {
        int i = data[front];
        front = (front + 1) % CAPACITY;
        count--;

        remaining[i]--;

        if (remaining[i] > 0) {
            rear = (rear + 1) % CAPACITY;
            data[rear] = i;
            count++;
        } else {
            printf("Customer %d finished\n", customer[i]);
        }
    }

    return 0;
}

Quick check

If round-robin service used a stack instead of a queue for re-serving unfinished customers, what would happen?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Queue Applications

Maps to course outcomes CO1, CO3, CO4.