Queues
A queue is a FIFO (i.e. first in, first out) data structure. A good analogy for a queue is a physical queue. New items enter at the back of a queue. Items are removed from the front of the queue.
Linear queues
A linear queue where information enters from the rear and is removed from the front. It can be implemented in two ways. The first is as a list with a max size and pointer to the rear item. When items are removed from the list
all the other items are moved along one place.
This method becomes increasingly inefficient the larger the queue and the more elements it contains.
A linear queue can be implemented using a list with a maximum size and pointers to the front and rear of the queue. Create a linear queue class with a maximum size and a pointer to the rear of the queue.
As you can see in this example. Using this method the data is removed from the front of the queue when it is output, making room for more items to be added once the queue is no longer full. However, when we try to add a 6th
item to a full queue it is not allowed. In our case using a Python list to implement this data structure means we can use pop and the moving up of all other items in the queue is taken care of for us but normally this would
involve a loop to one at a time move items forward. This means the longer the queue, the slower this is.
The other way to implement it involves having front and rear pointers.
This makes it more efficient when removing items from the front of the list. However, it means the spaces at the start of the array where items have been removed are no longer available. This means it needs more space and will
be inappropriate where the data in the queue is regularly refreshed.
Make a new class for a linear queue with both front and rear pointers where removing items from the queue simply moves the front pointer along one place.
As you can see in this example. Using this method the data is not removed from the front of the queue when it is output. This means no free space is created by removing items from the queue. I put a few extra outputs in so
you can see the queue as well as the state of the list it is based on.
Circuar queue
One way to overcome the problems of linear queues is with a circular queue. We still have a queue of fixed size with pointers to the start and end of the queue. When an item is removed the front pointer is adjusted to point
to the next item in the queue. When a new item is added it is added at the next available space after the rear pointer. This includes if the next space is back at the start of the queue.
Implement a new class for a circular queue. When you output the queue, also output the actual list it is based on as well as the values for front and rear pointers and number of elements.
As you can see in this example. Using this method the data is placed in the next free space even if that is at the start of the list. You can see that when we dequeue the first value it is not yet removed from the list.
This happens when we need to use that space for a new element of the circular queue. The outputting of the queue along with the list it is based on and data for the front and rear of the queue as well as number of items in
the queue make it clear what is happening.
Priority queues
A priority queue is one where new items are added to the queue in a location that is based on their priority. Consider an A&E department. As new people join the queue they are assessed as to the urgency of their medical
needs. Those that require urgent treatment will be placed in front of those in the queue with lower needs.
Create a priority queue, using an array of tuples that automatically sorts patients in an A&E queue based on their priority. Priorities are raned 1 for urgent, 2 for high priority and 3 for low priority. New patients should be
added to the list in front of those with a lower priority but behind those with an eual or higher priority already in the queue.
You can see that although they are enqueued later Sam and Jan take their appropriate priority based position in the queue.
Uses of queues
Jobs that are sent to the printer are held in a print queue and then printed in the order they were received. Keyboard inputs are stored in a buffer as the user types and then dealt with in the order they were struck.
