Question 4 of 7: Waiting

Question 4: Waiting (20 marks: ADT + 3 functions, 5 marks each)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Approach. Model the waiting list as a FIFO queue capped at 100 elements, but store only the two ticket-number "pointers" (next number to hand out, next number to serve) plus a live count — not the tickets themselves — since tickets are just $1,2,\dots,100$ handed out in order and wrapping around.

1. ADT definition — 5 marks

typedef struct {
    int next_ticket;   /* next number (1..100) to hand to an arriving customer */
    int next_serve;    /* next number (1..100) to call for service */
    int count;         /* customers currently waiting, 0..100 */
} WaitingList;

void init(WaitingList* w) {
    w->next_ticket = 1;
    w->next_serve  = 1;
    w->count = 0;
}

2. Get_number — 5 marks

Refuses to issue a ticket once 100 people are already waiting; otherwise hands out the next ticket and advances the counter, wrapping from 100 back to 1.

int Get_number(WaitingList* w) {
    if (w->count >= 100) return -1;             /* room is full: error */
    int n = w->next_ticket;
    w->next_ticket = (w->next_ticket == 100) ? 1 : w->next_ticket + 1;
    w->count++;
    return n;
}

3. get_next — 5 marks

int get_next(WaitingList* w) {
    if (w->count == 0) return -1;                /* nobody waiting: error */
    int n = w->next_serve;
    w->next_serve = (w->next_serve == 100) ? 1 : w->next_serve + 1;
    w->count--;
    return n;
}

4. num_waiting — 5 marks

int num_waiting(WaitingList* w) {
    return w->count;
}

Every operation here is $O(1)$ precisely because the ADT never stores the tickets themselves, only two rotating pointers and a count — there is nothing to search or shift when a customer arrives or is served. This matters in a real front-desk system: a naive design that kept an actual array or linked list of "currently waiting" ticket numbers would still need $O(1)$ insert-at-back and remove-from-front, but would tempt an implementer into an $O(n)$ linear search whenever num_waiting or a "is ticket K still waiting" query was added later, whereas the counter-based design keeps every future extension just as cheap.