Having trouble to understand the full code of Queue using Array

[Simon Penders]

Hey guy's,

Sorry for asking this (probably stupid) question, and since i am Dutch, sorry if my English is off. But since i don't have a teacher and i am learning myself, i would like to have a better explanation for this code. Or perhaps some links to websites or video's which explain this more easy. I've just learned about Array's, the usage of constructors and methods. I am using the book Java, A beginners guide version sixth edition. First off the code, i hope it's ok this way, otherwise, so sorry:

/*
Project 5-2
A queue class for characters.
*/

class Queue {
 char q[]; // this array holds the queue
 int putloc, getloc; // the put and get indices
 Queue(int size) {
  q = new char[size+1]; // allocate memory for queue
  putloc = getloc = 0;
 }

// put a character into the queue

void put(char ch) {
 if(putloc==q.length-1) {
  System.out.println(" – Queue is full.");
  return;
 }
  putloc++;
  q[putloc] = ch;
}

// get a character from the queue

char get() {
 if(getloc == putloc) 
  System.out.println(" – Queue is empty.");
  return (char) 0;
 }
  getloc++;
  return q[getloc];
 }
}

// Demonstrate the Queue class.

class QDemo {
 public static void main(String args[]) {
  Queue bigQ = new Queue(26);
  Queue smallQ = new Queue(4);
  char ch;
  int i;
  System.out.println("Using bigQ to store the alphabet.");

// put some numbers into bigQ

for(i=0; i < 26; i++)
bigQ.put((char) ('A' + i));

// retrieve and display elements from bigQ

System.out.print("Contents of bigQ: ");
for(i=0; i < 26; i++) {
 ch = bigQ.get();
 if(ch != (char) 0) System.out.print(ch);
}
System.out.println("\n");
System.out.println("Using smallQ to generate errors.");

// Now, use smallQ to generate some errors

for(i=0; i < 5; i++) {
 System.out.print("Attempting to store " + (char) ('Z' - i));
 smallQ.put((char) ('Z' - i));
 System.out.println();
}
 System.out.println();

// more errors on smallQ

System.out.print("Contents of smallQ: ");
 for(i=0; i < 5; i++) {
 ch = smallQ.get();
 if(ch != (char) 0) System.out.print(ch);
  }
 }
}

Ok, here my questions:

1. Why has the size of the array has to be 1 bigger then the requested queue, like written in the constructor: q = new char(size+1) ? The book said it's because of the algorithm that the array has to be one size bigger then the size of the requested queue. I don't get this, how does it work?
2. I don't understand how this code part works: if(putloc==q.length-1) or if(getloc == putloc), it's to chec if a queue is full or empty, but how does this works exactly?
3. In the char get() method, why if the queue is empty it does this: return (char) 0; ?
4. In example, if the smallQ has the size of 5 (4+1), why can it only store the letters Z, X, Y, w and not V? If the array has five spaces, you can store 5 letters right?

Sorry for al the questions, i googled, watched on youtube, read in the book again, but the code kept my head spinning for almost two weeks now. If someone can explain this more easy, i would appreciate that. I prefer examples with a table of the array or something like that so i can visualize it as well, if someone knows a great video, website link or own explanation for this, it would be so helpful. Thanks in advance for your time.

[Keith Lynn]

The default value of a char in Java is \u0000

So, for example, if you want to store 4 characters in the queue, you create a queue with 5
spaces

array = {\u0000,\u0000,\u0000,\u0000,\u0000}

At this point, putloc and getloc are both 0

You enqueue 'Z'

putloc is increased by 1

The array becomes

array = {\u0000,'Z',\u0000,\u0000,\u0000}

You enqueue 'Y'

putloc is increased by 1

array = {\u0000,'Z','Y',\u0000,\u0000}

You enqueue 'X'

putloc is increased by 1

array = {\u0000,'Z','Y','X',\u0000}

You enqueue 'W'

putloc is increased by 1

array = {\u0000,'Z','Y','X','W'}

