Difference between revisions of "Queues"
|(One intermediate revision by the same user not shown)|
|Line 104:||Line 104:|
Latest revision as of 16:58, 9 October 2019
A queue is a data structure with a first-in first-out policy.
The videos below combine stacks & queues:
- 1 Types of Queue
- 2 Add to Queue
- 3 Take from Queue
- 4 Test for empty
- 5 Test for full
- 6 Quiz
Types of Queue
A linear queue is where items are removed from the front of queue and items are added to the rear of the queue. As items are removed from the front of the queue the front of the queue will move further and further back.
If we simply add to the rear of the queue and remove from the front in a linear fashion we would eventually reach the maximum limit of the queue and have no more space to add items. Also, there will be wasted empty space at the front of the queue.
It is also impractical to move all the items up a place when an item is removed (as would happen in a shop queue). This would require each item in the queue to be moved every time an item was removed from the queue. This would require too much processing especially for large queue sizes.
Rather than move the data items, we move the front and rear pointers as data is added or removed. We still need to know when the queue is full or empty. The easiest method is to simply count the number of items in the queue.
Pointers are required to point to the front and rear of the queue. The rear pointer always points to the last item in the queue and the front pointer points to the next item to be removed from the front of the queue. Initially rear pointer would be set to 0 and front pointer to 1.
We have a limit to the size of the queue (ie queuemax). To make the queue circular when either pointer reaches queuemax it will next move to position 1.
The queue is full when Number of items = queuemax and the queue is empty when Number of items = 0. We can only add an item if the queue is not full and we can only remove an item if the queue is not empty.
A priority queue is essentially two queues. You have a queue for priority items, and a queue for standard items. New priority items are added to the back of the priority queue, and new standard items are added to the back of the standard queue.
Items are removed from the front of the priority queue first. When no priority items are queued, items will be removed from the front of the standard queue.
Add to Queue
Items can only be added to a queue if the queue is not currently full. This algorithm implements a circular queue, so when the rear pointer is equal to the QueueMax it is looped back to 1.
This algorithm gets the input first, and then adds the item inputted onto the queue.
procedure TestAndAdd (ref Queue, Front, ref Rear) begin if NoOfItems = QueueMax then output ‘queue is full’ else if Rear = QueueMax Then Rear := 1 else Rear := Rear + 1 endif input data_item queue[Rear] := data_item NoOfItems := NoOfItems + 1 endif end
Take from Queue
Remember an item can only be removed from the queue if the queue is not currently empty. This algorithm will output the item from the queue, and then increment the front pointer value. This is for a circular queue, so when the front point is equal to the QueueMax the pointer is reset to 1.
procedure TestAndRemove (ref Queue, ref Front, Rear) begin if NoOfItems = 0 then output ‘queue is empty’ else output Queue[Front] if Front = QueueMax then Front := 1 else Front := Front + 1 endif NoOfItems := NoOfItems - 1 endif end
Test for empty
Remember an item can only be removed from the queue if the queue is not currently empty.
procedure TestEmpty (ref Queue, ref Front, Rear) begin if NoOfItems = 0 then output ‘queue is empty’ else output ‘queue is not empty’ endif end
Test for full
Items can only be added to a queue if the queue is not currently full.
procedure TestFull (ref Queue, Front, ref Rear) begin if NoOfItems = QueueMax then output ‘queue is full’ else output ‘queue is not full’ endif end