The Queue is the final linear data structure that we will examined. Like the stack, the queue is also a type of restricted list. Instead of restricting all the operations to only one end of the list as a stack does, the queue allows items to be added at the one end of the list and removed at the other end of the list. The figure below should give you a good idea of the abstract view of the queue.

This restrictions placed on a queue cause the structure to be a "First-In, First-Out" or FIFO structure. This idea is similar to customer lines at a in any bill payment store(eg. phone bill payment queue). When customer A is ready to check out, he or she enters the tail(end) of the waiting line. When the preceding customers have paid, then customer A pays and exits from the head of the line. The bill-payment line is really a queue that enforces a "first come, first serve" policy.

When we looked at the ordered list and stack data structures, we saw two different ways to implement each one of them. Although the implementations were different, the data structure was still the same from the abstract point of view for both stack and ordered list. We could still use the same operations on the data structures regardless of their implementations. With the queue, it is also possible to have various implementations that support the operations EnqueueItem and DequeueItem. The distinction between the logical representation of the queue and the physical representation of the queue. Remember that the logical representation is the way that we think of the way data being stored in the computer. The physical representation is the way the way data is actually organized in the memory cells(computer memory).

Now let's consider how the EnqueueItem and DequeueItem operations might be implemented in the queue. To store letters into the queue, we could advance the tail pointer by one location and add the new letter in the queue. To dequeue(delete) letters, we could remove out the head letter and increase the head pointer by one location. While this approach seems very straight forward, it has a serious problem. As items are added and removed, our queue will march straight through the entire memory of the computer. We have not limited the size of our queue to a fixed amount of size.

Perhaps we could limit the size of the queue by not allowing the tail pointer to advance beyond the certain memory location. This implementation would stop the queue from traversing the entire memory, but it would only allow us to fill the queue one time. Once the head and tail pointers reached the stop location, our queue would no longer work untill we delete some data from it.