In this lab you will finish a partially written Java GUI application that demonstrates the basic functions of a queue. This project is similar to your previous lab Lab 04 featuring a stack, but it introduces a queue as a list with different rules for adding and removing data. You should recall that in the case of a stack, additions and removals must both occur at one end of the list, which is called the top. For a queue, both ends of the list are given names, typically front and rear. The rules for additions and removals are almost as simple as those for a stack:

• To add an item to a queue, you must append it to the rear of the list.
• To remove an item from a queue, you must take it from the front of the list.

These rules are sometimes summarized by saying that a queue is a FIFO ("First In, First Out") list. In contrast, a stack is called a LIFO ("Last In, First Out") list.

In this lab you will implement a queue using an array, in a manner similar to that used for the Stack class that you implemented in Lab 04. In particular, the queue will also store values of type Object (which automatically includes objects of any class in Java).

Once again the GUI framework has already been created and tested, and a partially written source file of the Queue class will also be provided to you. Your task is to implement several essential Queue methods, which are presently only stubs. The GUI demo application will need correct versions of all these methods to work properly.

After you have completed the Queue class definition as described below, you should be able to compile all the files and run the project. Initially, the application should display the following window:

The GUI framework already includes event handlers that respond to user clicks on each of the buttons at the bottom of the window. These buttons are used to change the state of a single Queue object shown in the middle of the window.

The internal Queue array appears as the vertical pile of boxes, with the zeroth component on the bottom. But in contrast to the Stack, which had only one special index named top, the Queue must have two integer indexes pointing to the front and rear of the queue respectively. As in the Stack class, these indexes will be stored along with the array itself, as private instance variables. The rear index advances upward by one location whenever data is added to the queue, while the front index advances by one location whenever data is removed.

To establish a convention, the initial empty Queue will have both front and rear set to zero as indicated in the figure above. As it turns out, the only times that both front and rear have the same value are when the queue is either empty or full. But normally, you should interpret the rear index as indicating the next available location to store a new value. You may recall that this is identical to the role of the top index in the array-based Stack lab. In fact the only time when this is not the case is when there is no available location, namely when the Queue is full. As mentioned above, in that case the front and rear indexes become identical. Similarly, the front index usually indicates the location of the next valid data to be removed from the queue. The only time when this is not the case is when the queue is empty, as in the figure above.

The GUI application for this lab will allow you to store String values in the queue. To add a string (say a name) to the rear of the Queue, enter it in the leftmost text box in the bottom control panel and then click the Add button (or just press Enteron the keyboard, whichever you prefer). Whenever you click the Remove button, the item at the front of the Queue is removed and shown in the text box just to the left of the Remove button.

The following image was taken after adding the name "Fred":

After adding three more items (say for example "Alice", "Tina", "Bob"), and then removing two items from the front (first "Fred", then "Alice"), the display should appear as follows:

At any time you could go on to delete all the remaining items without encountering any problems. The only thing to note is that neither front nor rear would end up back at zero, at least not in the example used here. However, they would become equal. This will always be true of an empty queue in this implementation.

But by now maybe you have already detected a potential problem with the addition of any more items. After you add another item, say "Tom", you might expect that the rear index should be forced beyond the current array bounds. At first you might think you could avoid this by simply providing the queue with a setCapacity() method, similar to the method you implemented in Lab 04. Then whenever the rear index was about to go beyond the array bounds, you could just resize to a bigger array and save the day. But this is not a good solution if you look closely at the example above, since you can see that there is still room in the array below the current front pointer. Since items were removed as well as added, there are still vacant positions. It does not seem either necessary or efficient to resize the array in this case.

In fact there is a good solution to this problem, which is to introduce the notion of a circular array. Instead of going outside the array bounds, the rear index can be reset to 0, marking the zeroth component as the next available location. Thus after adding "Tom", the display should appear as shown below:

As you then proceed to insert more items, rear again advances upward from the bottom as it did originally. It turns out you will be doing similar things with the front index, so both indexes end up cycling repeatedly through the array.