Now the value of putloc is 4, which is the length of the array minus 1, which means there is
no more space in the queue

Now suppose you dequeue elements.

How do you know when you have dequeued all the elements?

At this point putloc is 4, and getloc is 0.

You dequeue an element.

getloc becomes 1. You dequeue 'Z'

You dequeue another element.

getloc becomes 2. You dequeue 'Y'

You dequeue another element.

getloc becomes 3. You dequeue 'X'

You dequeue another element.

getloc become 4. You dequeue 'W'

Now the value of getloc is the same as the value of putloc

This is an indication that the queue is empty.

So the next time you try to dequeue, what is returned is (char) 0 from the get method. The reason
for doing this is that the get method returns a char so you need to return something that is a
char.

So to answer your questions

(1) You create an array with 1 space larger than you need because of the way the put method
and get method work. That is, before you enqueue an element, you increment putloc to 1

(2) When the value of putloc is equal to the length of the array - 1, you know the queue is full. When
getloc is equal to putloc, you know you have dequeued everything

(3) Again, since the method returns a char, you can't return a 0 directly. You could repace return (char) 0 with return ' '

(4) When the size of the array is 5, you can store 4 characters

Does this help?

[Simon Penders]

Keith Lynn wrote:The default value of a char in Java is \u0000

So, for example, if you want to store 4 characters in the queue, you create a queue with 5
spaces

array = {\u0000,\u0000,\u0000,\u0000,\u0000}

At this point, putloc and getloc are both 0

You enqueue 'Z'

putloc is increased by 1

The array becomes

array = {\u0000,'Z',\u0000,\u0000,\u0000}

You enqueue 'Y'

putloc is increased by 1

array = {\u0000,'Z','Y',\u0000,\u0000}

You enqueue 'X'

putloc is increased by 1

array = {\u0000,'Z','Y','X',\u0000}

You enqueue 'W'

putloc is increased by 1

array = {\u0000,'Z','Y','X','W'}

Now the value of putloc is 4, which is the length of the array minus 1, which means there is
no more space in the queue

Now suppose you dequeue elements.

How do you know when you have dequeued all the elements?

At this point putloc is 4, and getloc is 0.

You dequeue an element.

getloc becomes 1. You dequeue 'Z'

You dequeue another element.

getloc becomes 2. You dequeue 'Y'

You dequeue another element.

getloc becomes 3. You dequeue 'X'

You dequeue another element.

getloc become 4. You dequeue 'W'

Now the value of getloc is the same as the value of putloc

This is an indication that the queue is empty.

So the next time you try to dequeue, what is returned is (char) 0 from the get method. The reason
for doing this is that the get method returns a char so you need to return something that is a
char.

So to answer your questions

(1) You create an array with 1 space larger than you need because of the way the put method
and get method work. That is, before you enqueue an element, you increment putloc to 1

(2) When the value of putloc is equal to the length of the array - 1, you know the queue is full. When
getloc is equal to putloc, you know you have dequeued everything

(3) Again, since the method returns a char, you can't return a 0 directly. You could repace return (char) 0 with return ' '

(4) When the size of the array is 5, you can store 4 characters

Does this help?

First of all, thanks for your answer. I'm sorry to say it, but it still is all confusing to me. So, i want to make a queue in which i want to store 4 letters. Char has an initial value of null i understand ( i don't get why this is mentioned) , but why can't i use the index [0] of the array in this case? So in your example: array = {\u0000,\u0000,\u0000,\u0000,\u0000} and then store it like this: array = {Z,Y,X,W,V} ? Why has putloc to be incremented first?

Also the book says you enqueue at the rear of the queue, and dequeue from the front. But the back of the queue supposed to be index [4] or [5] right? In many examples the enqueue at index [0] first, but this is the front?! I guess i am confusing indexes, values and other stuff and it became a mess in my head. So sorry to ask for more explanation, because i really aprreciate the effort you've put into your answer, feeling so stupid right now.. Hope you can simplify it further..

