Question

Python - Please include running time of push(), pop(), and top() methods and tester code for all methods.

Design a stack ADT using a single queue as an instance variable, and only constant additional local memory within the method bodies. What is the running time of the push(), pop(), and top() methods for your design? Implement your modified stack ADT in Python, including tester code to test all its methods.

Answer 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

# Implement Stack using single queue and recursion class Stack:     # Constructor     def __init__(self):         self.q = []     # Insert an item into the stack     def push(self, data):         self.q.append(data)     # Utility function to reverse contents of a queue     def reversedeque(self):         # base case         if not self.q:             return         # hold front element in recursion call stack and insert         # it back into the queue after recursive call is over         front = self.q.pop()         self.reversedeque()         self.q.append(front)     # Remove the top item from the stack     def pop(self):         # if the queue is isEmpty         if not self.q:             print("Underflow!!")             exit(0)         # reverse the queue         self.reversedeque()         # pop front element of reversed queue         front = self.q.pop()         # revert the queue to original state         self.reversedeque()         return front if __name__ == '__main__':     keys = 1, 2, 3, 4, 5     # insert above keys into the stack     s = Stack()     for key in keys:         s.push(key)     for i in range(len(keys) + 1):         print(s.pop())