Of course it is possible to fill up the entire Queue array, say by adding first "Mary" and then "Charles":

Note that the front and rear pointers are equal for a full array, just as they are for an empty array. In the instructions below, you will be able to distinguish between these two extremes simply by checking an item counter that will be included as one of the Queue instance variables.

Since arrays can become full, later in this project you will in fact need to implement a method called setCapacity(), which is similar in purpose to the setCapacity() method you wrote for the Stack class in Lab 04. Just as in the case of the push() method you implemented for the Stack, the add() method for the Queue must automatically invoke setCapacity() whenever it detects that it is currently full, so that it can increase its capacity before it goes on to add the new item.

Note that setCapacity() may be used to increase the capacity by an arbitrary amount. For instance, if you decide to boost the capacity by 3 each time your add() method detects a full array, use the statement

setCapacity (getCapacity() + 3);

Incidentally, you may have noticed that the positions of the array components were rearranged by setCapacity(), as were the front and rear indexes. This is perfectly legal, as long as all components are kept in the same (circular) order and both indexes still point to the values currently at the front and rear of the Queue.

Some remaining details need to be clarified before you plunge in:

The Trim, Clear, and Reset buttons all have the same functions as their counterparts in Lab 04. Trim adjusts the Queue capacity to match the number of currently stored components. Either Reset or Clear may be used to remove all values from the Queue, but Reset also resizes its internal array to its original length.

Finally, the GUI components at the top of the window also are similar to components provided in Lab 04. The text boxes on the left display the current number of values stored in the Queue and its current capacity (length of the internal array). Also note the text box labeled New capacity and its associated Apply button. These components will allow you to change the Queue capacity directly.

To complete this project, follow the steps listed below:

1. Launch the NetBeans IDE and select the File/New Project... option to create a new project named Lab05. Define the project to be a Java Application and be sure to create the Lab05 project folder in your csci/202/labs directory. Otherwise accept all the default settings so that NetBeans automatically writes a class named lab05.Main for you. As usual, the source file for this class will be in Lab05/src/lab05.
2. Download the following files into your Lab05/src/lab05 project folder. As you have seen before, NetBeans will detect these files and automatically include them in your project:

   DisplayFrame.java

   DisplayPanel.java

   Queue.java

3. Open the file lab05.Main and add the following lines of code into its main() method:

   	DisplayFrame frame = new DisplayFrame();
   	frame.setVisible(true);
   

4. For a quick overview of all these classes: the only task of the main() method in lab05.Main is to create a DisplayFrame, which is the main application window for this project. One special feature of a DisplayFrame is that it includes a single Queue object as part of its member data (instance variables in Java terminology). The DisplayPanel class represents the central portion of the application window, which will display the current state of the Queue object.
5. The version of the Queue class as defined in Queue.java contains only stubs of the following methods, all of which are essential for the application to work correctly:
   1. public void add (Object item)
   2. public Object remove ()
   3. public boolean isEmpty ()
   4. public int getItemCount ( )
   5. public int getCapacity ( )
   6. private void setCapacity ()
   7. public void clear ()
   8. public void reset ()

   Note, however, that Queue.java does define all the instance variables for the Queue class as well as two fully working constructors. It also includes a fully implemented render() method, which enables the DisplayPanel to draw the Queue object in the display area of the window. And it even contains a complete trim() method, since that one happens to be identical to what you should have used for the Stack in Lab 04. But even though some of the other methods listed above also have their Stack counterparts, they will all have to be implemented differently for a Queue.

   Before proceeding, you should look over the declarations for both the instance variables and the constructors.. As usual, both are near the top of the class definition.

   Now proceed to implement the bodies of the methods listed above, so that they perform the following tasks:

