1. The ArrayStack class (section 14.4) is an Array implementation of a stack. :a) Complete the big-oh notation for each stack methods assuming the Array implementation: ("n" is the # items)Big-ohisEmpty( ) len( )peek( )pop( )push(item)__init__(constructor)b) The below push method of the ArrayStack class doubles the array size when it fills. For a stack of size n, howmany moves due to resizing of arrays occurred?c) Modify the push method of the ArrayStack class in the file stack.py such that it reduces the array sizewhen the logical size of the array is less than or equal to one-fourth of its physical size and its physical size isgreater than the default capacity. In thiscase, reduce the physical size of thearray either to half its physical size or toits default capacity, whichever is greater. Data Structures (810:052) Lecture 8 Name:_________________Lecture 8 - Page 1abc topbottom Stack "Abstract" _item: _top: _size: 23ArrayStack Object Array Objecta b c0 1 2 3 9 def push(self, newItem): """Inserts newItem at top of stack.""" # Resize array if necessary if len(self) == len(self._items): temp = Array(2 * self._size) for i in xrange(len(self)): temp[i] = self._items[i] self._items = temp # newItem goes at logical end of array self._top += 1 self._size += 1 self._items[self._top] = newItem def pop(self): """Removes and returns the item at top of the stack. Precondition: the stack is not empty.""" oldItem = self._items[self._top] self._top -= 1 self._size -= 1 # Resizing the array if necessary return oldItem""" File: node.py Node class for one-way linked structures. """class Node(object): def __init__(self, data, next = None): """Instantiates a Node with default next of None""" self.data = data self.next = next2. The Node class (in node.py) is used to dynamically create storage for a new item added to the stack. TheLinkedStack class (in stack.py) uses this Node class. Conceptually, a LinkedStack object would look like:abc topbottom Stack "Abstract" _top: _size: 3 data next data next data next'c' 'b' 'a'LinkedStack Objecta) Complete the push and pop methods.b) Trace the __str__ call for the abovestack.c) Complete the big-oh notation for each of the following stack methods assuming this linked implementation:Big-ohisEmpty( ) len( )peek( )pop( )push(item)__init__Data Structures (810:052) Lecture 8 Name:_________________Lecture 8 - Page 2""" File: stack.py Stack Implementations """from node import Nodeclass LinkedStack(object): """ Link-based stack implementation.""" def __init__(self): self._top = None self._size = 0 def push(self, newItem): """Inserts newItem at top of stack.""" def pop(self): """Removes and returns the item at top of the stack. Precondition: the stack is not empty.""" def peek(self): """Returns the item at top of the stack. Precondition: the stack is not empty.""" return self._top.data def __len__(self): """Returns the number of items in the stack.""" return self._size def isEmpty(self): return len(self) == 0 def __str__(self): """Items strung from bottom to top.""" # Helper recurses to end of nodes def strHelper(probe): if probe is None: return "" else: return strHelper(probe.next) + str(probe.data) + " " return
View Full Document
Unlocking...