By the end of this lab, you will be able to:
matplotlib.Download all files and put them into your labs/lab4 folder.
stack.py (Task 1)myqueue.py (Task 2)timequeue.py (Task 3)Open stack.py file and first review the given stack implementation and the size
function we discussed in lecture.
Complete the following tasks. Note that you should write these as top-level functions, not stack methods.
While you may use a temporary stack (as we did in lecture for size), do not use any other
Python compound data structures, like lists.
Write a function that takes a stack of integers and removes all of the items that are greater than 5. The other items in the stack, including their relative order, should remain unchanged.
Write a function that takes a stack and returns a new stack that contains two copies of every item in the old stack. We’ll leave it up to you to decide what order to put the copies into in the new stack.
Note that because nothing else is specified in this function description, the old stack should remain unchanged when the function returns.
You learned in the readings this week that a queue is another simple ADT that works in the opposite way to a stack: when asked to remove an item, a queue always removes the item that was added first, making it a “first-in, first-out” (FIFO) data structure. Any time we’d like to model a lineup (of people at the grocery store, for example), queues are a natural choice.
Here are the operations supported by the Queue ADT:
__init__: initialize a new empty queueis_empty(): return whether the queue is empty.enqueue(item): add item to the back of the queue.dequeue(): remove and return the front item, if there is one, or None
if the queue is empty.Your first task is to implement the Queue class found in myqueue.py. We strongly
recommend you review the stack implementation from lecture to remember how we used a list to implement the
Stack class.
After you’ve finished, complete the functions product and product_star in
myqueue.py, which compute the product of all numbers in a queue (but have an important
difference - read the docstring carefully and compare them!). Notice that these are defined outside
the class (they are not indented). That makes them ordinary top-level functions, not methods.
Now that you have a complete working implementation of Queue, we’ll introduce a new technique
for evaluating your code: running timing experiments to see how quickly it runs. This is a very simple form
of software profiling, which is the act of measuring the amount of resources (like time) a program
takes while its running. In fact, PyCharm has a built-in profiler, but that’s more advanced than what we
need for this course, and so you’ll use a simpler profiling library that comes with Python.
Your first task is to open timequeue.py and follow the instructions contained within it
to complete the timing experiment.
After you’ve run your experiment, you should notice that your two queue operations
enqueue and dequeue behave quite differently. While one seems to take the
same amount of time no matter how many items are in the queue, the other takes longer and longer as
the number of items are in the queue.
Compare your notes with other groups. Which end of a Python list seems to be the “slow” end?
After you’ve completed that, let’s make our timing experiment a bit more visually appealing. Rather than print out a bunch of numbers, it would be much more satisfying to take these values and plot them on a graph to display.
To do this, you’ll need to do a few things:
Implement time_queue_lists, a modified version of your timing experiment function that
returns a tuple containing three lists:
enqueue for each queue sizedequeue for each queue sizeNote that each of your lists should have the same length.
To actually plot the data, we’ll use the Python library matplotlib, which is an
extremely powerful and popular library for plotting all sorts of data.
If you’re on a lab machine, you already have this library installed. If you’re on your own machine, you should have already installed this library by following the CSC148 Software Guide. (Look for the section on installing Python libraries.)
Add the statement import matplotlib.pyplot as plt to the top of
timequeue.py, and make sure you can still run your file without error.
To get a basic 2-D plot of your timing data, work your way through the first part of this guide. (Ignore all of the references to “numpy”, which is another Python library we aren’t using in this course. Also ignore the other sections after the first one; the whole tutorial is pretty long!)
You can use an x-axis range of 0-200000 and a y-axis range of 0-0.02 (feel free to adjust the y-axis depending on how long the experiments take to run on your computer).
If you still have time, explore! There’s lots of customization you can do with
matplotlib to make your graphs really pretty.
As we discussed in lecture, one of the most common applications of stacks is in implementing an “undo” or “back” functionality in various contexts, from website browsing to editing documents.
Your task here is to write a program which repeatedly prompts the user for a string, and stores the strings in a stack. Except when the user types “UNDO”, rather than storing the string “UNDO”, it prints out the most recently stored string, and removes it from the stack.
Once you have that working, implement redo functionality using a second stack: when the user types “REDO”, your program should print the most recently “undone” string, and push the string back onto the original stack. The user should be able to “REDO” multiple times to restore multiple strings in a row. What should happen if a user types in “REDO”, and then begins entering new strings? Get some ideas from here.