Description In this project, you will be implementing a stack class. As learned
ID: 3756816 • Letter: D
Question
Description
In this project, you will be implementing a stack class. As learned in class, a stack is an abstract data type where “pushing” and “popping” items always occurs at the same end, often referred to as the “top”. A stack class has been created for you. Your assignment is to complete the remaining functions to have a fully functional stack class, in addition to implementing functions to reverse a given stack and to replace items in a stack.
Assignment Specifications
The point of this project is to implement the functionality of a stack, which would be trivial using Python list methods. Do not use Python list methods outside of the grow or shrink functions.
Your task will be to complete the methods listed below:
The Stack class is included in the starter file with the following functions and should not be edited.
__init__
This function initializes an empty stack. Optional argument is capacity, which defaults to two if no argument is passed in. The three member variables of the function are:
capacity: the number of data items the stack can hold
data: the data in the stack
size: the number of data items in the stack
__str__
This function provides a string representation of the Stack. Note that the the number of data items that this function will print is equal to size, and if there are only None items in the stack, this function will print Empty Stack. Make sure you are properly updating size if you are using this function for debugging.
__eq__
This function checks if two stacks are equivalent to each other, including checking their capacity, and data. If they are equal, returns True, otherwise returns False.
The rest of the functions listed are your responsibility to complete and test. Take note of specified parameters and return values, as well as the listed time and space complexities we expect from your functions. Do not change the function signatures.
stack_size(self): Returns the current number of items in the stack.
Time complexity: O(1)
Space complexity: O(1)
is_empty(self): Returns True if the stack is empty, False if not.
Time complexity: O(1)
Space complexity: O(1)
top(self): Returns the top item from the stack, None if the stack is empty. Does NOT remove the top item.
Time complexity: O(1)
Space complexity: O(1)
push(self, val): Adds val to the top of the stack, returns nothing.
Time complexity: O(1)*
Space complexity: O(1)*
pop(self): Removes the top item from stack by setting it back to None and returns the top item from the stack. Returns None if empty.
Time complexity: O(1)*
Space complexity: O(1)*
grow(self): Resize the stack to be 2 times its previous size when stack size equals capacity. Returns nothing.
Time complexity: O(N)
Space complexity: O(N)
shrink(self): Resize the stack to be half its current size when stack size is less than or equal to half its capacity. Note that stack capacity should never be below 2. Returns nothing.
Time complexity: O(N)
Space complexity: O(N)
* refers to amortized time, or average case performance when the operation is done many times. Normally, pushing or popping an item to/from the stack takes constant time, until the case where you have to grow or shrink the stack. Each grow/shrink operation takes O(N) time, but you’ve waited longer to do it (until the stack is full/half empty), so the cost is “spread out” among the prior insertions/removes.
In addition to the above methods, you must complete two more functions: reverse and replace.
reverse(stack): Reverse the order of the given stack, stack. Returns the reversed stack.
Time complexity: O(N)
Space complexity: O(N)
replace(stack, old, new): Replace all instances of the integer value old in the given stack, stack with the integer value new. Return the stack with the replaced values.
Time complexity: O(N)
Space complexity: O(N)
Starter code:
class Stack:
"""
Stack class
"""
def __init__(self, capacity=2):
"""
DO NOT MODIFY
Creates an empty Stack with a fixed capacity
:param capacity: Initial size of the stack. Default size 2.
"""
self.capacity = capacity
self.data = [None] * self.capacity
self.size = 0
def __str__(self):
"""
DO NOT MODIFY
Prints the values in the stack from bottom to top. Then, prints capacity.
:return: string
"""
if self.size == 0:
return "Empty Stack"
output = []
for i in range(self.size):
output.append(str(self.data[i]))
return "{} Capacity: {}".format(output, str(self.capacity))
def __eq__(self, stack2):
"""
DO NOT MODIFY
Checks if two stacks are equivalent to each other. Checks equivalency of data and capacity
:return: True if equal, False if not
"""
if self.capacity != stack2.capacity:
return False
count = 0
for item in self.data:
if item != stack2.data[count]:
return False
count += 1
return True
def stack_size(self):
return self.size()
def is_empty(self):
if self.size()==0:
return True
return False
def top(self):
pass
def push(self, val):
pass
def pop(self):
pass
def grow(self):
pass
def shrink(self):
pass
def reverse(stack):
pass
def replace(stack, old, new):
pass
Explanation / Answer
So the source code for stack implement is
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, data):
self.items.append(data)
def pop(self):
return self.items.pop()
s = Stack()
while True:
print('push <value>')
print('pop')
print('quit')
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'push':
s.push(int(do[1]))
elif operation == 'pop':
if s.is_empty():
print('Stack is empty.')
else:
print('Popped value: ', s.pop())
elif operation == 'quit':
break
And the output will be like this-
push <a value>
pop
quit
What would you like to do? push 8
push <a value>
pop
quit
What would you like to do? push 7
push <another value>
pop
quit
What would you like to do? pop
Popped value: 7
push <value>
pop
quit
What would you like to do? pop
Popped value: 8
push <value>
pop
quit
What would you like to do? pop
Stack is empty.
push <value>
pop
quit
What would you like to do? quit
Case 2:
push <value>
pop
quit
What would you like to do? pop
Stack is empty.
push <value>
pop
quit
What would you like to do? push 1
push <value>
pop
quit
What would you like to do? pop
Popped value: 1
push <value>
pop
quit
What would you like to do? quit