Important:
ECS 32B – Introduction to Data Structures Homework 03
Due: Friday, April 30, 2021, 5:00pm PST
Download the hw03.py file from Canvas -> Homework -> Homework03.
Write your code (in Python3) in the designated positions in hw03.py.
Thepurposeofthehomeworkistopracticeusingthelineardatastructureswehavelearnedinclass so far, i.e., stack, queue, linked list.Problem 1 must be solved using queue. Problems 2 and 3 must be solved using linked lists.The definition for Queue and Node classes are included in hw03.py. They must be submitted together with your function.If you didn’t use the corresponding data structures, you will not get any points.
When writing on paper, we represent a Python list with elements 1, 2, 3 as[1, 2, 3]. We represent a linked list with elements 1, 2, 3 (1 being the head of the linked list) as 1→2→3.
You may upload as many times as you want before the deadline. Each time the autograder will let you know how many of the test cases you have passed/failed. To prevent people from manipulat- ing the autogader, the content of some of the test cases are hidden.
Pleasedo not copy others’ answers. Autograder can detect similar code. Also, for your own benefit, do not try to find solutions online.
Problem 1:Stack2
Implement a class for stacks (calledStack2) using the Queue class we defined in class. In other words,
the only operations that can be used in your Stack2 class are the ones defined in the Queue class.
Problem 2
Given a linked list, transform it into a Python list. The head of the linked list corresponds to the left-most element of the Python list. When the input linked list is empty, the output Python list should be empty as well.
Example: When the input linked list is 1→2→3, the output Python list should be[1,2,3]. Solve the problem both iteratively and recursively. The template contains two functions:
•transform(lst1, lst2): solves the problem using iteration, i.e., for or while loop.No points will be given if the function is not iterative.
1
•transformRecursive(lst1, lst2): solves the problem using recursionNo points will be given if the function is not recursive.
Problem 3
Given two (possibly empty) linked lists, concatenate them such that the first list comes first.
Example: When the first input linked listlst1is 1→2→3 and the secondlst2is 7→8→9, the output
linked list is 1→2→3→7→8→9.
Solve the problem both iteratively and recursively. The template contains two functions:
•concatenate(lst1, lst2): solves the problem using iteration, i.e., for or while loopNo points will be given if the function is not iterative.
•concatenateRecursive(lst1, lst2): solves the problem using recursionNo points will be given if the function is not recursive.
Hint: For the recursive version, it would be helpful to define a helper function forconcatenateRecursive. The helper function would be recursive, butconcatenateRecursiveitself is not.
Note: Only linked lists are used in this questions. Python lists or other data structure cannot be involved in any way.
2
this isthetemplate that we are suppose to turn the answers in
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
class Node:
def __init__(self, val):
self.val = val
self.next = None
def getVal(self):
return self.val
def getNext(self):
return self.next
def setVal(self, val):
self.val = val
def setNext(self, node):
self.next = node
"""
Problem 1: Stack2
"""
class Stack2:
def __init__(self):
return
def isEmpty(self):
return
def push(self, item):
return
def pop(self):
return
def peek(self):
return
def size(self):
return
"""
Problem 2: tranform (iterative)
Input: lst - the head node of a linked list
Output: a Python list
"""
def transform(lst):
return
"""
Problem 2: tranform (recursive)
Input: lst - the head node of a linked list
Output: a Python list
"""
def transformRecursive(lst):
return
"""
Problem 3: concatenate (iterative)
Input: lst1 - the head node of a linked list
lst2 - the head node of another linked list
Output: the head node of a linked list
"""
def concatenate(lst1, lst2):
return
"""
Problem 3: concatenate (iterative)
Input: lst1 - the head node of a linked list
lst2 - the head node of another linked list
Output: the head node of a linked list
"""
def concatenateRecursive(lst1, lst2):
return