Circular queues

• A static array has a fixed capacity, meaning that as you add elements to the queue, you will eventually reach the end of the array. However, as items are dequeued, space is freed up at the start of the array. Moving elements up to the beginning of the array would be very time-consuming. Instead, a circular queue (also called a circular buffer) is implemented.
• A circular queue reuses the empty slots at the front of the array that are caused when elements are removed from the queue. As items are enqueued, and the rear index pointer reaches the last position of the array, it wraps around to point to the start of the array (so long as the array is not full). Similarly, as items are dequeued the front index pointer will wrap around until it passes the rear index pointer (which shows that the queue is empty).
• When you write code to manipulate items in a circular queue, you must be able to advance the index pointers such that they will reset to 0 once the end of the array has been reached.

  You can calculate the new position for the index pointer by using the following expression:

  (pointer + 1) MOD MAX_SIZE
• The steps to initialise an array to service a circular queue is similar to that of a linear queue but the front index pointer is initialised to -1. This will allow you to be certain that you are dealing with an empty queue.
• Before an item can be enqueued, you must check whether the array is full. It will be full if the next position to be used is already occupied by the item at the front of the queue.
• If the queue is not full, the rear index pointer must be adjusted to reference the next free position so that the new element can be added. Remember that, with a circular queue, the next free position may be position 0 (if the rear index pointer is currently referencing the position at the end of the array).
• Before attempting to remove an element from the queue you need to check that the queue is not empty. The subroutine is_empty() is called to check whether the front index pointer is -1.
• If the queue is not empty, the item at the front of the queue is dequeued. If this is the only item that was in the queue, the front and rear pointers are reset. Otherwise the front pointer is advanced to reference the next item in the queue.
• Remember that you do not need to delete the element that has been dequeued. The front index pointer is adjusted (using the same technique that you used for the rear index pointer) and the position in the array will be overwritten in future enqueue operations.