A queue is a First-In First-Out (FIFO) data structure, commonly used in situations where you want to process items in the order they are created or queued. It is considered a limited access data structure since you are restricted to removing the oldest element first.
By convention, the queue insert operation is called enqueue
and the
remove operation is called dequeue
. Since we are mimicking the Java API,
we will stick to the add
, offer
, poll
, and remove
.
One common model of usage for a queue is to have one thread adding work to the queue, and another processing work from the queue. This is a common way to architect server programs.
The following image shows a conceptual image of a queue. The front of the queue is where items are removed, and the rear of the queue is where items are added.
![Queue](imagesdir/QueueImage.jpg)
Circular Array Queues
During this recitation we will be creating a circular array queue with a maximum capacity. This will give us an idea of how queues are implemented outside of academia. The capacity is a very realistic constraint.
The following image is a visual aid as to how circular array queues work:
![Circular Queues](imagesdir/CircularBuffers.png)
If you would like to learn more about circular arrays, go here.