Queues

A queue is a data structure with a first-in first-out policy.

The videos below combine stacks & queues:

https://www.youtube.com/watch?v=WnjVVJ0kIgQ&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW&index=5

https://www.youtube.com/watch?v=1hEK9yWs_cM&index=6&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW

Types of Queue

Linear

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.

Circular

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.

Priority

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