A Level Computer Science OCR Practice Exam

Which data structure is best for implementing a first-come, first-served (FIFO) schedule?

1. Stack

2. Queue

3. Array

4. Linked list

The correct answer is: Queue

A queue is the optimal data structure for implementing a first-come, first-served (FIFO) schedule because it is specifically designed to handle elements in the order they were added. In a queue, elements are added at the back and removed from the front, effectively allowing the first element added to also be the first one to be removed. This characteristic aligns perfectly with the FIFO principle, where the first task or item put into the queue is the first one to be processed or served. Stacks, on the other hand, operate on a last-in, first-out (LIFO) basis, meaning the most recently added element is the first to be removed, which does not support FIFO scheduling. Arrays can store elements in a linear structure, but they lack built-in mechanisms to easily manage the removal and addition required for FIFO behavior. Linked lists could theoretically implement FIFO with the right pointers set up, but they require more overhead in terms of managing nodes and pointers compared to a queue, which is designed for this purpose. Therefore, a queue is the most efficient and appropriate choice for a FIFO scheduling system.