Problem: to understand the solution, when the length of the queue is 5.
Exercise:
Its solution:
Question: Why is the solution not C A B B B, otherwise everything the same in the "Solution"-picture above?
+6
A:
It's because of the definition of the Queue class in your notes. A queue with capacity stated as 5 seems only to be able to hold 4 elements meaningfully, as it reports full when myBack coincides with myFront, and myBack points after the last element. In this case, the Queue errors saying it's full before the character in question can be overwritten with the B value stored in ch.
David M
2009-07-22 13:09:28
That's a pretty awful circular buffer, but it very well could be the answer. Without the implementation of the queue it's hard to say.
Welbog
2009-07-22 13:11:14
The implementation of the queue is in the lecture notes on the page the questioner linked to...
David M
2009-07-22 13:12:21
Ah. I'm looking at it now. You're right. It's because of the way the guard on the `add` method is implemented. The queue tracks the last index rather than the size of the queue. I maintain that is a terrible circular buffer implementation. I'll withdraw my answer as it no longer applies.
Welbog
2009-07-22 13:14:26
And I totally agree with your criticism of the implementation, so +1
David M
2009-07-22 13:19:41
@David M: Do you mean the sentence in the notes: "Note that we need to leave an empty slot in the array in order to distinguish between empty array and a full array."
Masi
2009-07-22 14:25:17
Suppose the sentence. There is no empty slot in the answer. Contradiction?!
Masi
2009-07-22 14:30:03
More here: http://files.getdropbox.com/u/175588/SO/contradiction.png
Masi
2009-07-22 14:31:50
@UnixBasics: no, it's to do with how the queue is tested for fullness. No contradiction. Check through the implementation, and if you need to, implement the code and step through it in a debugger.
David M
2009-07-22 14:40:28
+2
A:
[A,B,-,-,-] (k=1) (A)
[-,B,A,B,-] (k=2) (B)
[C,-,A,B,B] (k=3) (A)
[C,A,B,B,B] (k=4) (B)
in my opinion you are right, solution is not true :)
ufukgun
2009-07-22 13:11:41
It *should* work this way, but unfortunately the way queue is defined means it defies common sense. Please take a look at David's answer and the course notes on queues and you'll see why.
Welbog
2009-07-22 13:18:34