1 Queues

In this lab, you're going to write a Queue class.

Your queue class should be called Queue and it should go in a file queue.py. It should have the following methods:

• Constructor (__init__) that takes no arguments and makes an empty queue.
• enqueue(item) to add a new item to the back of the queue.
• dequeue() to remove and return the next item at the front of the queue.
• peek() to return, but don't remove, the next item at the front.
• size() to return the number of items currently in the queue.

You can use either a linked list or an array to implement your queue, as we discussed in class. Either way you do it, every method must have \(O(1)\) running time (possibly amortized).

2 Testing your queue

There are some basic sanity checks for your Queue class, and as usual you should also do some more extensive testing of your own to make sure your queue works correctly.

To see how efficient your queue is, I want you to write a program testqueue.py that does the following:

1. Creates a new instance of your Queue class.
2. Alternates between calling enqueue and size 1 million times to insert a million numbers into the queue. (I don't care what the numbers are; that doesn't really matter.)
3. Alternates between calling peek and dequeue 1 million times to completely empty out the queue
4. Prints out how much time (in seconds) it took to do all of that.

To get the timing, I want you to use the clock() method from Python's time package. Specifically, you'll do something like this:

1
2
3
4
5
6

import time
 
start = time.clock()
# DO YOUR THING HERE
end = time.clock()
print("The time elapsed was", (end-start), "seconds.")

There are no auto-tests for the testqueue.py program, but you should explain in your README.txt what times you got for this. I will also run your code myself after you submit.

3 Deque in Python

Did you know that Python also has a built-in queue? It's called deque and is part of the collections module.

Add another section to your testqueue.py above that does the same exact test, but using Python's collections.deque class. You'll have to look at the documentation to figure out which methods in that class correspond to our definition of enqueue, dequeue, peek, and size! Ask if you need help to figure that out.

After this, running your testqueue.py program should test both your own Queue class as well as Python's deque, and print out both times separately. Add some more discussion to your README.txt about the timing results you see here.

4 Going futher

Experiment with more options! If you implemented your queue with an array, do it with a linked list. If you implemented with a linked list, try it with an array. Try what would happen if you used Python's regular lists, with pop() as dequeue and insert(0, item) as enqueue? Be sure to add some more discussion to your README.txt if you do this.