Queues

Página 1

Basics Of Queues

Fundamental Rules of Queues:

Items are added to the back.

Items are Removed from the front.

Queues also need to have front and back pointers, so that the values don't always have to have their positions changed after each leaves.

These work by moving along the queue like a type writer, doing the operations on each as needed.

So when one operation is completed and that value is removed the front pointer is moved to the next item along, and when a value is added to the back, the back pointer is moved to it. This means the total size of the queue can be fount by doing (Back pointer position) - (Front pointer position).

However when the queue becomes full, this no longer works as there are no more spaces to add new values to the back of the queue, but a massive feed of empty positions at the front. So what next?

This is solved by adding new items to the front of the queue, but keeping the pointers where the first item to join is, meaning that the queue acts a lot like a circular disc; reading from the first item to arrive, and overwriting the empty slots to make space for new items to join the queue.

So just like a hamster wheel, the front of the queue is recycled to act as the back of the queue to make the process more efficient.

Página 2