USE PYTHON3; DO NOT IMPORT ANY PACKAGES

Please do all of question 1(which has 3 parts)

Here is the code format (with doctests) in the text editor for your reference:

# Question 1.1 class Collection: """ A class to abstract the common functionalities of Stack and Queue. This class should not be initialized directly. """

def __init__(self): """ Constructor. """ # YOUR CODE GOES HERE # self.items = ... self.num_items = ...

def size(self): """ Get the number of items stored. """ # YOUR CODE GOES HERE # return ...

def is_empty(self): """ Check whether the collection is empty. """ # YOUR CODE GOES HERE # return ...

def clear(self): """ Remove all items in the collection. """ # YOUR CODE GOES HERE #

# Question 1.2 class Stack(Collection): """ Stack class.

>>> stk = Stack() >>> stk.size() 0 >>> stk.is_empty() True >>> str(stk) '(bottom) (top)' >>> stk.push(None) Traceback (most recent call last): ... ValueError: item cannot be None >>> stk.push('LAB 10') >>> stk.size() 1 >>> stk.is_empty() False >>> stk.push('DSC') >>> stk.push(20) >>> stk.size() 3 >>> str(stk) '(bottom) LAB 10 -- DSC -- 20 (top)' >>> stk.pop() 20 >>> stk.pop() 'DSC' >>> stk.peek() 'LAB 10' >>> stk.size() 1 >>> stk.clear() >>> stk.pop() >>> stk.peek() """

def push(self, item): """ Push `item` to the stack. """ # YOUR CODE GOES HERE #

def pop(self): """ Pop the top item from the stack. """ # YOUR CODE GOES HERE # return ...

def peek(self): """ Peek the top item. """ # YOUR CODE GOES HERE # return ...

def __str__(self): """ Return the string representation of the stack. """ # YOUR CODE GOES HERE # return ...

# Question 1.3 class Queue(Collection): """ Queue class.

>>> que = Queue() >>> que.size() 0 >>> que.is_empty() True >>> str(que) '(front) (rear)' >>> que.enqueue(None) Traceback (most recent call last): ... ValueError: item cannot be None >>> que.enqueue('LAB 10') >>> que.size() 1 >>> que.is_empty() False >>> que.enqueue('DSC') >>> que.enqueue(20) >>> que.size() 3 >>> str(que) '(front) LAB 10 -- DSC -- 20 (rear)' >>> que.dequeue() 'LAB 10' >>> que.dequeue() 'DSC' >>> que.peek() 20 >>> que.size() 1 >>> que.clear() >>> que.dequeue() >>> que.peek() """

def enqueue(self, item): """ Enqueue `item` to the queue. """ # YOUR CODE GOES HERE #

def dequeue(self): """ Dequeue the front item from the queue. """ # YOUR CODE GOES HERE # return ...

def peek(self): """ Peek the front item. """ # YOUR CODE GOES HERE # return ...

def __str__(self): """ Return the string representation of the queue. """ # YOUR CODE GOES HERE # return ...

Thank you for your work!

Question 1 In this question, you will implement stack and Queue backed by Python lists. You can use list built-in functions in your implementation, but you are not allowed to use len() function. Every method in this question can be implemented within 5 lines, but it is ok if your implementation is longer. Part 1: Collection In this part, you will implement a Collection class, which will be the parent class for both stack and Queue. This class is used to abstract all shared functionalities between Stack and Queue, thus you should not initialize a collection instance directly. You should implement the following methods: _init__(self) The constructor for both stack and Queue. You should initialize these two instance attributes: items (list): a list to store all items, initialize it with an empty list. num_items (int): the number of items stored in this collection, initialize it with 0. size (self) Return the number of items stored. is_empty (self) Return True if no items are stored, and False otherwise. clear (self) Remove all items in this collection and update the instance attributes accordingly. Part 2: Stack In this part, you will implement the functionalities of a stack. The top of the stack should always be at the end of the items list. Make sure that all operations have 0(1) complexity. You should implement the following methods: push (self, item) Add the item to the stack. If the item is None, raise a ValueError with the message "item cannot be None". pop (self) Remove the top item from the stack and return the removed item. If the stack has nothing to remove, return None. peek (self) Return the top item without removing it. If the stack has nothing stored, return None. _str_ (self) Return the string representation of the stack. The formats are as follows: 0 items: "(bottom) (top)" 1 items: "(bottom) itemo (top)" More than 1 items: "(bottom) itemo -- item1 (top)" Where itemk is the string representation of the item at index k of the items list, instead of the actual string "itemk". Part 3: Queue In this part, you will implement the functionalities of a Queue. The front of the queue should always be at the start of the items list. You should implement the following methods: enqueue (self, item) Add the item to the end of the queue. If the item is None, raise a ValueError with the message "item cannot be None". dequeue (self) Remove the front item from the queue and return the removed item. If the queue has nothing to remove, return None. peek (self) Return the front item without removing it. If the queue has nothing stored, return None. _str__ (self) Return the string representation of the queue. The formats are as follows: O items: "(front) (rear)" 1 items: "(front) itemo (rear)" More than 1 items: "(front) itemo -- item1 (rear)" Where itemk is the string representation of the item at index k of the items list, instead of the actual string "itemk