CMPSC-132: Programming and Computation II
Fall 2018
Lab #10
Due Date: 10/26/2018, 11:59PM
Instructions:
– The work in this lab must be completed alone and must be your own. Do not copy code
from online sources. That is considered plagiarism.
– Use the starter code provided on this CANVAS assignment. Do not change the function
names or given started code on your script
– The file name must be LAB10.py (incorrect name files will get a -1 point deduction)
– A doctest is provided as an example of code functionality. Getting the same result as
the doctest does not guarantee full credit. You are responsible for testing your code
with enough data as possible.
– Each function must return the output (Do not use print in your final submission otherwise,
you will get a -1 pt deduction)
– Do not include test code outside any function in the upload. Remove all your testing code
before uploading your file. Do not include the input() function in your submission.
Goal:
[10 pts] In class, we discussed the abstract data type Queue. A queue is a collection of items where
the addition of new items happens at one end (tail) and the removal of existing items occurs at the
other end (head) (FIFO). Use the Node class (an object with a data field and a pointer to the next
element) to implement the queue data structure with the following operations:
Queue() creates a new queue that is empty. It needs no parameters and returns nothing
enqueue(item) adds a new Node with value=item to the tail of the queue. It needs the value
of the Node and returns nothing.
dequeue() removes the head Node from the queue. It needs no parameters and returns the
value of the Node removed from the queue. The queue is modified.
isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a
boolean value.
len() returns the number of items in the queue. It needs no parameters and returns an
integer.
EXAMPLE
>>> x=Queue()
>>> x.isEmpty()
True
>>> x.dequeue()
‘Queue is empty’ # None is fine too
>>> x.enqueue(1)
>>> x.enqueue(2)
>>> x.enqueue(3)
>>> x.enqueue(4)
>>> print(x)
Head:Node(1)
Tail:Node(4)
Queue:1 2 3 4
>>> x.isEmpty()
False
>>> len(x)
4
>>> x.dequeue()
1
>>> x.dequeue()
2
>>> x.dequeue()
3
>>> x.dequeue()
4
>>> x.dequeue()
‘Queue is empty’
>>> print(x)
Head:None
Tail:None
Queue:
>>> x.enqueue(3)
>>> x.enqueue(2)
>>> print(x)
Head:Node(3)
Tail:Node(2)
Queue:3 2
>>> x.dequeue()
3
>>> print(x)
Head:Node(2)
Tail:Node(2)
Queue:2
NOTE: To grade this assignment, the grading script will perform a series of mixed queue
operations and compare the final status of your queue. Verify that all your methods work correctly
when mixed together.
Tips:
– Starter code contains the special methods __str__ and __repr__, use them to ensure the
queue operations are updating the elements in the queue correctly
– When calling dequeue, you always need to check the size of the queue first to ensure there
are elements in the queue.
– Remember that calling dequeue when the size is 1 should update the head and tail pointers
to None
Deliverables:
Submit your code in a file name LAB10.py to the Lab10 CANVAS assignment before the
due date