Lab #3

? practice using stacks, implement a queue, then practice using them You should work on these on your own before Thursday, and you are certainly welcome to come and get some guidance from your TA on working through these exercises. There will be a short quiz at the end of the lab based on these exercises. setup stacks 1. Navigate to sub-directory of csc148 called lab03, and copy the ?le stack.py into it from http://www. cdf.toronto.edu/~csc148h/winter/Labs/lab03. 2. Open stack.py in PyCharm (or another IDE) 3. Create a new ?le in lab03 called stack client.py. You'll probably need to import the stack module to get started in stack client.py. use stacks Now write code in the if name == ’ main :’ block of stack client.py that will: 1. Create a new stack. 2. Read text typed from the keyboard, using input(’Type a string:’). 3. Add the typed string to the stack. 4. Repeat the ?rst two steps until the string end is typed 5. Remove the strings, one-by-one, from the stack and print them. Show your work to your TA when you're done. Above the if name == ’ main :’ block, write a function called list stack that takes a list and a stack as arguments, has a None return, and does the following: 1. Adds each element of the list to the stack. 2. Removes the top element from the stack. If the element is a non-list, it prints it. If the element is a list, it stores each of its elements on the stack. 3. Continue the previous step until the stack is empty. Check for an empty stack, rather than causing an exception to be raised! Try out your list stack function on: ? [1, 3, 5] ? [1, [3, 5], 7] ? [1, [3, [5, 7], 9], 11] Show your work to your TA when you're done. 1 implement queue A queue is another abstract data type (ADT) that stores a sequence of values. Unlike a stack, where the last item in is the ?rst item out (LIFO), a queue makes sure that the ?rst item in is the ?rst item out (FIFO). This models the lineup at a co?ee shop or vending machine. The operations your queue will support are: add: add an object at the end of the queue. remove: remove and return the object at the beginning of the queue. is empty: return True if this queue is empty, False otherwise. To implement a queue you should 1. Open csc148 queue.py in PyCharm or another IDE. 2. Complete all the unimplemented methods and store csc148 queue.py in your lab03 directory. 3. Download testqueue.py from http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab03, open it in PyCharm, and run it to see whether your implementation of Queue passes the unit tests in it. Create an if name == ’ main :’ block in a new ?le queue driver.py1 and add some more code to: 1. Create a new queue. 2. Prompt for an integer at the keyboard, and add it to the queue. Remember that the built-in function input(...) returns a string, from which you can construct an integer using int(...). 3. Repeat the previous step until you have read in, but not stored, 148. 4. Print the sum of all the numbers that were in the queue. Now above the if name == ’ main :’ block, create a function list queue which takes a list and a queue as arguments, and does the following: 1. Adds each element of the list to the queue. 2. Removes the top element from the queue. If the element is a non-list, print it. If the element is a list, store each of its elements on the queue. 3. Continue the previous step until the queue is empty. Check for an empty queue, rather than causing an exception to be raised! Try out your queue list function on: ? [1, 3, 5] ? [1, [3, 5], 7] ? [1, [3, [5, 7], 9], 11] Show your work to your TA when you're done. 1Of course, you'll need to import csc148 queue create unit tests for stack Emulate (that is, copy intelligently) the unit tests in testqueue.py to create unit tests for our Stack class. Of course you will slightly modify the tests, since a stack isn't a queue. Save your stack tests in teststack.py. In this week's lecture we have some pointers on how to create unit tests. Show your work to your TA when you're done. addition exercises For the examples above that use list stack and list queue, draw a diagram that shows the elements remaining on the stack/queue after each print statement. Show the elements in order, labelling the top/bottom or front/back.