CPSC 170 Lab 11: Queues

Implementing Queues

The file Queue.java contains an interface for the queue abstract data type. Create a class that implements the Queue interface using either an array or a linked implementation. You can use your code from previous labs, but it is not sufficient to create a class that uses an array list or a linked list as an instance variable. If you choose to implement the queue using an array, you should implement it using a circular array. If you choose to implement the queue using links, you will need an implementation with pointers to both the begining and end of the list. Remember to code in small pieces and test thoroughly. Proceed only when you are sure that your classes are functioning properly.

Maze Solver

The file Maze.java contains a Java class that represents a maze as a two dimensional array cells that are either paths or walls. The file MazeSolver.java contains the outline for a program that animates finding a path through a maze. The program uses a timer that calls the actionPerformed method every half a second. This method calls the update method, which currently does nothing. You should complete the update method so that it emulates a call to the recursive method that we developed in class. Each call to the method will update the current location instance variable. When the current location reaches the end of the maze the animation should stop. You will need a stack to simulate the recursive call stack. You can test your program with the maze in the file maze1.txt. When you have the animation working with a stack try replacing the stack with a queue. How is the animation different? What is the significance of this difference?


The files Mandelbrot.java and InteractiveMandelbrot.java contain a program that allows the user to interactively render high resolution images of the Mandelbrot set to an image file. Run the program to see how it works. Look at the code for the program as well. Notice that the program generates low resolution images (which can be created quickly) so that the program does not become unresponsive when the user clicks to zoom in. When the user presses the space bar, it generates a high resolution image and saves it to a file. While the program generates the high resolution image it is not possible to zoom in.

Fix this program to allow the user to continue to interact with the program while it is generating the high resolution image. Hint: if a second thread creates the high resolution image then the main thread can continue to handle mouse events and render low resolution images. If the user presses the space bar while the second thread is rendering an image it should use a queue to store the parameters of the next image to render instead of creating yet another thread.


You can use this program to generate movies of zooming into a fractal. Use the interactive program to zoom into a cool looking, deep part of the fractal. Then, instead of just generating a high resolution image of the current screen, create a collection of images, each just a little closer to the end image. Do this by interpolating between the initial dimensions and the final dimensions by an increasing fraction, each time rendering the result to an image file. These image files can then be turned into a movie.

To submit your code: Tar the files in your lab11 directory and copy the tgz file to the directory /home/staff/bouchard/CPSC170A/lab11. Be sure to name the tar file with your names, not lab11.tgz.