21

21 — Practice solutions

← Questions

These are independently written explanations, not an official marking scheme.

21A

After operation	front	rear	size	Logical order
Enqueue A,B,C,D	0	3	4	A,B,C,D
Dequeue A	1	3	3	B,C,D
Dequeue B	2	3	2	C,D
Enqueue E	2	0	3	C,D,E
Enqueue F	2	1	4	C,D,E,F

Answer: removed A,B; physical array [E,F,C,D]; logical order [C,D,E,F]; front2, rear1, size4. Enqueue G returns False with unchanged state.

Why: rear wraps after3 and reuses vacated cells0 and1. When size reaches4, all cells are live. Overwriting index2 with G would replace C, the next order due to be served.

Reasoning

This asks for both storage order and service order, plus state. Work with the count-based convention stated in the question. Do not switch to the original paper’s −1 empty sentinel mid-trace.

21B

Requires the Node class from Chapter19.

class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None
 
    def enqueue(self, item):
        new = Node(item)                # Node.next initially points to None.
        if self.rear is None:
            self.front = new           # First node is also the front.
        else:
            self.rear.next = new       # Preserve the existing chain.
        self.rear = new                # New node is now last in either case.
 
    def dequeue(self):
        if self.front is None:
            raise IndexError("queue empty")
        item = self.front.data         # Save the item being served.
        self.front = self.front.next    # Bypass the old front node.
        if self.front is None:
            self.rear = None           # No last node remains when empty.
        return item
 
    def items(self):
        result = []
        current = self.front           # Local pointer; do not advance front.
        while current is not None:
            result.append(current.data)
            current = current.next
        return result

Trace: after enqueue X, front and rear reference the same X node. Dequeue returns X and makes both None. Enqueue Y sets both to the new Y node. The removed X node is not reconnected.

Why the reset matters: if rear still referenced X after removal, the next enqueue would take the nonempty branch and link Y after the removed node. Front could remain None, so the supposedly enqueued Y would be unreachable through the queue’s front.

Reasoning

Enqueue must connect the new node differently depending on whether a last node already exists. Dequeue always advances front, but removing the only node also invalidates rear. items traverses with a local variable because it must leave the queue unchanged.

21C

Resulting FIFO order: [103,104,105,106]. Dequeue each item and push it onto a stack until the queue is empty. Then pop each stack item and enqueue it. New order: [106,105,104,103]. The stack removes the most recently pushed item first, so it reverses order. Repeating the complete process reverses again, restoring the original sequence.

def reverse_queue(queue):
    # This version uses the count-based CircularQueue interface.
    stack = []
    while queue.size > 0:
        stack.append(queue.dequeue())  # Last original item ends on top.
    while len(stack) > 0:
        queue.enqueue(stack.pop())     # Last original item returns first.

The same number of items is reinserted, so its original capacity suffices. If a task asks to preserve the original queue while returning a reversed copy, this mutating function does not satisfy that different contract.

Reasoning

The question permits changing this queue. A stack is useful because the last dequeued item must become the first re-enqueued item. Transfer all items before transferring back; alternating one push and one pop would simply reinsert items without obtaining the desired reversal.

21D

Decode the supplied interface. Capacity8 is fixed; there is no supplied size attribute; empty pointers are −1; enqueue returns True/False; serve returns the removed item or False; printQueue must print without removing. The question asks for pseudocode, so the answer below uses explicit assignments and block endings. orders, start and end denote the current object’s attributes.

Derive the cases. A full queue blocks order before any assignment. First insertion must initialise start. Serve saves the old front value; a singleton resets both pointers. Print follows a temporary index and must include the last item before stopping.

(a) order(food) — original allocation 5 marks

FUNCTION order(food)
    IF (end + 1) MOD 8 = start THEN
        RETURN False                 // Reject without overwriting an order.
    ENDIF
    IF start = -1 THEN
        start ← 0                    // First order establishes the front.
        end ← 0
    ELSE
        end ← (end + 1) MOD 8         // Advance with wraparound.
    ENDIF
    orders[end] ← food
    RETURN True
ENDFUNCTION

In the empty state, (−1+1) MOD8 is0, which differs from start=−1, so the full test correctly allows the first insertion.

(b) serve() — original allocation 4 marks

FUNCTION serve()
    IF start = -1 THEN
        RETURN False
    ENDIF
    food ← orders[start]             // Preserve the value to return.
    IF start = end THEN
        start ← -1                   // The only remaining item was removed.
        end ← -1
    ELSE
        start ← (start + 1) MOD 8
    ENDIF
    RETURN food
ENDFUNCTION

Clearing the old array cell is optional in this representation: the pointers define live membership. Returning False is the paper’s specified failure result, not an exception.

(c) printQueue() — original allocation 3 marks

PROCEDURE printQueue()
    IF start <> -1 THEN
        position ← start
        OUTPUT orders[position]      // Includes a singleton queue.
        WHILE position <> end
            position ← (position + 1) MOD 8
            OUTPUT orders[position]
        ENDWHILE
    ENDIF
ENDPROCEDURE

Printing before the first condition check prevents omitting a singleton. The loop advances until it has also printed the item at end. It never changes start/end. A plain range from start to end fails when the logical sequence wraps through index0.

(d) suitability — original allocation 2 marks

A stack is LIFO, so it would serve the newest order before earlier unserved orders. The stall needs FIFO to serve customers in arrival order.

Check the answer without a computer

Case	Expected behaviour under this convention
Initially start=end=−1	serve returns False; printQueue outputs nothing.
One order at index0	serve returns that order and resets both pointers to−1.
start6, end1	print visits indices6,7,0,1.
start2, end1	Full, since next rear position2 is occupied by the front; order returns False.

The part totals above are from the original paper. The derivation and answers are independently written; they are not a claim about how its official scheme distributes marks within each part.

21E

After operation	front	rear	Live order / outcome
Enqueue A,B,C	0	2	A,B,C
Dequeue A	1	2	B,C; returns A
Attempt D	1	2	False; B,C unchanged
Dequeue B	2	2	C; returns B
Dequeue C	0	−1	Empty; returns C; resets pointers
Enqueue D	0	0	True; D

The linear policy does not wrap or compact, so rear reaching the final index prevents insertion even with a vacated earlier cell. After emptying it resets. The circular queue instead reuses index 0 for D while B,C remain, yielding logical order B,C,D.