4.2.2.1 Queues.md

Queues

Be able to describe and apply the following to linear queues, circular queues and priority queues:

• add an item
• remove an item
• test for an empty queue
• test for a full queue

Operations and descriptions

Operation	Description
Add (Enqueue)	Adds a new item to the rear of the queue
Remove (Dequeue)	Removes an item from the front of the queue

Pseudocode

Add an item

Linear Queue

IF Queue is FULL THEN
  Error
ELSE
  Queue[Queue.size + 1] = "Ian"
  Queue.size += 1
END IF

Circular

IF Queue is FULL THEN
  Error
ELSE
  position = (Queue.size + 1) % Queue.max
  Queue[position] = "Ian"
  Queue.size += 1
END IF

Priority

Remove an item

Linear Queue

Circular

IF Queue is FULL THEN
  Error
ELSE
  position = Queue.size % Queue.max
  Queue[position] = null
  Queue.size -= 1
END IF

Priority

Testing for an empty queue

Linear Queue

Circular

Priority

Testing for a full queue

Linear Queue

Circular

Priority