|
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.
|
