Queues
Computer Science: OCR A Level, topic 4.2.3
Queues
A queue is a data structure where data items are always added to the end and removed from the front. It is often referred to as a 'first in, first out’ data structure.
Queues
- Queues can be implemented using other data structures, such as arrays or linked lists.
- In either case, two extra variables are required to identify the front and rear of the queue.
- Queues can be ‘static’ (fixed in size) or ‘dynamic’ (able to grow in size as necessary)
Queue operations
- Several operations can be carried out on queues:
- enQueue() - adds an item to the rear of a queue.
- deQueue() - removes and displays the item at the front of a queue.
- isEmpty() - checks to see if the queue is empty.
- isFull() - checks to see if the queue is full.
Uses
- Queues have a wide range of uses in computer science, including:
- Storing print jobs until the printer is ready to print.
- CPU scheduling.
- Breadth-first traversal of a graph.
Linear or circular
- Queues can also be ‘linear’ or ‘circular’.
- When an item of data is removed from the front of a linear queue, all the other items move up one place.
- This is only suitable in a small queue, otherwise data processing time can be excessive.
- When an item of data is removed from the front of a circular queue, the only processing required is to update the two pointers identifying the new front and rear of the queue.