$ mkdir ~/cs170/labs/lab19 $ cd ~/cs170/labs/lab19
You should, by this point, have a fairly well functioning linked list object. Today, we are going to start looking at how and why you might use a linked list. Obviously you are using a linked list for the assignment, but what about other examples. One example of why you would use them is in the creation of a different class of data-structure, known as a Stack.
A Stack is known as a Last-In, First-Out (LIFO) data structure. That means that the data that was most recently added to the structure is the first and only thing that can be removed. In order to get to data that was added earlier to the stack, you have to remove all of the things that are above it. The interesting thing about stacks are that you have been implicity using one, without even knowing it.
First things first, you need to copy your LinkedList
class into your current directory.
$ cd ~/cs170/labs/lab19 $ cp ~/cs170/labs/lab18/linked_list.py .
Create a new file called stack.py. In this file, you should
define a class Stack, which will inherit
your linked list class. You will need to import
linked_list at the top of your file so that you can have access
to your LinkedList class.
Your class must have the five key methods for a stack, plus one additional method for testing purposes:
push - Takes data as a parameter, and
adds it to the top of the stack.
pop - Removes the node from the top of the stack,
and returns its data. If the stack is empty, you should print an
error message and return -1.
peek - Returns the data from the node on the top
of the stack without removing it. If the stack is empty, you should
print an error message and return -1.
size - Returns an integer, the number of items
currently in the stack.
is_empty - Returns a boolean, True if the
stack currently has no data. False otherwise.
__str__ - Returns a string representation of the
current format of the stack.
Make sure that your methods work appropriately. Think about special cases you might need to handle for pop and peek!
>>> my_stack = Stack() >>> my_stack.push(1) >>> my_stack.push(2) >>> my_stack.push(3) >>> print(my_stack) top -> 3 -> 2 -> 1 -> bottom >>> print(my_stack.size()) 3 >>> print(my_stack.pop()) 3 >>> print(my_stack) top -> 2 -> 1 -> bottom >>> my_stack.pop() >>> my_stack.pop() >>> my_stack.pop() No more elements in the stack. >>>
Your operations here are pretty straight forward. A majority of them you already have written, you just need to "re-name" them through inheritance.
push is essentially insert, where the location to
insert is ALWAYS 0. To simplify your size
computation, however, you should maintain a size attribute that
increments with every push.
pop is really the only new method. You need to
essentially remove the front element, and return the data from
that element. To remove the front element, you just need to
move the head reference. You will need to store the data in
that node before you remove it, so that you can return it
later. Don't forget to decrement your size attribute!
You would be able to do the next portion of the lab pretty easily with just the built in python list. However, there is this notion of Abstract Data Types (ADTs). An ADT is simply an interface that the data type must follow to be representative of this type. We explicity followed the ADT for a Stack above. However, the built in python list does not explicitly follow the ADT.
Write a class class called StackList, which inherits
the built in list class (notice the punctuation). This
class should have the same methods as the linked list
Stack class. The methods you use, however, will be
different.
A very useful tool for a majority of paint programs is the tool. The paint bucket tool allows the user to click on an enclosed area, and it fills that enclosed area with the current fill color. A very common way that this is accomplished is by using a stack to keep track of the locations of the image that need to be filled.
You are given a program that has a recursive method to solve the paint bucket problem. However, this program will crash if you select certain regions of the image to fill. This is because there are a lot of pixels to fill, and the recursion limiter of python prevents the program from running.
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. What you will do today, is modify this program so that it uses a loop and a stack instead.
The file
paint_bucket.py
(You will also need the file
ovals.gif) contains
a program that draws an image with several overlapping ovals. There
are a lot of methods already defined for you. The method you are
modifying is fill_region_loop. You should read over
the Pre and Post conditions of the built in helper file carefully,
so that you can understand how to use them effectively.
fill_region_loop will be using a stack in order to
accomplish its goal.
You should initialize the stack with the coordinate the user clicked on. Then, while the stack is not empty, you pop the item off the top of the stack and process it. The processing portion is essentially the same: if the current pixel color is the color to fill, color it in. The only difference is that instead of making a recursive call, you will simply push all of the neighbor's coordinates onto the stack.
You should be able to use the size attribute of the stack to determine whether there are still elements in the stack to process.
Tk can load any ".gif" image directly onto the canvas. Find an image that is not a black and white image, and load it onto the canvas. Pick a region of this image, and modify the program that you can click on the region and color it in. Do you notice anything peculiar about this behavior?
This program relies on the pixel colors to be exactly the same in order to fill them in. However, in real images this property is extremely rare. Instead, we can use a process known as in order to get around this.
Define a global parameter FUZZ_FACTOR which is some
integer value that you can modify easily. For a decent start,
choose a value 10. If the euclidean distance of the color of the
current pixel and the color to fill is less than the fuzz factor, go
ahead a fill that pixel in.
When you have finished, create a tar file of your lab19 directory. To create a tar file, execute the
following commands:
cd ~/cs170/labs tar czvf lab19.tgz lab19/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
19. Make sure you include a header
listing the authors of the file.
