Linear queues

• A problem with using linear queues is that space in the array cannot be reused. The queue may appear to be full even when there are no items in it. This can be overcome by using a circular array.
• When using a linear queue, no attempt is made to re-use space at the start of the array (that has been freed up as items are dequeued). Thus you will get a 'queue is full' message when the last position in the array is used, no matter how many items are on the queue.
• Using a linear queue, when an item dequeued, the front pointer moves/is incremented by 1. The data does not need to be deleted as it will no longer be part of the queue.
• The front index pointer is initialised to 0 and the rear index pointer is initialised to −1. The rear index pointer will be incremented every time you add an item to the queue, so this initial value will ensure that the first item is added into the first position of the array (position 0). Thus, once the first item has been added, both front and rear will correctly point to this element in the array.
• Before adding an item to the queue you need to check that the queue is not full. When the rear index pointer is pointing to the final slot of the array, there is no room to add new items.
• If the end of the array has not been reached, the rear index pointer is incremented and the new element is added to the queue.
• Before taking an element from the queue you need to check that the queue is not empty. A subroutine is_empty() can be defined for this purpose. The subroutine will check whether the front index pointer is ahead of the rear index pointer.

  If the queue is not empty, the element at the front of the queue (as referenced by the front index pointer) is returned and the front pointer is incremented by 1.