[Keith Lynn]

Yes you add to and remove from the queue at different ends.

I think part of your confusion is thinking of the whole array as the queue.

This is not the case.

Only a portion of the array is the queue.

When you increment putloc, that means you are using more of the array.

[Stefan Evans]

> why can't i use the index [0] of the array in this case?
>Why has putloc to be incremented first?

There is no absolute requirement for it. It is just the way this particular implementation works.

You could write it so that you enqueue into the putloc and THEN increment the putloc variable.
You would have to make the corresponding change in the dequeue method.
I think the rest would remain pretty much the same. (Try it and see. It should still pass all the tests of the QDemo class)

I actually agree with you. That first index is "wasted space". And it doesn't have to be. It is possibly a carry-over from legacy code examples and c++ days? Who knows?
If you continue in the industry, you will often find code like that that has been written by someone in a 'non-optimal' manner.
The important question though : Does it work?

>Also the book says you enqueue at the rear of the queue, and dequeue from the front. But the back of the queue supposed to be index [4] or [5] right? In many examples the enqueue at index [0] first, but this is the front?!
The array is just storage space. It isn't the actual queue.
The "front" and "back" of the queue are tracked in the variables getloc and putloc.
The queue is the data stored in the array based on the in the indexes between getloc and putloc.

The concept of data structures like this, is that the underlying implementation of the queue doesn't matter to the end user.
As long as it looks like a queue, and behaves like a queue, the fact that it uses an array to implement things is irrelevant to them.
Whether it starts from index 0 and counts up, or at index 'max' and counts down, or even 'wraps around' so that when you get to the end you start again at the beginning (as long as it isn't still being used there)

[Campbell Ritchie]

Stefan Evans wrote:. . .
I actually agree with you. That first index is "wasted space". And it doesn't have to be. It is possibly a carry-over from legacy code examples
. . .

And nobody is going to bother to change it in order to save 8 bytes of memory

Now that memory is cheap it is probably not worth changing such things for a tiny gain. But when you are writing new code, you might as well write it according to current best practice.

[Simon Penders]

Thanks for all the answers, i am starting to get it a little more. By the way, why is there a return statement in a void method anyway? A void method does not return a value anyway, right? Also, can't you just use a void method for the get method, so you don't have to use return (char) 0; ?

Also, why in this code they did this: Queue bigQ = new Queue(100); ? Because to store the alphabet it's enough to have a supporting array with the size of 27 right?

[Knute Snortum]

why is there a return statement in a void method anyway? A void method does not return a value anyway, right?

It's a way of exiting the method early.

Also, can't you just use a void method for the get method, so you don't have to use return (char) 0; ?

The get() method needs to return something since it's declared char get(), so even when it exits early, it returns a character (not the best design, BTW).

[Stephan van Hulst]

Stefan Evans wrote:I actually agree with you. That first index is "wasted space". And it doesn't have to be. It is possibly a carry-over from legacy code examples and c++ days? Who knows?

It actually looks like it might have been a left-over (or in preparation) of a circular buffer. With circular buffers it's not easy to determine the difference between an empty and a full buffer. A common solution is to make the buffer size one bigger than it needs to be.

[Simon Penders]

Thanks again for the answers. Only one question remains, why they have made a array of size 100 for storing the alphabet? You can simply use an array of 27 in this case right?

So, to sum it all up: if i understand correctly, two array objects are created in this code, thanks to the constructor those are full objects. One array object is made with the name smallQ and one bigQ. Both have the variables putloc and getloc. In example Z is inserted via the put method, but putloc is incremented first. So smallQ array has the letter Z on the index [1], Y on index [2] and so on. If putloc and getloc are both 0 then the Queue is empty, if putloc is the same as the array size-1 it is full. Correct thinking this way? If anyone knows some great video's or other tutorials about this Queue, please let me know. So i can get deeper into the material, i really like Java, but sometimes it can be hard suddenly..