ATTACHED SOLUTION to Lab 4 - Abstract Data Types

Learning outcomes
By the end of this lab, you will be able to:

Define the new abstract data type called the queue
Implement a queue using Python lists
Compare the runtime efficiency of two different implementations of an ADT using simple profiling
Brainstorm different implementations for an ADT

This week we learned about stacks, a very simple ADT that always removes items in "reverse" order, so that the most recently added item is the first that gets removed. A queue is another simple ADT that does the opposite: 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 line (of people at the grocery store, for example), queues are a natural choice. (You've been working with priority queues in Assignment 1. This is another ADT that elaborates the concept of a queue to add in the notion of priority.)

Here are the operations supported by the queue ADT:

__init__: create a new empty queue
is_empty(): return True if the queue is empty (and False otherwise).
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).

Let's test the performance of our Queue class against Stack from lecture. To start, open timequeue.py. Using the technique from class, run some experiments to measure the time it takes to enqueue and dequeue items as the size of the list grows. Feel free to add your own queue-manipulation methods for experimenting! We recommend having queue sizes in the 10 000's to see some noticeable growth in the time taken.

You should see that at least one of your queue operations takes linear time (i.e., time to execute the operation grows proportionally to the size of the queue). Make sure that both you and your partner can explain to each other why this is the case.

Then, spend the remaining time brainstorming ways of changing your Queue implementation to make both enqueueand dequeue run in constant time (independent of the size of the queue). Be creative, and have fun!