In this lab you are going to implement linked lists that represent two new data structures: Stacks and Queues. We will discuss these data structures over the next few days, but today is as good a day as any to start. These are covered in Chapter's 6 & 7 in the textbook.
The file linked_list.py contains a linked list class similar to what you have been using for two weeks. Take special notice that this version has the "last" reference that we discussed in class, and it does not have a method for removing arbitrary elements. The only thing that you have not implemented in labs as of yet is the "add_front" method. Go ahead and fill this method in before you continue.
Create two new classes: Stack and Queue. These both should inherit from linked list. A Stack is a class of data structure, which implements two key methods:
As you will notice, with a Stack you are always retrieving the most recent thing placed in the data structure. For this reason, stacks are commonly referred to as Last In-First Out, or LIFO, data structures. This is very similar to a stack of plates as you would find in the Commons.
Queues, on the other hand, are referred to as First In-First Out, or FIFO, data structures. The data you retrieve is always the oldest from within the data structure. For example, the line of people waiting to get their food at the Commons is a queue. For this functionality, queues implement their own three key methods:
Each of your classes should also prevent anyone from using methods that go against the behavior of that data structure. For example, the Stack class should prevent someone from calling the add_last method. You can do this by overriding the method in Stack, and raising an exception.
Before you continue, you should test both of these structures thoroughly.
The file maze.py contains a simple maze traversal program. The maze is simply represented by a 2-d list of integers, either 0 or 1. 0 means that the cell is empty, 1 means the cell is occupied. You will write code, using a queue, that will determine if you can navigate between some start point, and some end point within the maze.
Write the can_traverse method to use a loop and
a queue. The queue version should begin by
adding the location of the start cell to an empty queue. Then, while
the queue is not empty it should remove a cell from the queue. If the
removed cell is the end cell then the loop should stop and the method
should return true. If the cell is not the end cell it should add all
of its neighboring cells that are valid to the queue, and mark the
current cell as visited. If the queue
becomes empty without ever traversing to the end cell, then the method
should return false.
What is the Big-O complexity of this method? Let n = WIDTH *
HEIGHT = the number of cells in the map. Write up an analysis of
the Big-O complexity of the can_traverse method in a file
called maze_analysis.txt. Include this file in your
submitted directory.
The file paint_bucket.py (you will also need the file ovals.gif for this program) contains a program that draws an image with several overlapping ovals. Complete the program so that clicking on the image fills regions like a paint bucket tool in raster drawing programs. When the mouse is clicked, the program calls the fill_region_recursive method and passes it the click location and the color of the pixel that was click. The method should set all pixels that neighbor the clicked pixel and are the same color to be the fill color.
The provided fill_region_recursive method implements a recursive solution to the problem. It simply colors in the specified point, and attempts to fill in the adjacent points as well. Test this code on the tiny oval at the center of the image first. If that works, test this code on a larger region. The program likely crashed on the large oval, and you will soon fix it. Do you know why it crashed?
As it turns out, any recursive method can be rewritten using a stack. This is because Python uses a stack (referred to as the "call stack") to keep track of where in the program to return when the program finishes executing. The call stack also stores local variables of a method so that their values can be restored after a method call.
The paint bucket program fails if the area being filled is large
because the Python interpreter 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 called full_region_loop
that uses a loop and a stack instead of recursion. Also change the
mouse click callback method to call the
new fill_region_loop 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.
We have seen two different problems, which queues and stacks are
very well suited at solving, respectively. What happens if we use
the opposite data structure? For each of the above programs, create
a version that uses the opposite data structure. Is there any funny
behavior that becomes apparent? Or do they seem to work just the
same? Write up your findings in a text file
called StackQueueFindings.txt, and include it in your
submitted zip file.
Submit a zip file of your code on the course Inquire site that uses your last names as the file name.
