Lab 4: Queue implementations

Lab 4: Queue implementations
Goal:
• Implement a Queue class using a linked data structure: Class QueueLinked
• Implement a Queue class using a circular array: Class QueueArray
1. The first implementation you will use a linked structure similar to the linked structure
used in implementing the Queue ADT. In this case, there must be a way to add items to the back
of the list and remove items from the front of the list in O(1). use the same class Node you used
in lab 3 (node.py).
2. The second implementation will use a circular array for storing the items in the queue.
There are different ways of doing this but they share the idea presented in the picture. Namely
elements are added to the rear of the queue using the next “free entry” in an array. (rear may be
the index of the current last index storing an item in the queue or one beyond it. Elements are
removed from the front (read in the picture) of the queue. Elements are added to the queue at the
rear (write) of the queue. The indices in front and rear are incremented as elements are added and
deleted from the queue. All arithmetic is modulo the size of the array structure allocated to
store the queue. Care must be taken in distinguishing a full from an empty queue and this can be
done in different ways. Use the following formula (read pointer == ( write pointer + 1 ) %
(len(array)))
Note that in this implementation the maximum number of items the queue can hold is one less
than the size of the array-like structure allocated. When a user of your Queue class specifies its
capacity, you may have to take this into account so that the queue can actually store capacity
items. This means that you need to create an array with [None] * (capacity + 1). In the figure
below, buf is an array:
1
CPE202 Spring 2020
Implementation Specs
Make sure that you follow the design recipe (write tests in lab4_tests.py). (Your submission
files do not need to contain pseudo code.) Note: Your class names, function names and file
names must follow the spec of the lab. Every class needs to have __init__, __eq__, and
__repr__.
Singly Linked List:
● Put the following class in the node.py file.
● Use the following data definition for the linked list:
class Node:
"""A Linked List is one of
- None, or
- Node(val, next) : A Linked List
Attributes:
val (any) : the payload of any type
next (Node) : a Linked List
"""
def __init__(self, val, nxt=None):
self.val = val # the payload
self.next = nxt # a reference to the next node
● Do not forget to implement __eq__ and __repr__ methods for Node class.
2
CPE202 Spring 2020
QueueLinked
● Create a new file, queue_linked.py, and put the code for QueueLinked in it.
● Import the Node class from node.py.
● create a member variable called capacity (self.capacity), which represents the number of
items the queue can hold. The initial value of capacity shall be passed as an argument to
the constructor. If the argument is not passed, the capacity shall default to 2.
● create a member variable called num_items (self.num_items), which stores the number of
items in the Queue. The initial value of self.num_items should be 0.
● create a member variable called front (self.front), which points to the front of the queue
(a Node object). It should be initially None because the queue is empty.
● create a member variable called rear (self.rear), which points to the back of the queue (a
Node object). It should be initially None because the queue is empty.
● Write a method, dequeue, for dequeuing an item. When a user tries to dequeue from an
empty Queue, your dequeue method should raise an IndexError.
● Write a method, enqueue, for enqueuing an item. When a user tries to enqueue an item to
a full Queue, your enqueue method should raise an Index Error.
● Write a method, is_empty, which returns True if the queue is empty.
● Write a method, is_full, which returns True if the queue is full.
● Write a method, size, which returns the number of items in the queue.
● You may include other functions/methods.
QueueArray:
● Create a new file, queue_array.py, and put the code for QueueArray in it.
● create a member variable called arr (a variable defined in QueueArray class: self.arr) in
the QueueArray class. The arr is a python built-in list data construct, but you may not use any
functions provided by list including append(), pop(), index(), and list slicing, list
concatenation (+), except for [None] * self.capacity operation and accessing items by
indices using [].
● create a member variable called capacity (a variable defined in QueueArray class:
self.capacity), which stores the size of the array. The initial value of capacity shall be passed as
an argument to the constructor. If the argument is not passed, the capacity shall default to 2.
● Initialize the queue by creating an array containing as many Nones as self.capacity + 1:
[None] * (self.capacity + 1) will create an array of Nones. Assign the array to self.arr.
● create a member variable called num_items (a variable defined in QueueArray class:
self.num_items), which stores the number of items in the Queue. The initial value of
self.num_items should be 0.
3
CPE202 Spring 2020
● create a member variable called front (self.read), which points to the front of the queue
(an index in the self.arr)
● create a member variable called rear (self.write), which points to the back of the queue
(an index in the self.arr)
● Write a method, dequeue, for dequeuing an item. When a user tries to dequeue from an
empty Queue, your dequeue method should raise an IndexError.
● Write a method, enqueue, for enqueuing an item. When a user tries to enqueue an item to
a full Queue, your enqueue method should raise an Index Error.
● Write a method, is_empty, which returns True if the queue is empty.
● Write a method, is_full, which returns True if the queue is full.
● Write a method, size, which returns the number of items in the queue.
● You may include other functions/methods.
Submission
Submit all your files including lab4_tests.py to Gradzilla and then to Canvas.
4