In the last lab you used a linked list to implement a queue. The linked list was a good choice for a queue because the queue does not need index access to stored data. A stack is another type of list data structure that does not need index access. A stack only adds to or removes from one end of the list.
The file LinkedList.java contains
the linked list class that you created in the last lab. The class
already has a method to add to the beginning of the list, but to use it
as a stack you will need to complete the removeFirst
method. Remember to code in small pieces and test thoroughly.
Proceed only when you are sure that your class is functioning
properly.
The file PaintBucket.java contains a simple drawing program, similar to the one you created in a previous assignment. One difference between this program and the one you created is that it draws to an image instead of directly to the window. This drawing program also only has two tools, draw oval and fill. Complete the fill method so that when the user clicks while the fill tool is selected the program fills in the clicked region of the drawing with the specified color.
The fill method has four parameters. The first parameter, raster, is a two dimensional array of ints that represents all of the pixels in the drawing window. The second parameter, fillColor, is the color to fill the specified region with. The third a fourth parameters specify the coordinates of the pixel that the user clicked on. The fill method can be written very easily using recursion. Complete the method so that if the raster at the specified row and column is already the fill color it does nothing. If the raster at the specified row and column is not already the fill color, set the specified pixel to be the fill color. Then recursively call the fill method on the four neighboring pixels if they are the same color as the specified pixel before it was changed to the fill color. Be sure you do not access an array element that is out of bounds. Also be sure that the recursion will terminate. Test your code on a very tiny oval, such as 10 by 10 pixels. Also test it on a small oval that is not entirely in the window. Now test your code on a large oval. It's okay if your program crashed on the large oval, you will soon fix it. Do you know why it crashed?
In class we talked about how all recursive algorithms can be rewritten to not use recursion. The reason this can be done is that the Java runtime uses a stack to know where in the program to return to after a method finishes executing. This is also why the runtime error produced with infinite recursion is called stack overflow. The call stack also stores the local variables of a method so that the state can be restored after a method call.
The paint bucket program fails if the area being filled is
large because the Java runtime ran out of memory for the call
stack. Now that you have learned (and created) stacks, you can
create a looping version of the paint bucket program that will not
crash. Create a new fill method (Don't modify or delete the old
one!) that uses a loop and a stack instead of recursion. Also
change the mouseReleased method to call the new fill
method. The looping version of the fill algorithm should begin by
pushing the coordinates of the initial fill location onto an empty
stack. Then, while the stack is not empty it should pop the top
of the stack. If the top coordinate is of the same color as the
initial click location, then it should set the color of the pixel
at the coordinate and push the coordinates of each of the four
neighboring pixels onto the stack.
Submit a zip file of your code on the course Inquire site that uses your last names as the file name.