Queues (OCR A Level Computer Science)
Revision Note
Author
James WoodhouseExpertise
Computer Science
Queues
What is a Queue?
A queue is a First in First out (FIFO) data structure
Items are added to the end of the queue and removed from the front
Imagine a queue in a shop where customers are served from the front and new customers join the back
A queue has a back (tail) pointer and a front (head) pointer.
Much the same as with a stack, an attempt to enqueue an item when the queue is full is called a queue overflow. Similarly, trying to dequeue an item from an empty queue is called a queue underflow.
A queue can be static or dynamic
There are three types of queues
Linear Queue
Circular Queue
Priority Queue
Main Operations
Operation | Description |
|---|---|
enQueue(value) | Adding an element to the back of the queue |
deQueue() | Returning an element from the front of the queue |
peek() | Return the value of the item from the front of the queue without removing it from the queue |
isEmpty() | Check whether the queue is empty |
isFull() | Check whether the queue is full (if the size has a constraint) |
Queue Keywords
Keyword | Definition |
|---|---|
Queue | An abstract data structure that holds an ordered, linear sequence of items. It is a First in First out structure. |
FIFO | First In First Out |
Static Data Structure | Has a fixed size and can’t change at run time. |
Dynamic Data Structure | Able to adapt and accommodate changes to the data inside it so it doesn’t waste as much space in memory. |
Pointer | An object that stores a memory address |
Linear Queues
What Are Linear Queues?
A linear queue is a data structure that consists of an array.
Items are added to the next available space in the queue starting from the front
Items are then removed from the front of the queue
Enqueue Data
Before adding an item to the queue you need to check that the queue is not full
If the end of the array has not been reached, the rear index pointer is incremented and the new item is added to the queue
In the example below, you can see the queue as the data Adam, Brian and Linda are enqueued.
Dequeue Data
Before removing an item from the queue, you need to make sure that the queue is not empty
If the queue is not empty the item at the front of the queue is returned and the front is incremented by 1
In the example below, you can see the queue as the data Adam is dequeued
Circular Queues
What Are Circular Queues?
A static array that has a fixed capacity which means that as you add items to the queue you will eventually reach the end of the array
When items are dequeued, space is freed up at the start of the array
It would take time to move items up to the start of the array to free up space at the end, so a Circular queue (or circular buffer) is implemented
It reuses empty slots at the front of the array that are caused when items are dequeued
As items are enqueued and the rear index pointer reaches the last position of the array, it wraps around to point to the start of the array as long as it isn’t full
When items are dequeued the front index pointer will wrap around until it passes the rear index points which would show the queue is empty
Enqueue Data
Before adding an item to the circular queue you need to check that the array is not full
It will be full if the next position to be used is already occupied by the item at the front of the queue
If the queue is not full then the rear index pointer must be adjusted to reference the next free position so that the new item can be added
In the example below, you can see the circular queue as the data Lauren is enqueued.
Dequeue Data
Before removing an item from the queue, you need to make sure that the queue is not empty
If the queue is not empty the item at the front of the queue is returned
If this is the only item that was in the queue the rear and front pointers are reset, otherwise the pointer moves to reference the next item in the queue
In the example below, you can see the queue as the data Adam is dequeued
Exam Tip
When asked to display a queue visually, make sure that you also identify the position of the front and rear pointers.
Worked Example
The current contents of a queue called 'colours', have been implemented in an array are shown below:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
red | yellow | green | blue | grey |
|
|
|
↑ front |
|
|
| ↑ back |
|
|
|
Front = 0
End = 4
The queue has the subprograms enqueue and dequeue. The subprogram 'enqueue' is used to add items to the queue and the subprogram 'dequeue' removes items from the queue.
Use the following diagram to show the queue shown above after the following program statements have run:
enqueue(“orange”)
dequeue()
enqueue(“maroon”)
dequeue()
dequeue()
4 marks
Answer:
1. The first thing is to enqueue orange.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
red | yellow | green | blue | grey | orange |
|
|
↑ front |
|
|
|
| ↑ back |
|
|
2. Then apply a dequeue() this will remove the first item in the queue.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| yellow | green | blue | grey | orange |
|
|
| ↑ front |
|
|
| ↑ back |
|
|
3. Then enqueue maroon.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| yellow | green | blue | grey | orange | maroon |
|
| ↑ front |
|
|
|
| ↑ back |
|
4. Then apply another dequeue to remove the next item from the front.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
| green | blue | grey | orange | maroon |
|
|
| ↑ front |
|
|
| ↑ back |
|
5. Then apply the final dequeue command to remove the next item from the front.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
|
| blue | grey | orange | maroon |
|
|
|
| ↑ front |
|
| ↑ back |
|
Elements are in the queue (correct four colours)
… in the correct positions
'Front' points to the first element in the queue
'End 'points to the last element in the queue
You've read 0 of your 0 free revision notes
Get unlimited access
to absolutely everything:
- Downloadable PDFs
- Unlimited Revision Notes
- Topic Questions
- Past Papers
- Model Answers
- Videos (Maths and Science)
Did this page help you?