Laboratory: Implement Queues with Arrays

Read through ArrayBasedQueue.java. You will note that the iterator is not yet implemented. You may also note a few subtle (or not so subtle) bugs. If so, write them down. If not, that's okay, we'll work them out in the lab.

Look at ArrayBasedQueueExpt. Summarize what the queue should look like at each step of the first series of procedure calls. You may also want to revisit the ReportingLinearStructure class.

Run ArrayBasedQueueExpt and see if you get the output that you expect.

You've probably determined that there seem to be some significant bugs in the queue implementation. Can you tell where they are?

You might learn a bit more about the bug by adding a call to expt.put("d") before the first call to expt.get().

Do your best to correct the first bug: get and peek don't seem to return the correct value after some point. If you need a hint as to where to look, ask your instructor or mentor.

If you uncomment the second section of code and reduce the size of the queue to, say, 4, you may find that the queue fills before it should. (You may also have dealt with that issue.)

How do we fix that problem? Normally, we “wrap around”, so that the back of the queue goes to the front of the array. For example, if we have seven items in a queue, and the front is at 4, then the item 0 is at 4; item 1 is at 5; item 2 is at 6; item 3 is at 7; item 4 can't be at 8 (there is no index 8), so we wrap it around to index 0; item 5 is at 1, item 6 is at 2, and the back of the queue is at 3.

Rewrite your code so that elements wrap in the specified way. You'll need to change back. You may also need to change the code for isEmpty and isFull.

Right now, ArrayBasedQueue has only a stub iterator. Finish implementing the iterator. You may want to uncomment the third set of experiments to see if the iterator works.