1. add() must first check whether the current internal array is full, and if necessary invoke setCapacity() to make at least one available location. (For the sample figures in the Introduction, the capacity increment was chosen to be 3.) Then add() must go on to add its value parameter into the array slot indicated by the rear index. Next it must increment the rear index according to the rule for a circular array as described in the Introduction. This rule can be expressed as follows:
   rear = (rear + 1) % array.length;

   Finally, add() must increment the Queue instance variable itemCount, which keeps track of the current number of stored values.

2. remove() must first check whether the Queue is currently empty. If so, it must immediately throw an IllegalStateException and return without making any changes to the Queue. Otherwise, the method should make a local reference to the array component indicated by the front index, since on exit it must return this value. Then it must increment the front index, using the same "mod" rule for a circular array that was used above for the rear index:
   front = (front + 1) % array.length;

   Finally, remove() must decrement the itemCount instance variable before returning the value it just removed.

3. isEmpty() should use the itemCount instance variable to determine whether the queue is currently empty and return the result. Note: while it is true that both the front and rear indexes become equal for an empty queue, this also happens for a full queue. Thus checking these indexes for equality is an ambiguous test for an empty queue.
4. getItemCount() must return the current number of values stored in the queue.
5. getCapacity() must return the current length of the array instance variable. Note that this is the number of array components allocated by the new operator, not the number of values currently stored in the queue.
6. setCapacity() is similar in some respects to the setCapacity() method that you implemented for a Stack in Lab 04, but its array-swapping code cannot be written quite the same way in the case of a Queue. In fact, implementing this method correctly is the most challenging part of this lab, so you may want to tackle all the other methods first.

   That being said, its first steps are quite easy: it must check whether its input parameter capacity, the requested new capacity, is at least as large as the number of stored items. If not, the method must immediately throw an IllegalStateException without making any change to the Queue.

   Otherwise, setCapacity() must use the new operator to create a new Object array of length capacity. As with its Stack counterpart, you must declare a local reference to this array until you have copied all the contents of the current Queue array. After the copying is done, the instance variable array is reassigned to reference the new array.

   The tricky part for a Queue is how the copying itself must be done. It cannot be the same sort of b[i] = a[i] loop that would copy an array a into array b. This is all it took for a Stack, but if you just stare at some of the figures above you should soon realize that a Queue must be handled differently.

   But there is no need to panic just yet, since there is a fairly simple approach that works as follows: just load the new array starting at index 0, no matter where the front index is in the current array. In more detail:

   • Declare a local variable, say i, and initialize it to the value of the front instance variable. Use this variable as an index into the current array, starting at the front.
   • Declare another local variable, say j, and initialize it to 0. Use this variable as an index into the new array (let us call it temp), starting at 0.
   • Set up a loop in which each iteration copies array[i] to temp[j]. At the end of each iteration, increment both indexes in circular fashion, using the same "mod" increment that you needed for the add() and remove() methods. Caution: remember that the two arrays have different lengths...

     Note that the range of this loop is easy to specify: you will need to copy exactly itemCount values, so a simple for loop with a loop counter should work well here.

   • When the copying loop has completed, swap out the old array for the new. Then set the front index to 0, and the rear index to the final value of j (which will normally be the next available slot in the new array).

7. clear() must remove all values from the Queue, without changing its current capacity. However, for simplicity it should also reset both the front and rear indexes back to 0.
8. reset() must completely restore the Queue to its original state, just after it was first constructed. This means that all values should be removed, and also that the current array should be replaced by a new array with the original capacity.
6. Once you have completed the implementation of the new Queue class, try to build your Lab05 project. Of course if you encounter any compiler errors, you will have to fix them all before you can proceed...
7. Run the project. You should now verify the application behavior as described in the Introduction. You should experiment with several sequences of adding and removing data. Verify especially that the graphical representation of the Queue changes in the way you would expect.

When your project is complete and working correctly, demonstrate it to your lab instructor. Then, before you exit NetBeans, clean your Lab05 project. Finally, before you logout, open a terminal window and use the cd command to enter your csci/202/labs directory. Then create a JAR file of your Lab05 project folder, using the command

jar cf Lab05Project.jar Lab05