When we looked at the ordered list and stack data structures, we saw two different ways to implement each one. Although the implementations were different, the data structure was still the same from the abstract point of view. 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. However, in this lesson, we are only going to focus on one implementation in order to highlight another distinction: the distinction between the logical representation of a queue and the physical representation of a queue. Remember that the logical representation is the way that we think of the data being stored in the computer. The physical representation is the way the data is actually organized in the memory cells.
To implement our queue, we will use an array of eight memory cells and two pointers to keep track of the head and tail of the queue. The diagram below shows a snapshot of a queue in the computer's memory. The queue currently contains five letter items with 'L' at the head of the queue and 'O' at the tail of the queue.
Now let's consider how the EnqueueItem and DequeueItem operations might be implemented. To enqueue letters into the queue, we could advance the tail pointer one location and add the new letter. To dequeue letters, we could remove the head letter and increase the head pointer one location. While this approach seems very straightforward, it has a serious problem. As items are added and removed, our queue will march straight through the computer's entire memory. We have not limited the size of our queue.
Perhaps we could limit the size of the queue by not allowing the tail pointer to advance beyond a certain 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.
What we really need is a way to make our array circular. Of course, we know that the computer's memory is linear, so we can't change the physical representation of the data. However, we can implement our operations in such a way that our queue acts like it was a ring or a circle. In other words, we are going to create a logical representation that is different from the physical representation in memory. The applet below shows these two representations along with the abstract view of the queue. Click the button below to start the applet. The applet will open in a new window along with instructions for using the queue.