Computational Thinking and Data Structures: Question 8

Syllabus 10.4

Structured AS 10 marks

A university's network print server must process print jobs from students in the exact order they are submitted: the job submitted first must always be printed first.

(a) State which abstract data type, a stack or a queue, should be used to store the waiting print jobs so that they are processed in the order described above, and justify your answer by referring to the order in which jobs are added and removed. [2]

(b) The print server implements this abstract data type, named PrintQueue, using a 1D array of up to 5 elements, DECLARE PrintQueue : ARRAY[1:5] OF STRING, together with two integer pointer variables: Front (the array index of the job at the front of the queue, next to be printed) and Rear (the array index of the job most recently added). Both Front and Rear start at 0, meaning PrintQueue is empty. Starting from this empty state, the following operations occur, in order:

ENQUEUE "Report1"
ENQUEUE "Report2"
ENQUEUE "Report3"
DEQUEUE
ENQUEUE "Report4"
DEQUEUE

Complete a trace table showing the value of Front, the value of Rear, and the contents of PrintQueue after each of these six operations. [5]

(c) State which print job would be produced if DEQUEUE were called one more time, immediately after the six operations above. [1]

(d) Front and Rear in this implementation only ever increase, they never wrap back around to the start of the array. State one limitation this causes, illustrating your answer with a specific example based on the array PrintQueue. [2]

Show worked solution Hide worked solution

Part (a): Stack or queue?

Print jobs must be printed in the exact order they are submitted: the job submitted first must always be printed first. This is a first-in, first-out (FIFO) access pattern. The earliest job added is the first one removed. That is precisely the defining behaviour of a queue.

A stack would be the wrong choice here, because a stack is last-in, first-out (LIFO). It would print the most recently submitted job first, which does not match the order described.

[2 marks]: [1] for stating “queue”, [1] for justifying it with reference to FIFO order (the job waiting longest is removed first).

Part (b): Tracing ENQUEUE and DEQUEUE with Front and Rear

ENQUEUE increases Rear by 1 and stores the new value at PrintQueue[Rear] (and, if the queue was previously empty, also sets Front to 1). DEQUEUE reads the value currently at PrintQueue[Front] and then increases Front by 1.

Operation	Front	Rear	Contents of `PrintQueue` (front → rear)
`ENQUEUE "Report1"`	1	1	`[Report1]`
`ENQUEUE "Report2"`	1	2	`[Report1, Report2]`
`ENQUEUE "Report3"`	1	3	`[Report1, Report2, Report3]`
`DEQUEUE`	2	3	`[Report2, Report3]`. “Report1” is removed
`ENQUEUE "Report4"`	2	4	`[Report2, Report3, Report4]`
`DEQUEUE`	3	4	`[Report3, Report4]`. “Report2” is removed

Note that after each DEQUEUE, the array position itself still physically holds the old value (for example, PrintQueue[1] still holds “Report1” after the fourth row). It is simply no longer part of the logical queue, because Front has moved past it.

[5 marks]: [1] for the correct value of Front after each of the six operations, [1] for the correct value of Rear after each of the six operations, [1] for the correct contents after the three ENQUEUE operations, [1] for correctly removing the job that has been waiting longest on each DEQUEUE (not the most recently added job), [1] for the final state Front = 3, Rear = 4, PrintQueue logically containing [Report3, Report4].

Part (c): One more DEQUEUE

After the six operations, Front = 3, so PrintQueue[Front] is PrintQueue[3] = "Report3". Calling DEQUEUE once more produces “Report3”, and Front would then increase to 4. [1 mark]

Part (d): A limitation of Front and Rear that never wrap around

Because Front and Rear only ever increase and never wrap back around to reuse positions freed by earlier DEQUEUE operations, those freed positions become permanently unusable. In this example, after the six operations Front = 3 and Rear = 4, so array positions 1 and 2 are free but can never be written to again. Only one further ENQUEUE is possible. Rear can still become 5, which is a valid index in ARRAY[1:5], but a second further ENQUEUE after that would need Rear to become 6, which is outside the declared array bounds. The queue would therefore report itself as full and reject a new print job, even though positions 1 and 2 are genuinely free and could have stored it. [2 marks]: [1] for identifying that freed positions at the start of the array can never be reused, [1] for a concrete illustrative example (using the actual index values from this scenario) showing the queue incorrectly reporting itself as full.

Final answers

(a) A queue. FIFO order matches “job submitted first is printed first”.
(b) See the trace table above; final state after all six operations: Front = 3, Rear = 4, PrintQueue logically containing [Report3, Report4].
(c) “Report3” is produced; Front becomes 4.
(d) Freed positions at the start of the array (indices 1 and 2 here) can never be reused, so the queue can incorrectly report itself as full. For example, after only one more ENQUEUE (Rear = 5), a further ENQUEUE would need Rear = 6, outside ARRAY[1:5].

Common mistakes

Choosing a stack instead of a queue for the print server, without checking that print jobs here must be processed first-in, first-out (FIFO) in the order they were submitted, not last-in, first-out (LIFO).
On DEQUEUE, removing the job at Rear and decreasing Rear, rather than removing the job at Front and increasing Front, confusing which end of the queue jobs are actually removed from.
Forgetting to set Front to 1 on the very first ENQUEUE (when the queue was previously empty), leaving Front at 0 and so pointing at a position that does not exist in ARRAY[1:5].
In (c), applying LIFO reasoning and stating "Report4" (the most recently enqueued job) instead of "Report3" (the job actually at Front after the six operations), forgetting a queue always removes the job that has been waiting longest.
In (d), assuming the array-based queue can store an unlimited number of jobs as long as few are currently waiting, rather than recognising that Rear increasing without ever wrapping back to reuse freed positions means the queue can report itself as "full" and reject new jobs even when earlier positions are now unused.